Алгоритм сортировки масива.

← →
sergey2 (2003-07-19 12:08) [0]

Вот чего-то зашла в голову мысль насчет сабжа.
Допустим нам нужно посортировать масив по возрастанию.
Конечно возможно есть уже готовые функции/процедуры для этого, но если принять во внимание что может быть случай когда это не массив, а например база данных, для которой в силу некоторых причин нецелесообразно создавать индексный файл, или еще что-нить в этом роде, то как их отсортировать в таком случае?
Вот есть алгоритм типа такого:

var
....
f:=true;
while f do
begin
f:=false;
for i=1 to N-1 do
begin
if A[i]>A[i+1] then
begin
B:=A[i];
A[i]:=A[i+1];
A[i+1]:=B;
f:=true;
end;
end;
end;

но для очень больших массивов (БД и пр.) он будет слишком долго работать. Можно его слегка оптимизировать (уменьшив кол-во присваиваний в цикле), но все равно это почти ничего не дает.
Да и время работы его пропорционально квадрату кол. элементов массива.
Существуют ли другие алгоритмы для этого? А то что-то ничего в голову не лезет... Вобщем что можно придумать?

← →
Sergey Masloff (2003-07-19 12:19) [1]

Прочитать хотя бы одну книжку по программированию (а не по манипуляциям мышью).
Например:
Керниган и Пайк - практика программирования
Ахо и Ульман -Структуры данных и алгоритмы
Торп Структуры данных в С++

Вобщем любая нормальная книжка по программированию с этого начинается. Прочитай, не пожалеешь. Пару алгоритмов конечно тебе и тут расскажут но...

← →
Palladin (2003-07-19 12:20) [2]

Существуют конечно, причем у тебя на диске, прямо в директории %Delphi%\Demos\Threads

← →
Anatoly Podgoretsky (2003-07-19 12:25) [3]

Sergey Masloff (19.07.03 12:19)
А Кнута почто обидел?

← →
sergey2 (2003-07-19 12:28) [4]

> Sergey Masloff (19.07.03 12:19)
> Прочитать хотя бы одну книжку по программированию (а не
> по манипуляциям мышью).
> Например:
> Керниган и Пайк - практика программирования
> Ахо и Ульман -Структуры данных и алгоритмы
> Торп Структуры данных в С++
>
> Вобщем любая нормальная книжка по программированию с этого
> начинается. Прочитай, не пожалеешь. Пару алгоритмов конечно
> тебе и тут расскажут но...

Хм. А эти книжки существуют "не в бумажном представлении"? В смысле чтобы можно было их из инета скачать....

← →
Acidy (2003-07-19 12:31) [5]

Да их читать на экране монитора - так глаза через неделю на лоб полезут .... книги они тока на бумаге книги ...

← →
sergey2 (2003-07-19 12:34) [6]

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

← →
Sergey Masloff (2003-07-19 12:36) [7]

Anatoly Podgoretsky © (19.07.03 12:25)
>А Кнута почто обидел?
Вспылил был неправ ;-)
Но мне кажется Кнут посложнее для восприятия - обычно новички откладывают эту книжку в сторону когда видят что чтобы разбирать примеры из нее для начала неплохо изучить код MIX. И что там нет ничего про иконку в трее и не описан компонент TSuperPuperSort который перетягиваешь на форму и он сортирует тут же все массивы которые находит ;-)
Кстати интересно сильно ли изменилась книга (Кнута) в новой редакции? У меня еще то, 1976 года.

← →
sergey2 (2003-07-19 12:37) [8]

> Acidy © (19.07.03 12:31)
> Да их читать на экране монитора - так глаза через неделю
> на лоб полезут .... книги они тока на бумаге книги ...

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

← →
sergey2 (2003-07-19 12:42) [9]

> Но мне кажется Кнут посложнее для восприятия - обычно новички
> откладывают эту книжку в сторону когда видят что чтобы разбирать
> примеры из нее для начала неплохо изучить код MIX. И что
> там нет ничего про иконку в трее и не описан компонент TSuperPuperSort
> который перетягиваешь на форму и он сортирует тут же все
> массивы которые находит ;-)

Да мне не нужен компонент или еще что-то в этом роде. Хочу знать есть ли алгоритмы позволяющие это делать намного быстрее чем тот что я привел? Если да, то приведите пример.
А насчет %Delphi%\Demos\Threads посмотрю дома есть ли там что-нить стоящее. А щас (на работе) дельфи под рукой нет.

