Каков наилучший алгоритм сортировки для случайного набора чисел?

Question

Мой коллега только что задал этот вопрос сегодня днем, и это вызвало у меня любопытство. Я разбираюсь в сортировке алгоритмов, но мне не хватает формальной степени в compsci / compeng (что-то, чего я не хочу признавать), я не могу понять, как это сделать. : Р

И да, это мягко в контексте реализации C # / .NET ... на всякий случай, если что-то немного изменить.

Спасибо, ребята. :)

Answer 1

Для чисел фиксированной длины вы не ограничены алгоритмами сортировки на основе сравнения, поэтому O(n*log(n)) - это , а не . Radix Sort работает в O(n) и может использоваться довольно удобно из-за удивительного свойства правильной сортировки поплавков IEEE 754, когда их битовый массив интерпретируется как целые числа.

Answer 2

Я вижу, что никто не упомянул introsort , который решает наихудший случай быстрой сортировки O(n^2) путем переключения на heapsort , когда глубина рекурсии превышает определенный порог. Это означает, что быстрая сортировка не даст возможности выродиться, поскольку ее количество рекурсивных вызовов определенно будет ограничено.

Другая оптимизация заключается в переключении на сортировку вставок всякий раз, когда число элементов последовательности, в которой вы находитесь в данный момент, мало (скажем, 16).

Вот так может выглядеть интросорт:

void Introsort(int A[], int N, int left, int right, int depth)
{
    if ( left < right ) // note: this doesn't switch to insertion sort if right - left is small enough
    {   
        if ( (1 << depth) > N )
            Heapsort(A, left, right);
        else
        {
            int P = Partition(A, left, right);
            Introsort(A, N, left, P, depth+1);
            Introsort(A, N, P+1, right, depth+1);
        }
    }
}

Это, в сочетании с хорошей функцией разбиения (просто случайный выбор оси должен быть достаточным для большинства целей), даст вам очень быстрый алгоритм сортировки.

Существует также выбор radix sort , который работает очень хорошо, особенно если ваши поплавки не слишком велики. Однако из того, что я видел, для радикальной сортировки требуются миллионы элементов, чтобы превзойти интросорт.

Answer 3

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

Например (с использованием gcc 3.4.6) применение qsort (по возрастанию) к {2, 1, nan, -1} дает {1, 2, nan, -1}.

С другой стороны, inf и -inf не проблема.

Answer 4

Теоретически вы сравниваете алгоритмы, используя big O нотацию , которая позволяет вам сравнивать, какой алгоритм будет быстрее для «почти бесконечной» задачи. На практике в большинстве случаев это очень хорошая отправная точка для сравнения того, как алгоритмы будут вести себя в реальной жизни.

Два самых популярных алгоритма быстрой сортировки - это MergeSort и быстрая сортировка. Сортировка слиянием гарантированно будет O (n log n) для любых данных, тогда как быстрая сортировка имеет среднее время O (n log n) и пессимистическое время O (n ^ 2). На практике большинство людей используют быструю сортировку, потому что:

1. Естественно, это происходит почти на месте (я думаю, что вы можете сделать сортировку слиянием на месте, но это утомительно и сделает ее медленнее - это увеличит постоянную, скрытую в нотации O) - для больших наборов данных это проблема, если данные не помещаются в память
2. На практике это быстрее в большинстве случаев
3. Вы можете слегка изменить его (т.е. взять медиану первого, среднего и последнего элемента для разбиения), чтобы было очень трудно получить данные, которые замедлили бы его

Подводя итог, я думаю, что быстрая сортировка будет быстрее для ваших случайных операций с плавающей запятой, даже если только смотреть на нотацию O, это кажется хуже - потому что вы получите ожидаемое O (n log n), и оно будет иметь меньшую постоянную, чем Сортировка слиянием.

Answer 5

Если вы хотите визуально представить алгоритмы сортировки, проверьте этот фантастический сайт:

Sorting-algorithms.com

Вы получите ощущение, которое лучше всего работает в разных случаях, но мой фаворит - сортировка слиянием, хотя она не намного лучше, чем быстрая сортировка.