Отправляет email-рассылки с помощью сервиса Sendsay

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

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 977 RSS
←   Июнь 2005   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
09.06.2005
12:12:18
13:22:33
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Открыта: 01-08-2004

Автор
ferrik

Статистика

977 подписчиков
0 за неделю
←   Все выпуски   →

Разбор классических алгоритмов и олимпиадных задач. Быстрая сортировка.


Информационный Канал Subscribe.Ru
QuickSort
Быстрая сортировка(QuickSort) - это рекурсивный алгоритм, который использует подход "Разделяй и властвуй". Список, который нужно отсортировать делится пополам, и для каждой из частей, процедура вызывает себя рекурсивно.
 Итак, рассмотрим. следующую схему сравнений/обменов. Имеются два указателя i и j, причем вначале i = l, a j = N. Сравним Ki : Kj, и если обмен не требуется, то уменьшим j на единицу и повторим этот процесс. После первого обмена увеличим i на единицу и будем продолжать сравнения, увеличивая i, пока не произойдет еще один обмен. Тогда опять уменьшим j и т. д.; будем "сжигать свечку с обоих концов", пока не станет i = j. Посмотрим, например, что произойдет с нашим файлом из шестнадцати чисел:
Дано: 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703 -j
1-й обмен 154 087 512 061 908 170 897 275 653 426 503 509 612 677 765 703 +i
2-й обмен 154 087 503 061 908 170 897 275 653 426 512 509 612 677 765 703 -j
3-й обмен 154 087 426 061 908 170 897 275 653 503 512 509 612 677 765 703 +i
4-й обмен 154 087 426 061 503 170 897 275 653 908 512 509 612 677 765 703 -j
5-й обмен 154 087 426 061 275 170 897 503 653 908 512 509 612 677 765 703 +i
6-й обмен 154 087 426 061 275 170 503 897 653 908 512 509 612 677 765 703 -j
 (Чтобы выявить состояние i и j, ключи Ki и Kj напечатаны жирным шрифтом.) Заметим, что в каждом сравнении этого примера участвует ключ 503; вообще в каждом сравнении будет участвовать исходный ключ K1 потому что он будет продолжать обмениваться местами с другими ключами каждый раз, когда мы переключаем направление. . моменту, когда i = j, исходная запись R1 займет свою окончательную позицию, потому что, как нетрудно видеть, слева от нее не будет больших ключей, а справа-меньших. Исходный файл окажется разделен таким образом, что первоначальная задача сведется к двум более простым: сортировке файла R1 : : : Ri-1 и (независимо) сортировке файла Ri+1 : : : RN. К каждому из этих подфайлов можно применить тот же самый метод. (Д. Кнут)
Вот его реализация на Delphi:

 Быстрая сортировка самый рапространённый алгоритм. Его вы можете найти в таких классах Delphi как TList и TStringList. Также посмотрите интересный пример на сортировки: Demos-->Threads-->.
У этого алгоритма много вариантов оптимизации. Попробуйте что-нибудь реализовать.

Замеры, мс
Кол-во 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536
Bubble 0.0025 0.0085 0.0323 0.1293 0.5214 2.0936 8.3018 32.793 130.88 532.87 2151.6 8685.4 47761
Shaker 0.0025 0.0080 0.0282 0.1092 0.4288 1.6955 6.7565 26.718 106.15 426.11 1716.6 6896.2 30936
Selection 0.0024 0.0070 0.0222 0.0772 0.2831 1.0826 4.1964 16.536 65.508 263.50 1054.2 4213.4 19436
Insertion 0.0012 0.0034 0.0114 0.0416 0.1588 0.6169 2.4413 9.7193 38.740 154.76 618.77 2474.2 13597
InsertionO 0.0013 0.0033 0.0099 0.0338 0.1238 0.4723 1.8481 7.3261 29.112 116.23 463.99 1855.5 11466
QuickSort 0.0027 0.0062 0.0137 0.0300 0.0650 0.1400 0.3000 0.6400 1.3600 2.9000 6.1400 13.000 28.100
Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора 		Подписан адрес:
Код этой рассылки: comp.soft.prog.fprogram 		Отписаться
Вспомнить пароль
В избранное