Здравствуйте, emergenter, Вы писали:
E>Подскажите пожалуйста какой наиболее быстрый алгоритм сортировки выбрать и где взять рабочий код? заранее благодарен!
Здравствуйте, Bell, Вы писали:
B>Массива чисел? Массива объектов некоторого класса? Массива указателей на объекты?
B>По существу: если используешь С++ — смотри std::sort, если С — функция qsort.
Эти функции не всегда самые быстрые — сортировка Хаара имеет свои узкие места. Зато универсальные.
Надо рассматривать конкретную ситуацию и выбирать алгоритм, благо их много.
Сортировка подсчетом рулит, если ее можно применить
Здравствуйте, emergenter, Вы писали:
E>Подскажите пожалуйста какой наиболее быстрый алгоритм сортировки выбрать и где взять рабочий код? заранее благодарен!
1. Сколько элементов сортируется?
2. Какой у них тип?
3. Какой язык программирования?
Без этого точно ответить нельзя.
Выбор сортировки:
а) если элементов мало, то пишем пузырек и не мучимся (или берем любую другую сортировку)
б) если диапазон значений маленький, а элементов много, берем сортировку подсчетом
с) если есть стандартная реализация qsort (или нестандартная) и никто специально против нее тестов придумывать не будет, берем qsort. Тут есть варианты: простой qsort, медиана из 3х, медиана из 5и. Чем отличаются? Ответ прост: средней и максимальной скоростью работы. Варианты перечислены в порядке уменьшения средней скорости и увеличения максимальной.
д) если нужна стабильность по скорости и памяти, берем heapsort
е) если задача специфическая, то выбираем из остального наиболее подходящее
Здравствуйте, Tan4ik, Вы писали:
T>Варианты перечислены в порядке уменьшения средней скорости и увеличения максимальной.
Варианты перечислены в порядке уменьшения средней скорости и увеличения минимальной.
Здравствуйте, Sunworx, Вы писали:
K>>Сортировка подсчетом рулит, если ее можно применить
S>подсчетом чего?
Подсчётом элементов!
PS. Это был ответ в стиле развившейся дискуссии:
Подскажите пожалуйста какой наиболее быстрый алгоритм сортировки выбрать и где взять рабочий код? заранее благодарен!
сортировки чего?
Сортировка массива!
подсчетом чего?
PPS.
Если элементы массива arr[] суть целые числа, и размер массива сравним с диапазоном этих чисел, то
* заводим массив счётчиков c[], размером равный диапазону чисел
* за один проход по исходному массиву инкрементируем счётчики ++c[arr[k]]
* за один проход по массиву счётчиков порождаем сортированный массив
Здравствуйте, emergenter, Вы писали:
E>Сортировка массива!
Чем использовать массив как контейнер и потом сортировать, лучше использовать в качестве контейнера сортированный массив — он сразу помещает число в нужное место — это работает быстрее, потому что элементов в массиве меньше (пока он заполняется), а сортировать придется сразу полный массив.
Здравствуйте, GUID, Вы писали:
GUI>Здравствуйте, emergenter, Вы писали:
E>>Сортировка массива!
GUI>Чем использовать массив как контейнер и потом сортировать, лучше использовать в качестве контейнера сортированный массив — он сразу помещает число в нужное место — это работает быстрее, потому что элементов в массиве меньше (пока он заполняется), а сортировать придется сразу полный массив.
Очень, очень спорное утверждение.
Формально конечно это верно. Взять к примеру std::set и std::vector:
сортировка заполненного вектора с помощью std::sort — N log(N), последовательная вставка в set — log(N!) (сложность вставки в set — log(N)), что конечно же меньше. Но не надо забывать о том, что вектор — это непрерывный блок памяти, и может целиком поместиться в кэше процессора, а вот узлы сета могут находится в памяти "далеко" друг от друга. Так что на практике вектор частенько выигрывает.
Здравствуйте, Tan4ik, Вы писали:
T>Здравствуйте, emergenter, Вы писали:
E>>Подскажите пожалуйста какой наиболее быстрый алгоритм сортировки выбрать и где взять рабочий код? заранее благодарен!
T>1. Сколько элементов сортируется? T>2. Какой у них тип? T>3. Какой язык программирования?
T>Без этого точно ответить нельзя.
T>Выбор сортировки: T>а) если элементов мало, то пишем пузырек и не мучимся (или берем любую другую сортировку) T>б) если диапазон значений маленький, а элементов много, берем сортировку подсчетом T>с) если есть стандартная реализация qsort (или нестандартная) и никто специально против нее тестов придумывать не будет, берем qsort. Тут есть варианты: простой qsort, медиана из 3х, медиана из 5и. Чем отличаются? Ответ прост: средней и максимальной скоростью работы. Варианты перечислены в порядке уменьшения средней скорости и увеличения максимальной. T>д) если нужна стабильность по скорости и памяти, берем heapsort T>е) если задача специфическая, то выбираем из остального наиболее подходящее
Здравствуйте, Serginio1, Вы писали:
T>>Выбор сортировки: T>>а) если элементов мало, то пишем пузырек и не мучимся (или берем любую другую сортировку) T>>б) если диапазон значений маленький, а элементов много, берем сортировку подсчетом T>>с) если есть стандартная реализация qsort (или нестандартная) и никто специально против нее тестов придумывать не будет, берем qsort. Тут есть варианты: простой qsort, медиана из 3х, медиана из 5и. Чем отличаются? Ответ прост: средней и максимальной скоростью работы. Варианты перечислены в порядке уменьшения средней скорости и увеличения максимальной. T>>д) если нужна стабильность по скорости и памяти, берем heapsort T>>е) если задача специфическая, то выбираем из остального наиболее подходящее
S> А почему моей любимой сортировки слиянием не упомянул S> http://www.rsdn.ru/Forum/Message.aspx?mid=577195&only=1
А если серьезно, то попровляюсь:
д2)если нужна стабильность по скорости и памяти, и затраты на дополнительную O(N) память для нас не критичны, а скорость очень критична, берем mergesort
На самом деле я не сильно ошибся, забыв про mergesort (кроме пункта е), т.к.
1. quicksort(простой) быстрее mergesort, если ему не подбирать специально сортируемые данные
2. quicksort(медиана из 3х) быстрее mergesort (незначительно), но он не требует дополнительной памяти, а плохие данные ему подобрать очень сложно
3. heapsort устойчив по времени, не требует дополнительной памяти и незначительно медленее mergesort
Так что... я не вижу фишки mergesort... а его использование для простой сортировки массива в памяти... нужно только чтобы выделиться "а у меня вон как!"...
Здравствуйте, Bell, Вы писали:
GUI>>Чем использовать массив как контейнер и потом сортировать, лучше использовать в качестве контейнера сортированный массив — он сразу помещает число в нужное место — это работает быстрее, потому что элементов в массиве меньше (пока он заполняется), а сортировать придется сразу полный массив.
B>Очень, очень спорное утверждение. B>Формально конечно это верно. Взять к примеру std::set и std::vector: B>сортировка заполненного вектора с помощью std::sort — N log(N), последовательная вставка в set — log(N!) (сложность вставки в set — log(N)), что конечно же меньше. Но не надо забывать о том, что вектор — это непрерывный блок памяти, и может целиком поместиться в кэше процессора, а вот узлы сета могут находится в памяти "далеко" друг от друга. Так что на практике вектор частенько выигрывает.
Частенько? Я бы сказал всегда и очень выигрывает! Причем разница не в 2-3 раза, а на порядки!
Здравствуйте, GUID, Вы писали:
E>>Сортировка массива!
GUI>Чем использовать массив как контейнер и потом сортировать, лучше использовать в качестве контейнера сортированный массив — он сразу помещает число в нужное место — это работает быстрее, потому что элементов в массиве меньше (пока он заполняется), а сортировать придется сразу полный массив.
Ваш совет может пригодиться только для очень маленького количества специфических случаев. Для обычной же сортировки ничего лучше "свалить в кучу и отсортировать" сделать нельзя. И придется с этим смириться.
T>А если серьезно, то попровляюсь: T>д2)если нужна стабильность по скорости и памяти, и затраты на дополнительную O(N) память для нас не критичны, а скорость очень критична, берем mergesort
T>На самом деле я не сильно ошибся, забыв про mergesort (кроме пункта е), т.к. T>1. quicksort(простой) быстрее mergesort, если ему не подбирать специально сортируемые данные
Ну разница на интах не существенна на рассортированных последовательных данных
(то есть поле quicksort где она работает с максимальной скоростью)
Так вот результаты сортировки 10 миллионного массива
QuickSort(простой) 2 сек
MergeSort 2.2 сек
А вот результаты сортировки 25 миллионного массива
QuickSort 5.5 сек
MergeSort 5.8 сек.
Причем шина 266 (правда память 400). Но более быстрой шине результаты могут быть другими. Так что самой быстрой сортировкой считать QuickSort не стал бы. Кроме всего прочего нужна была для решения специфических задач таких как сортировка сцепленных страниц Б+ деревьев и больших файлов.
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Serginio1, Вы писали:
S> Ну разница на интах не существенна на рассортированных последовательных данных S> (то есть поле quicksort где она работает с максимальной скоростью)
S> Так вот результаты сортировки 10 миллионного массива S>QuickSort(простой) 2 сек S>MergeSort 2.2 сек
S>А вот результаты сортировки 25 миллионного массива S>QuickSort 5.5 сек S>MergeSort 5.8 сек.
Это либо неправильный QuickSort, либо оптимизнутый MergeSort. В любом случае, они не в равных условиях.
S> Причем шина 266 (правда память 400). Но более быстрой шине результаты могут быть другими. Так что самой быстрой сортировкой считать QuickSort не стал бы.
Зря. Лучше пока ничего не придумали (по средней скорости).
S> Кроме всего прочего нужна была для решения специфических задач таких как сортировка сцепленных страниц Б+ деревьев и больших файлов.
Вот так бы сразу. Это уже пункт е.
Здравствуйте, Tan4ik, Вы писали:
T>Здравствуйте, Serginio1, Вы писали:
S>> Ну разница на интах не существенна на рассортированных последовательных данных S>> (то есть поле quicksort где она работает с максимальной скоростью)
S>> Так вот результаты сортировки 10 миллионного массива S>>QuickSort(простой) 2 сек S>>MergeSort 2.2 сек
S>>А вот результаты сортировки 25 миллионного массива S>>QuickSort 5.5 сек S>>MergeSort 5.8 сек.
T>Это либо неправильный QuickSort, либо оптимизнутый MergeSort. В любом случае, они не в равных условиях.
вот код MergeSort http://www.rsdn.ru/Forum/Message.aspx?mid=577195&only=1
Procedure SortIntegerArray(a:TIntArray);
Var TempBuffer:Integer;
BeginArray:Cardinal;
MidlVar:Integer;
procedure QuickSort(L, R: PInteger);
var
I, J: PInteger;
begin
I :=L;
J :=R;
MidlVar:=PInteger(Cardinal(L)+(((Cardinal(R)-Cardinal(L)) shr 1) and SpaseInteger ))^;
repeat
while (I^- MidlVar) < 0 do
Inc(I);
while (J^- MidlVar) > 0 do
Dec(J);
if Cardinal(I) <= Cardinal(J) then
begin
TempBuffer:=I^;
I^:=J^;
J^:=TempBuffer;
Inc(I);
Dec(J);
end;
until Cardinal(I) > Cardinal(J);
if Cardinal(L) < Cardinal(J) then
QuickSort(L,J);
if Cardinal(R)>Cardinal(I) then
QuickSort(I,R);
end;
Begin
BeginArray:=PCardinal(@a)^;
QuickSort(PInteger(BeginArray),PInteger(BeginArray+(PCardinal(BeginArray-4)^-1)*4));
End;
Что бу замедления доступа по индексу массива не было. К сожалению это беда Delphhi. S>> Кроме всего прочего нужна была для решения специфических задач таких как сортировка сцепленных страниц Б+ деревьев и больших файлов. T>Вот так бы сразу. Это уже пункт е.
Но какие результаты дает. Самый ломовой метод. Все побарабану, кроме памяти!!!!!
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Насколько я знаю сортировка слиянием самая быстрая если нельзя Radix Sort приклеить.
Но сортировать надо чуть умнее чем стандартное описание.
1. Находим ВСЕ монотонные ( отсортированные или отсортированные наоборот) ПОДучастки последовательности.
2. Сливаем сортированные последовательности друг с другом ( соизмеримо с размерами последовательностей)
3. Делаем 1 и 2 пока не отсортируем.
ВЫГОДЫ:
Кеш френдли, особенно в случае баз данных всяких.
Нет плохих случаев ! ( и это еще не все ! )
Лучшее время O(N) ( в случае полностью отсортированной последовательности или отсортированной наоборот) худшее O(N*LOGN) ( надо нехило потрудиться чтобы найти такой случай).
НЕДОСТАТКИ:
требует дополнительной памяти для эффективной реализации. (может кто знает другую ? )
эффективная реализация довольно сложна.
Перекуём баги на фичи!
