Алгоритм сортировки вставок и пузырьковой сортировки против алгоритма быстрой сортировки

Я работаю над исследованием в классе, где я тестировал сортировку пузырьков и сортировку вставками, а также быструю сортировку. Я провел тест на случайных числах. Результаты показывают, что сортировка вставок выполняется быстрее, чем пузырьковая, а быстрая сортировка - самая медленная.

Итак, у меня есть рейтинг ниже по времени

сортировка вставок (самая быстрая)пузырьковая сортировка (вторая оценка)быстрая сортировка (самая медленная)

Принимая во внимание, что вставка и пузырьковая сортировка имеют сложность O (n2), тогда как быстрая сортировка O (n log n) и O (n log n) должна быть быстрее !!!

Кто-нибудь может поделиться со мной объяснениями?

Спасибо

(NSMutableArray *)quickSort:(NSMutableArray *)a
{
    // Log the contents of the incoming array
    NSLog(@"%@", a);

    // Create two temporary storage lists
    NSMutableArray *listOne = [[[NSMutableArray alloc]
    initWithCapacity:[a count]] autorelease];
    NSMutableArray *listTwo = [[[NSMutableArray alloc]
    initWithCapacity:[a count]] autorelease];
    int pivot = 4;

    // Divide the incoming array at the pivot
    for (int i = 0; i < [a count]; i++)
    {
        if ([[a objectAtIndex:i] intValue] < pivot)
        {
           [listOne addObject:[a objectAtIndex:i]];
        }
        else if ([[a objectAtIndex:i] intValue] > pivot)
        {
           [listTwo addObject:[a objectAtIndex:i]];
        }
    }

    // Sort each of the lesser and greater lists using a bubble sort
    listOne = [self bubbleSort:listOne];
    listTwo = [self bubbleSort:listTwo];

    // Merge pivot onto lesser list
    listOne addObject:[[NSNumber alloc] initWithInt:pivot]];

    // Merge greater list onto lesser list
    for (int i = 0; i < [listTwo count]; i++)
    {
        [listOne addObject:[listTwo objectAtIndex:i]];
    }

    // Log the contents of the outgoing array
    NSLog(@"%@", listOne);

    // Return array
    return listOne;
}
 martiert16 окт. 2012 г., 13:10
Первый вопрос, который приходит на ум: сколько данных вы использовали? Вы распечатали стартовый список и видели, что числа на самом деле случайные? Какой у вас алгоритм быстрой сортировки для определения значения расщепления?
 alex16 окт. 2012 г., 13:08
Насколько велики ваши данные, на которых вы тестируете, и используете ли вы одни и те же несортированные данные для каждого алгоритма?
 IVlad16 окт. 2012 г., 13:08
Вы либо неправильно реализовали быструю сортировку, либо вы сделали тест неправильно. Опубликуйте свои реализации и свой тест.
 Steve Jessop16 окт. 2012 г., 13:28
Ваша так называемая "быстрая сортировка" не является быстрой сортировкой. Это один раздел, за которым следуют два типа пузырьков плюс слияние.
 helpermethod16 окт. 2012 г., 13:08
С небольшим количеством элементов сортировка вставки выполняется быстрее, чем быстрая сортировка, потому что в то время как O (N ^ 2) имеет действительно небольшой постоянный коэффициент. Для лучшего результата попробуйте отсортировать массивы с большим количеством элементов (например, 1000, 1000000, 1000000000 элементов). Я не знаю, как пузырьковая сортировка ведет себя для небольших массивов, но я предполагаю, что только для нескольких элементов она может превзойти быструю сортировку.

Ответы на вопрос(3)

ы (такие как сортировка вставками) будут работать довольно хорошо, более качественные алгоритмы не нужны.

Однако, когда n большое (скажем, n = 10000000), быстрая сортировка, как правило, будет намного лучше, чем сортировка вставкой (или пузырьковая сортировка).

 Oracle Oracle16 окт. 2012 г., 13:43
спасибо за хороший пример
 Oracle Oracle16 окт. 2012 г., 13:46
Еще раз спасибо, как насчет сортировки пузырьков и сортировки вставок
 Oracle Oracle16 окт. 2012 г., 13:17
но я не понимаю, почему сортировка вставок лучше в числе samll, вы можете любезно объяснить, почему?
 Steve Jessop16 окт. 2012 г., 13:22
@OracleOracle: вот пример чего-тоO(n^2): for (int = 0; i < n*n; ++i) printf("%d\n", i);, Вот пример чего-тоO(n log n): for (int i = 0; i < n * log(n); ++i) { for (int j = 0; j < 1000*1000; ++j) printf("%d\n", i); }, Очевидно, для маленькихn первый код быстрее второго. Так почему бы сортировке вставки не быть быстрее, чем быстрой сортировке для малыхn только потому, что это хуже сложности? Причина, по которой он на самом деле быстрее, заключается в том, что у быстрой сортировки есть особые издержки (отслеживание разделов), которых нет у сортировки вставкой.
 Steve Jessop16 окт. 2012 г., 16:01
