Любимый метод сортировки

← →
Marser © (2005-11-14 18:31) [0]

Если нужно быстро написать код для сортировки одномерного массива, не используя дополнительные библиотеки и литературу, каким методом вы воспользуетесь скорее всего?

Вопрос возник после того, как препод выдал мне задание на сортировку(по возрастанию или убыванию в зависимости от параметра) массива памяти в AVR AT90. Задачу я решил быстро, применив свой излюбленный метод, до которого в своё время дошёл сам.

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

← →
Kerk © (2005-11-14 18:34) [1]

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

А быстрей всего написать TStringList.Sort :)

← →
Игорь Шевченко © (2005-11-14 18:35) [2]

TList.Soft(compare function)

← →
default © (2005-11-14 18:36) [3]

если числа целые и размерность их не высока то сортировка подсчётом рулит немеряно

← →
Юрий Зотов © (2005-11-14 18:36) [4]

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

← →
default © (2005-11-14 18:37) [5]

Kerk © (14.11.05 18:34) [1]
пузырь, ты что:)
хотя когда разупорядоченность невелика он рулит

← →
Marser © (2005-11-14 18:39) [6]

> А быстрей всего написать TStringList.Sort :)

> TList.Soft(compare function)

В AT90 ? :-)
Причём, на чистом асме, даже не на С. Впрочем, я уместился в надцать строк :-)

← →
Kerk © (2005-11-14 18:41) [7]

default © (14.11.05 18:37) [5]
пузырь, ты что:)

А мне редко приходится что-то сортировать вручную. А если и сортирую, то пару десятков элементов.

TList.Sort и ...ORDER BY рулят

← →
Mystic © (2005-11-14 18:52) [8]

Если в указаной архитектуре можно легко реализовать рекурсию, то скорее всего буду реализовывать быструю сортировку.

← →
Гаврила © (2005-11-14 19:06) [9]

Как то раз, очень давно, была задача отсортировать TList, содержащий очень много элементов (миллион и более)
Вызов Sort работал неприемлимо по времени, придумал вот что:
создаю второй TList в него переношу элементы из первого (вставка в сразу нужное место методом деления на два)
потом старый подменяю на новый

Как вы считаете - нормально придумал? Или отстой? :-)

← →
programania © (2005-11-14 19:25) [10]

Метод Шелла самый простой из самых быстрых
1млн за 1сек на С2800
var m:array of integer; q:integer=1000000; {$R *.DFM} PROCEDURE sort; var i,j1,g1,r,e:integer; begin //сортировка массива чисел m размером q g1:=q; while g1>0 do begin g1:=g1 div 2; i:=g1; while i<q do begin j1:=i-g1+1; while (j1>=1) and (m[j1]>m[j1+g1]) do begin r:=j1+g1; e:=m[j1]; m[j1]:=m[r]; m[r]:=e; dec(j1,g1) end; inc(i); end; end; end; procedure TForm1.Button1Click(Sender: TObject); var i:integer; begin setLength(m,q+1); for i:=1 to q do m[i]:=random(q); sort; end;

← →
Sergey Masloff (2005-11-14 20:51) [11]

Гаврила © (14.11.05 19:06) [9]
>Как вы считаете - нормально придумал? Или отстой? :-)
А сам-то как думаешь? Задачу решил? Быстрее стало? - рулез. Нет? - ацтой ;-))

← →
pasha_golub © (2005-11-14 21:25) [12]

> Гаврила © (14.11.05 19:06) [9]

TList - это значит указатели таскать... Наверное, можно было бы и без доп.списка.

> default © (14.11.05 18:37) [5]
>
> Kerk © (14.11.05 18:34) [1]
> пузырь, ты что:)

Классный метод. Особенно с некоторыми улучшениями вполне отвечает заданным начальным условиям. Особенно при теперешнем развитии техники, по-моему, абсолютно монописуально за 0,000002 или 0,000001 выполнится работа. Вот жили бы мы в годах 50, я бы воспринял ваш пост как стоящий. А на данный момент, это просто немножко понтов... ;0)

← →
default © (2005-11-14 22:19) [13]

pasha_golub © (14.11.05 21:25) [12]
"Особенно при теперешнем развитии техники, по-моему, абсолютно монописуально за 0,000002 или 0,000001 выполнится работа."
это смотря массивы какой величины сортируются
если такое различие, то, конечно, без разницы
вообще, в любой книге по теории алгоритмов показывается, что это заблуждение, что с возрастанием мощности компов ценность эффектинвых алгоритмов падает
насколько мне известно, пузырь эффективнее квиксорта когда массив почти упорядоченный
если памяти не жалко, то сортировка подсчётом рулит куче всех

