Эффективная сортировка?

Question

Я уже давно ищу ответ на этот вопрос ... «Какой самый эффективный способ сортировки миллиона 32-битных целых чисел?»

Мне кажется, что быстрая сортировка - это самоеэффективный в сортировке .. со средним временем выполнения O (n * log n).(с наихудшим случаем O (n²)) ..

Но некоторые результаты поиска говорят, что сортировка Radix / сортировка слиянием эффективна для сортировки миллионов целых чисел.

Любые указатели?

Answer 1

Гарантируется, что Mergesort будет O (n lg n), но имеет больший объем памяти, чем быстрая сортировка.

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

Сортировка по корням: O (n * r), где r - длина чисел.

Чтобы определить, лучше ли основание, чем выбранный вами метод LG-N, сделайте следующее:

n * r < n * lg (n)
divide by n on both sides
r < lg(n)

We know r is 32 bits

32 < lg(n)

for both sides, take 2^x

2^32 < 2^(lg(n)

2^32 < n

Так что, если n меньше 2 ^ 32 (4 миллиардов), используйте алгоритм lg-n.

Лично я бы использовал быструю сортировку, перетасовывая ее, если нужно, чтобы предотвратить ее деградацию.

Answer 2

если у вас достаточно места, возможно, вы можете попробовать сортировку по группам (http://en.wikipedia.org/wiki/Bucket_sort). Это более эффективно, но требует дополнительной памяти для хранения данных.

Answer 3

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

Answer 4

Корень лучше, если для больших чисел, особенно когда вы знаете диапазон чисел.

Исправление расчета:

Корень равен O (кН) , где k - количество цифр в наибольшем числе. (На самом деле речь идет о d * k * N , где d - база цифр, количество блоков, которые будут использоваться ... Алфавит = 26, десятичный = 10, двоичный = 2)

Максинт = 4 294 967 296
32 бита: k = 32 / log (d)

База 10 Radix:

d*k*n = 10*10*n < nlogn .... 100 < logn ... n > 2^100  

База 2 Radix:

d*k*n = 2*32*n < nlogn .... 64 < logn ... n > 2^64

То есть для 32-разрядных чисел, если у вас более 2 ^ 64 чисел, n * k * N лучше, чем nlogn

Но, если вы знаете, что диапазон будет до 1024, а не MAXINT, например:

MaxNumber = 1024

Base 10 Radix:

d*k*n = 10*4*n < nlogn .... 40 < logn ... n > 2^40 

Base 2 Radix:

d*k*n = 2*10*n < nlogn .... 20 < logn ... n > 2^20

То есть для чисел до 1024, если у вас более 2 ^ 20 чисел, n * k * N лучше, чем nlogn

Потому что большая буква O отбрасывает мультипликативные константы на время работы и игнорирует эффективность для низких входных размеров, это не всегда показывать самый быстрый алгоритм в практика или для данных практически размера устанавливает, но подход все еще очень эффективен для сравнения масштабируемость различных алгоритмов как размеры ввода становятся большими.