Быстрая пошаговая сортировка...

← →
ArtemESC © (2006-05-14 15:07) [0]

Помогите, пожалуйста, разобраться, что не работает в следующей
реализации сортировки - очень нужно разобраться:

function QuickSort(var Dates: TDates; L, R: Integer): integer; var Index : Integer; i : Integer; Number: Integer; begin If (R - L) < 2 then If CmpDate(Dates[R], Dates[L]) then Swap(Dates, R, L) else begin Index := (R - L) div 2 + L; i := L; While (i < Index) do begin If CmpDate(Dates[i], Dates[Index]) then begin Swap(Dates, i, Index); Index := i; end else Inc(i); end; i := R; While (i > Index) do begin If CmpDate(Dates[Index], Dates[i]) then begin Swap(Dates, i, Index); Index := i; end else Dec(i); end; QuickSort := Index; end; end;

procedure Quick_Sort; var S : TStack; m, n : integer; Index: integer; begin S := nil; Push(S, 1); Push(S, len); While not IsFree(S) do begin Pop(S, m); Pop(S, n); Index := QuickSort(Dates, n, m); If (m - n) >= 2 then begin Push(S, Index + 1); Push(S, m); Push(S, n); Push(S, Index - 1); end; PrintDates; end; PrintDates; wait; end;

← →
TUser © (2006-05-14 16:23) [1]

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

Результат функции может быть не определен. Варнинги читать надо.

← →
ArtemESC © (2006-05-14 16:55) [2]

TUser © (14.05.06 16:23) [1]
Мне вообще для BorlandPascal"я надо...
Алгоритм состоит в следующим, берем
опорное значение (например, среднее) и переставлям
остальные значения так, чтобы слева стояли были меньше, справа больше опорного значения, потом относительно этого опорного значения рассматриваем два массива - один от начала исходного массива до опорного значения, другой от опорного значения до конца массива - и проделываем тоже самое с каждым из них, и.т.д - забыл сказать, что сортировка должна быть не рекурсивной - потому использую стек...

← →
MBo © (2006-05-14 17:09) [3]

http://it.mmf.rsu.ru/forum/viewtopic.php?t=28&sid=81bd1177fe06b994f537de39199b3195

← →
TUser © (2006-05-14 18:13) [4]

Ну, Ок. Быстрая, так быстрая. Вот этот код, например, находит какую-то позицию в массиве и меняеет ее местами с "опорной". А массив на две части вовсе не обязан делится.

While (i < Index) do
begin
If CmpDate(Dates[i], Dates[Index]) then
begin
Swap(Dates, i, Index);
Index := i;
end else Inc(i);
end;

Вот код от Борланда. Он работает.
procedure QuickSort(SortList: PPointerList; L, R: Integer; SCompare: TListSortCompare); var I, J: Integer; P, T: Pointer; begin repeat I := L; J := R; P := SortList^[(L + R) shr 1]; repeat while SCompare(SortList^[I], P) < 0 do Inc(I); while SCompare(SortList^[J], P) > 0 do Dec(J); if I <= J then begin T := SortList^[I]; SortList^[I] := SortList^[J]; SortList^[J] := T; Inc(I); Dec(J); end; until I > J; if L < J then QuickSort(SortList, L, J, SCompare); L := I; until I >= R; end;

← →
ArtemESC © (2006-05-14 18:59) [5]

TUser © (14.05.06 18:13) [4]
Ну так здесь с рекурсией, а мне без надо...

← →
Cash © (2006-05-14 20:45) [6]

ArtemESC © (14.05.06 16:55) [2]:
Судя по изложенному - это не быстрая тебе нужна.
Тебе видать прамидальная (HeapSort) нужна. А... да ну его к лешему,
ходи на http://algolist.manual.ru, там тебе все покажут!!!

ЗЫ: Heap - это тоже "быстрая" сортировка! :о)

← →
ArtemESC © (2006-05-14 21:23) [7]

Cash © (14.05.06 20:45) [6]
Не прамидальная, но "быстрая" - именно такое название...

← →
MBo © (2006-05-14 21:27) [8]

>Ну так здесь с рекурсией, а мне без надо
А по ссылке не сходил, что ли?

← →
ArtemESC © (2006-05-14 21:29) [9]

MBo © (14.05.06 21:27) [8]
Сходил...

← →
begin...end © (2006-05-14 21:44) [10]

Удалено модератором

ArtemESC © (14.05.06 21:29) [9]:
Слушай, ты давай определяйся там! А то надо одну, а описание от другой
даеш!!!
Там, в описании метода, хоть понятие медианы вскакивает?

А вааще, быстрых сортировок много, но QuickSort - одна, что именно тебе
надо???

> MBo

Интересный факт.
Всю жизнь считал, что нерекурсивная быстрая сортировка быстрее рекурсивной.
Не так давно обнаружил, что на х86 это не так.

>Sha © (15.05.06 13:58) [13]
Видимо, это неоднозначный вопрос. Наверно, от размера данных и локальности обращения к памяти зависит?

> MBo

1. Массив целых чисел - максимально плотные данные.
2. У быстрой сортировки степень локализации обращений к памяти крайне
высокая - это надо специально стараться, чтобы ее испортить :)
3. От размера данных практически ничего не зависит, т.к. по существу вся
работа идет с двумя страницами памяти.

Итог:
Рекурсивный алгоритм выигрывает.

Быстрая пошаговая сортировка... Найти похожие ветки