← →
Palladin (2003-07-19 12:48) [10]

Пример: "Быстрая сортировка", есть в Demos\Threads

Но на самом деле скорость выполнения той или иной сортировки зависит от входных данных...

← →
Sergey Masloff (2003-07-19 12:51) [11]

sergey2 (19.07.03 12:28)
>Хм. А эти книжки существуют "не в бумажном представлении"?
Ну уж Керниган-то точно есть. Конкретных адресов конечно не назову - у меня-то все в нормальном виде есть. Но через поисковик найдешь без проблем.

Кстати, на http://www.podgoretsky.com/lang.html вполне можно найти чего-нибудь интересное...

← →
Piroman (2003-07-19 13:44) [12]

> Кстати интересно сильно ли изменилась книга (Кнута) в новой
> редакции? У меня еще то, 1976 года.

Все то же самое. Только бумага белая :) И сокращено чуть-чуть.

← →
хм (2003-07-20 00:02) [13]

>Sergey Masloff (19.07.03 12:19)

А Вирта???

← →
DHDD (2003-07-20 07:03) [14]

> sergey2 (19.07.03 12:08)

QuickSort из демо BP7 + asm
Посмотри в Debugger"е свой код (посчитай кол-во машинных команд),
напиши на asm"е и сравни.

← →
Alex Konshin (2003-07-20 08:55) [15]

Зайди еще и ко мне, на http://home.earthlink.net/~akonshin/index.htm
и взгляни на AVLtree и, особенно советую, на Arrays.
Второй - очень мощное оружие в умелых руках.
Оба очень шустрые.

← →
Alex Konshin (2003-07-20 09:03) [16]

И читай Кнута "Искусство программирования для ЭВМ", том третий "Сортировка и поиск". Книжка толстая и дорогая, но, даже если будешь читать через страницу, то все-равно польза будет.
Оттуда и узнаешь, что QuickSort, который используется везде - далеко не самое лучшее решение, его недостаток в том, что при определенных условиях (точнее, при уже упорядоченном массиве) он работает медленно.

← →
SergP (2003-07-20 10:03) [17]

> DHDD (20.07.03 07:03)
> > sergey2 (19.07.03 12:08)
>
> QuickSort из демо BP7 + asm
> Посмотри в Debugger"е свой код (посчитай кол-во машинных
> команд),
> напиши на asm"е и сравни.

Меня интересует не код, а именно алгоритм...

← →
Palladin (2003-07-20 10:08) [18]

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

враки, пробежит один раз по массиву

> далеко не самое лучшее решение,

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

← →
SergP (2003-07-20 11:03) [19]

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

Вот. Поэтому и хотел бы узнать. может кто-нить пользуется собственными (более эффективными) алгоритмами?

← →
Alex Konshin (2003-07-20 13:10) [20]

2 Palladin: в случае уже упорядоченного массива НЕМОДИФИЦИРОВАННЫЙ алгроритм быстрой сортировки имеет сложность N*N. Поэтому его иногда модифицируют. Насколько я помню, в Delphi он классический.
Ты все-таки почитай Кнута.

← →
Alex Konshin (2003-07-20 13:26) [21]

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

← →
ZZ (2003-07-20 13:35) [22]

Хочу знать есть ли алгоритмы позволяющие это делать намного быстрее чем тот что я привел
Почти любой алгоритм будет быстрее, чем твой :)
А вообще существуют такие сайты, как yandex.ru / google.com.ru и т.д. А поискать можно например "алгоритмы сортировки"

← →
SergP (2003-07-20 13:49) [23]

> Alex Konshin © (20.07.03 13:26)
> Тут еще одно соображение, о котором часто забывают: нужно
> еще учитывать с каким количеством элементов будем иметь
> дело. Если это всего-лишь десять-двадцать, то и незачем
> из пушки по воробьям, достаточно и пузырьком пройтись, если
> же это сотни тысяч, то уж есть за что побороться. При оценке
> сложности говорят о количестве итераций, но для разных алгоритмов
> цена самой итерации может быть очень различной. Вот и может
> получиться, что навороченный алгоритм с хорошей теоретической
> оценкой в итоге приведет к большему количеству машинных
> операций, чем какой-то тупой, но короткий.

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

Кстати смотрел я QuickSort. Насколько я понял - работает он так:
Типа относительно полученого значения Mid масссив должен разбиваться на две части: В одной значения меньше Mid, во второй больше, и дальше рекурсия.

Очень непонравилась мне там одна строчка:
Mid := A[(Lo + Hi) div 2];