@OracleOracle: Я думаю, что для сортировки вставок требуется меньше сравнений, чем для сортировки пузырьков, а может быть и меньше копий. Конечно, наихудший случай пузырьковой сортировки (где самый маленький элемент начинается в конце) требуетn*(n-1) Сравнения, тогда как для вставки сортировка требует не менее половины этого. Со случайными данными, вероятно, есть небольшие элементы близко к концу. Их называют "черепахами", и они сильно повредили простой пузырьковый сорт.

быстрая сортировка сильно зависит от ввода. Вам нужно перемешать ввод, прежде чем сделать быструю сортировку. Если ваш вход отсортирован, быстрая сортировка может иметь сложность O (n2)

сортировка вставок также может быть быстрее для небольших массивов

 Roman Pekar16 окт. 2012 г., 13:14
например, если вы отсортировали входные данные и сделали разбиение вокруг первого элемента, то сложность составит 1/2 o (N2)
 Oracle Oracle16 окт. 2012 г., 13:16
если бы я жестко закодировал точку поворота как среднее число, это было бы хорошо? т. е. за 5000 нормально ли сделать пивот 2500 ??
 Roman Pekar16 окт. 2012 г., 13:13
Быстрая сортировка делает разбиение вокруг одного элемента. Чтобы иметь O (n log n), вы должны быть уверены, что этот элемент близок к среднему значению. Один из способов сделать это - перемешать ввод перед быстрой сортировкой.
 Daniel Fischer16 окт. 2012 г., 13:30
@OracleOracle Для любой стратегии, выбирающей фиксированный элемент в качестве основного, есть входные данные, которые делают быструю сортировку O (n²). Если массив действительно случайный (или хорошее приближение к этому), эти случаи очень маловероятны. Если вы выбираете опорную точку на медиану медиан, она гарантированно будет O (n * log n), но постоянный коэффициент относительно велик, в среднем он будет медленнее, чем более простая стратегия выбора опорных точек. Медиана 3 делает поведение O (n²) очень маловероятным, поэтому это хорошая стратегия. Выбор среднего элемента массива лучше первого, но имеет больше плохих случаев, чем медиана 3.
 Oracle Oracle16 окт. 2012 г., 13:12
Я протестировал несколько траншей 5000, 10000, 15000 и 20000. Для всех трех алгоритмов применяются одни и те же массивы. Этого достаточно, чтобы ускорить сортировку вставок
Решение Вопроса

O(nlogn) тогда "быстрее"O(n^2), но давайте вспомним, что означают большие обозначения O.

Это означает, что если алгоритм А имеет сложностьO(nlogn)для некоторых константN_1, а такжеc1, для каждогоn>N - алгоритм "быстрее", чемc1*n*log(n), Если алгоритм B имеетO(n^2)есть некоторые константыN_2,c2 такой, что алгоритм "быстрее", чемc2 * n^2 * log(n) заn > N_2.

Однако - что происходит до этогоN? и что это за константаC? Мы не знаем.АлгоритмB все еще может быть "быстрее", чем алгоритмA для небольших входов, но для больших входов - действительно,A будет быстрее (асимптотическая граница лучше).

Например, давайте возьмем случай, когда алгоритмA работает вT_1(n) = 10* nlog(n) опс, а алгоритмB работает вT_2(n) = n^2, заn=3 - мы получаем этоT_1(3) = 10*3*2 = 60 (мы используем инструмент дляlog(n)), а такжеT_2(3) = 9 - таким образом алгоритмB, хотяO(n^2) тогда быстрееA для этого входа.

Что касается быстрой сортировки и вставки сортировки:
Быстрая сортировка обычно очень быстрая и в очень редких случаях затухает в квадратное время (вероятность того, что это произойдет, невелика, если мы выберем случайный элемент в качестве стержня).

Тем не менее, константа за большой нотацией в быстрой сортировке больше, чем вставка сортировки. Таким образом -возможная оптимизация: используйте быструю сортировку, пока не достигнете определенного порога (скажем, 30 элементов), а затем сортировать этот подмассив с сортировкой вставки, а не быстрой сортировкой.Эта почта обсуждает эту оптимизацию.

Пузырьковая сортировка (эмпирически) ужасна для случайных массивов, но может быть полезной, если массив почти отсортирован и элементы «не на своем месте» находятся в начале.

Ваш ответ на вопрос