← →
TUser © (2005-11-14 22:24) [14]

Если маленький массив - пузырьком. Большой - квиком. В особых случаях буду думать.

← →
default © (2005-11-14 22:27) [15]

смотря, конечно, какие единицы измерения у 0,000002 или 0,000001 :)

← →
partizan (2005-11-15 02:26) [16]

Heapsort рулит!
А если надо список а не массив сортировать, то сортировка слиянием

← →
Германн © (2005-11-15 03:14) [17]

Всё классно рулит! Но с учётом "препод выдал мне задание на сортировку(по возрастанию или убыванию в зависимости от параметра) массива памяти в AVR AT90" возникают проблемы. Стэк там весьма ограничен.

← →
wicked © (2005-11-15 03:40) [18]

> Если нужно быстро написать код для сортировки одномерного
> массива, не используя дополнительные библиотеки и литературу,
> каким методом вы воспользуетесь скорее всего?

пузырь.... знаю, что неэффективно, но ничего другого не помню.... :(

если есть доступ к литературе, то буду использовать то, что там найду.... ;)
постараюсь найти либо quick sort, либо версии, базирующиеся на нем....

если библиотеки в счет, то
1) sort (#include <algorithm.h>) - если пишу на си++
2) qsort (#include <stdlib.h>) - если пишу на простом си
3) TStringList.Sort, TList.Sort - если доступен vcl
4) что попадется.... ;)

← →
Sha © (2005-11-15 12:24) [19]

Оптимизированная QuickSort,
стандартная HeapSort.

← →
Булат Шакиров © (2005-11-15 13:04) [20]

Если нужно быстро написать, то через нахождение макс. (мин.) элемента и перестановку. Не в курсе, как это называется. Сам придумал ;)

← →
Marser © (2005-11-15 15:47) [21]

Не понимаю влюбленности большинства в "пузырёк". Мне он почему-то не кажется самым естественным. Метод выбора, ИМХО, как раз такой.

← →
Marser © (2005-11-15 15:53) [22]

Кстати, ещё выяснилось, что многие неправльно понимають, что есть "пузырёк". Например, моя сестра как раз назвала метод выбора методом "пузырька". Но алголист и Бакнелл на моей стороне :-)

← →
Marser © (2005-11-15 15:53) [23]

Marser © (15.11.05 15:53) [22]
Например, моя сестра как раз назвала метод выбора методом "пузырька".

А где в "выборе" элемент массива всплывает? Он там телепортируется в нужное место ;)

И Кнут тоже. Сегодня в книжном магазине пролистал третий том :-)

З.Ы. Извиняюсь за дубли....

Любителям пузырька, выбора и т.п. O(N^2) алгоритмов сортировки посвящается.

Разница в скорости работы этих алгоритмов и нормальных O(N logN)
алгоритмов на больших массивах не в разы, как думают некоторые.

Разница такова: один не завершится при вашей жизни, а другой сортирует :)

> Любителям пузырька, выбора и т.п. O(N^2) алгоритмов сортировки
> посвящается.
>
> Разница в скорости работы этих алгоритмов и нормальных O(N
> logN)
> алгоритмов на больших массивах не в разы, как думают некоторые.
>
>
> Разница такова: один не завершится при вашей жизни, а другой
> сортирует :)

Знаю, Бакнелла читал :-)
Хотя до твоего уровня пониманию алгоритмов оочень далеко...

> Sha © (15.11.05 16:12) [26]

> на больших массивах не в разы

Большой это сколько? И соответственно чего сортируем? И на какой машине?

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

Sha © (15.11.05 16:12) [26]

O(NlogN)=5 минут
O(N^2)=5 лет=5*60*24*365=2628000 минут
Имеем:
N^2/(NlogN)=2628000/5
N/logN=525600
N=525600logN
N>5000000

При всем желании для таких размерностей уже не поленишься QuickSort написать.
А для меньших вполне пузырек сойдет :)

> O(N^2)

(N^2)/2 для выбора, если быть точным.

> pasha_golub © (15.11.05 16:23) [28]
2 примера:
Построение индекса в online БД.
Выдача отсортированного оглавления www-сервером.

> Sha © (15.11.05 17:15) [32]

Я на триста процентов согласен, что бывают такие ситуации... Но и online БД может состоять из трех записей. ;0)

Любимый метод сортировки Найти похожие ветки