ИМХО алгоритм должен работать быстрее если массив будет разбиваться на две приблизительно одинаковые по кол-ву элементов части. Но в этой строчке вычисляется значение, которое не обязательно является средним. Оно также может быть как минимальным , так и максимальным. Все зависит от конкретного случая (исходных данных).

> Palladin © (20.07.03 10:08)
> враки, одно из лучших, при всем разнообразии входных данных.
> существует еще один алгоритм, он побыстрее будет, но ресурсов
> поболее кушает...

А можешь здесь показать этот алгоритм?

← →
Mystic (2003-07-20 15:01) [24]

> Очень непонравилась мне там одна строчка:
> Mid := A[(Lo + Hi) div 2];
>
> ИМХО алгоритм должен работать быстрее если массив будет
> разбиваться на две приблизительно одинаковые по кол-ву элементов
> части. Но в этой строчке вычисляется значение, которое не
> обязательно является средним. Оно также может быть как минимальным
> , так и максимальным. Все зависит от конкретного случая
> (исходных данных).

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

Да, конечно, если сформировать массив таким образом, чтобы не каждом шаге значение Mid := A[(Lo + Hi) div 2]; оказывалось минимальных (максимальным), то вычислительная сложность алгоритма будет N*N (как и у приведенном в первом посте алгоритме). Однако вероятность, что попадется именно такой массив ничтожна.

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

> Alex Konshin © (20.07.03 13:10)

Я неоднократно убеждался в том, что разработчики Dlphi читают Кнута очень внимательно :) Может потому Delphi --- один из самых быстрых компиляторов?

> Если это всего-лишь десять-двадцать, то и незачем из пушки
> по воробьям, достаточно и пузырьком пройтись

В общем-то даже в этом случае лучше вставки... Кстати, иногда быструю сортировка испольуют вместе с сортировкой вставками... Когда число элементов становится меньше 10-20.

← →
Palladin (2003-07-20 16:04) [25]

> А можешь здесь показать этот алгоритм?

в понедельник приведу, сейчас его под рукой нет, впрочем если ты выписывал "Программист", там он приведен...

> Тут еще одно соображение, о котором часто забывают: нужно
> еще учитывать с каким количеством элементов будем иметь
> дело

у меня тоже еще одно соображение, сколько раз мы будем иметь это количество

> Alex Konshin © (20.07.03 13:10)

Кнута я не читал, но могу предположить, что там описывается где и когда использовать те или иные алгоритмы для достижения наивысшей производительности...
К сожалению разработчики Делфи понятия не имели, что будет хранится в основном, по этому справедливо остановили свой выбор на модифицированом алгоритме быстрой сортировки... ведь ты же ее имел ввиду в своем сообщении от (20.07.03 09:03)... обвинив бедных программеров из борланд в некомпетенции...

← →
SergP (2003-07-20 16:21) [26]

> Palladin © (20.07.03 16:04)
>
> в понедельник приведу, сейчас его под рукой нет, впрочем
> если ты выписывал "Программист", там он приведен...

А "Программист" - это что такое? Обычный (бумажный) журнал что-ли? Или нечто в электронном виде? Если первое - то можно ли его выписывать на Украине? И сколько он стоит?
Кстати о чем он? А то я не очень люблю журналы и пр. в которых кроме рекламы харда и софта практически больше ничего нет.

← →
NightAngel (2003-07-20 16:26) [27]

Если интересно... Делал когда-то давно сортировку массива с использованием битов. Нужно было отсортировать очень большое количество целых величин в массиве. В голову пришла такая идея: создается массив переменных типа Byte такого размера, чтобы в нем содержалось столько битов, сколько целых чисел нужно отсортировать. Этот массив обнуляется. Затем просматривается весь список чисел и устанавливаются биты, соответсвующие каждому числу. После чего обрабатывается полученный массив от начала до конца, выдавая числа, соответсвующие каждому установленному биту. Каждый байт в массиве может содержать 8 битов-флагов, так что общее количество требуемых байтов определяется так: количество сортируемых чисел, деленное на 8. Посколько общее количество является кратным 8, не нужно беспокоится об обработке остатка. Бит, соответсвующий числу N из заданного диапазона, находится в байте, индекс которого равен N, деленному на 8. Команда сдвига выполняется быстрее, чем деление, поэтому для выбора необходимого байта я использовал N SHL 3. Внутри этого байта номер искомого бита будет равен остатку от деления N на 8, который получаем, выполняя AND для числа и 7.

