Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Быстрая сортировка.
|
|
При этом виде сортировке массив разбивается на две части, а затем рекурсивно вызывает сама себя для их сортировки. Притом элементы первой части меньше любого элемента второй части.
Рассмотрим данный вид сортировке на примере:
Если алгоритм вызывается для списка, который содержит нуль или один элемент, то подписок уже отсортирован и процедура заканчивается, в противном случае выбирается один элемент, относительно которого список разбивается на две части, в первый подписок идут элементы меньше выбранного, во второй больше. И затем, как уже было сказано, она рекурсивно вызывает сама себя для сортировки обои подсписков.
| Листинг 5.Быстрая сортировка |
| procedureQuickSort(vara: arrayof integer; min, max: Integer); Var i, j, mid, tmp: integer; Begin ifmin< max then begin mid: =A[min]; i: =min-1; j: =max+1; whilei< j do begin repeat i: =i+1; untilA[i]> =mid; repeat j: =j-1; untilA[j]< =mid; ifi< j then begin tmp: =A[i]; A[i]: =A[j]; A[j]: =tmp; end; end; QuickSort(a, min, j); QuickSort(a, j+1, max); end; end; |
Стоит также заметить, что такой сортировкой лучше всего пользоваться для упорядочевания массивов элементы в которых следуют абсолютно, случайно. В то время как, если список практически упорядочен, разумнее будет использовать пузырьковую сортировку. К тому же если список достаточно длинный, то алгоритм вызовет глубокую рекурсию и возможно переполнение стёка и как следствие зависание или аварийный выход программы.
Сортировка методом Шелла.
Ещё один метод сортировки - это сортировка методом Шелла.Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).
| Листинг 6.Сортировка методом Шелла |
| procedureTForm1.SortShell(vara: arrayof real; N: Integer); var h: Variant; c: Boolean; g: Integer; i: Integer; j: Integer; tmp: Real; begin h: =1; g: =0; repeat h: =3*h+1 until(h> =n); if(h> n) then begin h: = h/3; g: =h; end; n: =n-1; repeat i: =g; repeat j: =i-g; c: =True; repeat ifa[j]< =a[j+g] then begin c: =False; end else begin Tmp: =a[j]; a[j]: =a[j+g]; a[j+g]: =Tmp; end; j: =j-1 untilnot((j> =0)and(C)); i: =i+1 untilnot(i< =n); h: =g; h: =h/3; g: =h; untilnot(g> 0); end; |
Заключение.
В данной статье была предпринята попытка объяснить наиболее часто применяемые алгоритмы сортировки. Однако рассказать о всех аспектах реализации различных алгоритмов в одной статье довольно сложно, и статья получается перенасыщенная информацией, поэтому я решил разбить её на две части и сейчас вторая уже готовиться к выходу. В ней планируется рассказать о более специфических алгоритмах, сортировке не только цифр, но и слов, как русского так и английского языка, а также об обратном процессе сортировки - перемешивания.