Быстрая сортировка - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Быстрая сортировка (http://forum.oszone.net/showthread.php?t=30878)

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

Пример кода:

Код:

procedure swap(var a, b : integer);

var

 *c : integer;

begin

 *c := a;

 *a := b;

 *b := c;

end; *{Это просто процедурка, которая меняет местами значения A и B}



procedure sort(l, r : integer);

var

 *Y, j, x : integer;

begin

 *Y := l;

 *j := r; {с помощью указателей Y и J мы будем &quot;двигаться по массиву&quot;}

 *x := a[(l + r) div 2]; {выбрали произвольный элемент. Например из серединки}

 *repeat

 * *while (a[Y] &lt; x) do inc(Y); {Двигаем левый указатель до близжайшего элемента, большего X}

 * *while (a[j] &gt; x) do dec(j); {Двигаем правый указатель до близжайшего элемента, меньшего X}

 * *if Y &lt;= j then begin

 * * *swap(a[Y], a[j]);

 * * *inc(Y);

 * * *dec(j);

 * *end; {поменяли элементы местами, сдвинули указатели}

 *until Y &gt; j;

 *if Y &lt; r then sort(Y, r);

 *if j &gt; l then sort(l, j);

end;

As is (я не несу ответственности за последствия получения вами данного кода)

Праверьте ещё раз, правильно ли работает... Если что - стучите :)

[Гневные ругательства в адрес BigMac-а]
Кстати говоря... Паскалевское обращение к элементу массива вида A[W], где вместо "W" стоит "I" твой форум распознал как открытие тэга... Сделай примочку, которая в тэге CODE игнорирует все другие тэги...
[/Гневные ругательства в адрес BigMac-а]

(Отредактировал(а) noname00.pas - 10:06 8-01-2002)

noname00.pas
Понял..... он распознал его как косой шрифт.......гляну..... :)

noname00.pas
Вау! Круто! А на сколько быстрее она работает. А то зачем ее писать если я и пузырьком могу отсортить :)

BluesBrother
В худшем случае (при специально подобранных данных) она работает за O(N*N) операций. Но вероятность выпадения именно таких данных на достаточно больших массивах ничтожна мала, поэтому в общем случае кол-во операций можно оценивать как O(N*log(N)). В среднем этот алгоритм работает быстрее, чем HeapSort, Шелл и прочие алгоритмы сложности O(N*log(N))

(Отредактировал(а) noname00.pas - 11:46 8-01-2002)

noname00.pas :up:

Цитата:

Кстати говоря... Паскалевское обращение к элементу массива вида A[W], где вместо "W" стоит "I" твой форум распознал как открытие тэга... Сделай примочку, которая в тэге CODE игнорирует все другие тэги...

Лень. Если нужно поставить именно [[, то пиши квадратную скобку дважды [[[[. []как ни странно, но это написано не жирным шрифтом[]

ivank
А если програмка уже написана, а я её через буффер обмена сюда вставляю? :Р

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

ivank
Проще один раз исправить скрипт, чем каждый раз открывать блокнот. :)

std::sort :>
Кнута почитайте-с, - не знаснёте - много нового узнаете

std::sort это и есть быстрая сортировка (аналог сишного qsort, только на столь нелюбимых кем-то шаблонах :)), а он рассказывал про то, как это работает.

Цитата:

Кнута почитайте-с, - не знаснёте - много нового узнаете

Если бы не MIX, то была бы прекрасная книга -- а в асм несуществующей машины разбираться трудно. Хотя можно построить её мулятор...

а на фига разбираться? у тея есть алгоритм. описание того, как это должно работать и всё. Да и асм там не сложной, у iP2 И старше гораздо сложнее

Обычно мне хватает моего КЛР (Кормен&Лейзерсон&Ривест).