← →
Sha (2003-07-20 16:56) [28]

Существует еще модификация, предложенная Singleton. Она ощутимо быстрее.
Отличия от оригинала:
1) без рекурсии
2) если A[Mid]<A[Lo] или A[Mid]>A[Hi], то выполняется обмен;
3) расщепление применяется только в случае, если размер части больше 10-12 (зависит от машины) или если часть первая;
иначе - пузырек.
4) еще кое-что по мелочи (while -> if).

← →
SergP (2003-07-20 17:48) [29]

> 1) без рекурсии

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

> 2) если A[Mid]<A[Lo] или A[Mid]>A[Hi], то выполняется обмен;

Навряд ли это много дает. Если бы как-нить найти действительно среднее значение....

> 3) расщепление применяется только в случае, если размер
> части больше 10-12 (зависит от машины) или если часть первая;
> иначе - пузырек.

Пузырек - это BubbleSort? Если так то лучше SelectionSort, он в любом случае быстрее BubbleSort, даже для небольших масивов.

← →
Sha (2003-07-20 19:45) [30]

2 SergP © (20.07.03 17:48) Держи:
// Richard C. Singleton, alg.347, Comm. ACM 12 (Mar.1969), p.185 procedure Singleton(var a: TMorf; lp, rp: integer); // By Singleton var // Modified by A. Sharahov t, tt: TSkeletonRecord; // Temp elements for CompareSkeleton and exchange l, r: integer; // Current left and right positions p: integer; // Number of saved parts llim, rlim: array[1..16] of integer; // Left and right limits of parts lp0: integer; // Left limit of first part mp : integer; // Median of current part lpx, mpx: integer; // Temp positions in current part begin; lp0:=lp; p:=1; llim[1]:=lp; rlim[1]:=rp; // Prepare for first loop repeat; lp:=llim[p]; rp:=rlim[p]; dec(p); // Restore info about part while (lp+9<rp) or ((lp=lp0) and (lp<rp)) do begin;// Part is big or first mp:=(lp+rp) shr 1; // Sort a[lp],a[mp],a[rp] if CompareSkeleton(@a[mp],@a[lp])<0 then begin; lpx:=mp; mpx:=lp; end else begin; lpx:=lp; mpx:=mp; end; // Exchange to get a[lp]<=a[mp]<=a[rp] and t=a[mp] if CompareSkeleton(@a[rp],@a[mpx])<0 then if CompareSkeleton(@a[rp],@a[lpx])<0 then begin; if lpx=lp then begin; t:=a[lp]; a[lp]:=a[rp]; a[rp]:=a[mp]; a[mp]:=t; end else begin; t:=a[lp]; a[lp]:=a[rp]; a[rp]:=t; t:=a[mp]; end; end else begin; if lpx=lp then begin; t:=a[rp]; a[rp]:=a[mp]; a[mp]:=t; end else begin; t:=a[rp]; a[rp]:=a[lp]; a[lp]:=a[mp]; a[mp]:=t; end; end else begin; if lpx=lp then begin; t:=a[mp]; end // We want t=a[mp] else begin; t:=a[lp]; a[lp]:=a[mp]; a[mp]:=t; end; end; l:=succ(lp); while CompareSkeleton(@a[l],@t)<0 do inc(l);// Find transposition r:=pred(rp); while CompareSkeleton(@t,@a[r])<0 do dec(r);// .... a[l]>=t>=a[r] while l<r do begin; // If part is not over tt:=a[l]; a[l]:=a[r]; a[r]:=tt; // Exchange a[l] with a[r] inc(l); while CompareSkeleton(@a[l],@t)<0 do inc(l); // Find next transposition dec(r); while CompareSkeleton(@t,@a[r])<0 do dec(r); // ......... a[l]>=t>=a[r] end; inc(p); // Save info about greatest part and define limits of current one if r-lp>rp-l then begin; llim[p]:=lp; rlim[p]:=r; lp:=l; end else begin; llim[p]:=l; rlim[p]:=rp; rp:=r; end; end; while lp<rp do begin; // Sort small part, first part already sorted l:=lp; inc(lp); // Change limit of unsorted part if CompareSkeleton(@a[lp],@a[l])<0 then begin; // If transposition found: a[lp]<a[lp-1] t:=a[lp]; // Find place for t=a[lp] repeat; a[succ(l)]:=a[l]; dec(l); // Shift one element right until not (CompareSkeleton(@t,@a[l])<0); // Note: any element in prev part is less a[succ(l)]:=t; // Place found, store t end; end; until p<=0; // Until no part end;

← →
Sha (2003-07-20 19:51) [31]

PS
Размера массивов llim, rlim хватит для сортировки 2^16 элементов, если у тебя больше - ставь 32 (хватит на все случаи)

← →
AbrosimovA (2003-07-21 08:59) [32]

var MainForm: TMainForm; D: TStringList; ..... //Сортировка TStringList по возрастанию(метод "Всплывающих пузырьков") procedure Sort; var I, J, Min : integer; S: string; begin for I:=1 to D.Count do A[I]:=D.Strings[I-1]; for I:=1 to D.Count-1 do begin Min := I; for J:=I+1 to D.Count do if A[J]<A[Min] then Min := J; B := A[Min]; A[Min] :=A[I]; A[I] := B; end; for I:=1 to D.Count do D.Strings[I-1]:=A[I]; end;

← →
SergP (2003-07-21 09:34) [33]

← →
Sha (2003-07-21 10:56) [34]

>SergP © (20.07.03 17:48)

>> 1) без рекурсии
>Приведи пример.

Пример см Sha © (20.07.03 19:45)

>> 2) если A[Mid]<A[Lo] или A[Mid]>A[Hi], то выполняется обмен;
>Навряд ли это много дает. Если бы как-нить найти действительно среднее значение....

Дает много. Еще лучше оценивать медиану по 5 элементам. Но и это очень неплохо.

>> 3) расщепление применяется только в случае, если размер
>> части больше 10-12 (зависит от машины) или если часть первая;
>> иначе - пузырек.
>Пузырек - это BubbleSort?

Пузырек - это челнок (Shuttle). Термин у нас как-то не прижился, хотя суть отражает лучше.

← →
Palladin (2003-07-21 11:40) [35]

← →
NickBat (2003-07-21 12:16) [36]

А ведь автор ветки спросил как отсортировать данные из БАЗЫ?

И никто не сказал ему о славной команде ORDER BY

0:))

← →
Palladin (2003-07-21 12:33) [37]

← →
sergey2.1 (2003-07-21 12:34) [38]

> NickBat © (21.07.03 12:16)
> А ведь автор ветки спросил как отсортировать данные из БАЗЫ?
>
> И никто не сказал ему о славной команде ORDER BY
>
> 0:))

Да нет. Я хотел узнать именно об алгоритмах сортировки. (массивы, базы и пр.)
В смысле меня не интересуют готовые возможности. Интересуют именно алгоритмы.

← →
Sha2.71828 (2003-07-21 13:37) [39]

SORTING AND SORT SYSTEMS by Harold Lorin
есть перевод: Г.Лорин Сортировка и системы сортировки,Наука,М,1983

← →
blackman (2003-07-21 13:40) [40]

Какие проблемы ?
Структуры и алгоритмы. Библиотека. Алгоритмы внутренней сортировки.Методы сортировки. Рекурсия.Ссылки и указатели. Стек. Деревья.Поиск.Хеширование.Слияние.Внешняя сортировка.
http://blackman.wp-club.net/cncat/jump.php?356

← →
Sha (2003-07-21 14:14) [41]

← →
Sha (2003-07-21 14:39) [42]

← →
blackman (2003-07-21 14:48) [43]

Звиняйте, бананьев не припасли...
А если посмотреть внимательно, то это только ссылка на сайт
http://www.structur.h1.ru/biblio.htm
из моего каталога
http://blackman.wp-club.net/cncat/

← →
Alex Konshin (2003-07-22 06:45) [44]

Меня рассмешила статья про AVL-деревья (так сказать, профессиональный интерес), где говориться, что "удаление очень сложное, поэтому мы его рассматривать не будем".
На самом деле удаление ненамного сложнее, и отсутствие удаления из AVL скорее всего объясняется отсутствием его в книге Кнута, из которой все всё передирают.
Ссылка на алгоритм удаления из AVL-дерева в стиле Кнута:
www.msu.edu/user/pfaffben/avl/algorithm.ps
Про AVL-деревья поиcка:
http://www.msu.edu/~pfaffben/avl/

← →
iNew (2003-07-22 07:41) [45]

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

← →
Sha (2003-07-22 09:41) [46]

iNew © (22.07.03 07:41)
Если "метод бинарного дерева" - это TreeSort3, Robert W. Floyd alg.245 Comm. ACM 7 (Dec.1964), p.701,
то Singleton быстрее.

Алгоритм сортировки масива. Найти похожие ветки