Алгоритмы сортировки в Delphi

 
   Этой сортировкой можно сортировать  целые неотрицательные числа большого диапазона. Идея состоит в следующем: отсортировать числа по младшему разряду, потом устойчивой сортировкой сортируем по второму, третьему, и так до старшего разряда. В качестве устойчивой сортировки можно выбрать сортировку подсчетом, в виду малого времени работы. Реализация такова:  
 
Program RadixSort;  
Var A,B : array[1..1000] of word;  
N,i : integer;  
t : longint;  
Procedure Sort; {сортировка подсчетом}  
Var C : array[0..9] of integer;  
j : integer;  
Begin  
For j:=0 to 9 do  
C[j]:=0;  
For j:=1 to N do  
C[(A[j] mod (t*10)) div t]:= C[(A[j] mod (t*10)) div t]+1;  
For j:=1 to 9 do  
C[j]:=C[j-1]+C[j];  
For j:=N downto 1 do  
begin  
B[C[(A[j] mod (t*10)) div t]]:=A[j];  
C[(A[j] mod (t*10)) div t] := C[(A[j] mod (t*10)) div t]-1;  
end;  
End;  
Begin  
{Определение размера массива A (N) и его заполнение}  
…  
{сортировка данных}  
t:=1;  
for i:=1 to 5 do  
begin  
Sort;  
A:=B;  
t:= t*10;  
end;  
{Вывод массива A}  
…  
End.  
 
   Так как сортировка подсчетом вызывается константное число раз, то время работы всей сортировки есть O(n). Заметим, что таким способом можно сортировать не только числа, но и строки, если же использовать сортировку слиянием в качестве устойчивой, то можно сортировать объекты по нескольким полям. 
 
   Теперь вы владеете достаточным арсеналом, чтобы сортировать все что угодно и как угодно. Помните, что выбор нужной вам сортировки зависит от того, какие данные вы будете сортировать и где вы их будете сортировать.  
   P.S. Все программы рабочие — если, конечно, вам не лень будет заменить три точки на код ввода и вывода массивов :-). 

лгоритмы  Сортировки. Часть 1

 
Все из существующих ныне способов сортировки отличаются друг от друга по скорости выполнения, понятности и длине кода, по красоте решения. Зачастую в код  уже разработанного алгоритма вносятся какие-либо изменения и так возникает множество решений, некоторые и с которых мы и попробуем сейчас рассмотреть.  
 
Однако, следует отметить что изучение алгоритмов совсем не лёгкая задача, здесь требуется внимательное рассмотрение каждой строчки. Конечно если Вы воспользуетесь кнопками Ctrl+C и Ctrl+V Ваша программа не станет хуже работать, но на мой взгляд, нет ничего хуже когда программист сам до конца не понимает, как работает его программа.  
 
Итак, начнём.

Сортировка выбором

И начнём мы с  сортировки выбором. Хотя этот алгоритм и не является самым быстрым, но я решил начать с него потому что, на мой взгляд он наиболее прост для понимания. Суть алгоритма состоит в том, что бы в исходном массиве найти наименьший элемент, а затем поменять местами первый элемент в списке с найденным. После того, находиться наименьший их оставшихся и меняется со вторым элементом. И так до тех пор пока весь список не будет отсортирован.  
Таким образом понадобиться N+(N-1)+(N-2)+...+1 или N*N проходов чтобы отсортировать список.

 
Переменными min и mах можно ограничить область списка в которой, будет  выполнена сортировка. Что бы отсортировать  весь массив необходимо записать следующее

Сортировка вставкой

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

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

Пузырьковая сортировка

Чаще  всего используется для сортировки частично упорядоченных списков, так как именно для них скорость выполнения максимальна и может равняться O(N), где N количество элементов массива, а O время одного прохода через цикл. Этот алгоритм в исходном списке ищет пары цифр, которые следуют не по порядку и затем меняет их местами.Процесс повторяется до тех пор пока весь список не будет отсортированным. На рисунке изображен пример сортировки данным методом.  

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

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

Стоит также  заметить, что такой сортировкой  лучше всего пользоваться для  упорядочевания массивов элементы в  которых следуют абсолютно, случайно. В то время как, если список практически упорядочен, разумнее будет использовать пузырьковую сортировку. К тому же если список достаточно длинный, то алгоритм вызовет глубокую рекурсию и возможно переполнение стёка и как следствие зависание или аварийный выход программы.

Сортировка методом Шелла.

Ещё один метод  сортировки - это сортировка методом  Шелла.Основная идея этого алгоритма  заключается в том, чтобы в  начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие  друг от друга элементы. Как видно, интервал между сравниваемыми элементами постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

 
Заключение.

В данной статье была предпринята попытка объяснить  наиболее часто применяемые алгоритмы  сортировки. Однако рассказать о всех аспектах реализации различных алгоритмов в одной статье довольно сложно, и статья получается перенасыщенная информацией, поэтому я решил разбить её на две части и сейчас вторая уже готовиться к выходу. В ней планируется рассказать о более специфических алгоритмах, сортировке не только цифр, но и слов, как русского так и английского языка, а также об обратном процессе сортировки - перемешивания.  
 
Удачи!  
 
P.S. Замечания, пожелания и дополнения к этой статье просим оставлять на форуме.  

Цель: изучение алгоритма быстрой сортировки и ее модификаций.

На этом занятии  мы изучим алгоритм быстрой сортировки, который, пожалуй, используется более  часто, чем любой другой. Основа алгоритма  была разработана в 1960 году (C.A.R.Hoare) и с тех пор внимательно  изучалась многими людьми. Быстрая сортировка особенно популярна ввиду легкости ее реализации; это довольно хороший алгоритм общего назначения, который хорошо работает во многих ситуациях, и использует при этом меньше ресурсов, чем другие алгоритмы.

Основные достоинства этого алгоритма состоят в том, что он точечный (использует лишь небольшой дополнительный стек), в среднем требует только около N log N операций для того, чтобы отсортировать N элементов, и имеет экстремально короткий внутренний цикл. Недостатки алгоритма состоят в том, что он рекурсивен (реализация очень затруднена когда рекурсия недоступна), в худшем случае он требует N2 операций, кроме того он очень "хрупок": небольшая ошибка в реализации, которая легко может пройти незамеченной, мо жет привести к тому, что алгоритм будет работать очень плохо на некоторых файлах.

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

Улучшить алгоритм быстрой сортировки является большим искушением: более быстрый алгоритм сортировки - это своеобразная "мышеловка" для программистов. Почти с того момента, как Oia?a впервые опубликовал свой алгоритм, в литературе стали появляться "улучшен ные" версии этого алгоритма. Было опробовано и проанализировано множество идей, но все равно очень просто обмануться, поскольку алгоритм настолько хорошо сбалансирован, что результатом улучшения в одной его части может стать более сильное ухудшение в друг ой его части. Мы изучим в некоторых деталях три модификации этого алгоритма, которые дают ему существенное улучшение.

Хорошо же отлаженная версия быстрой сортировки скорее всего  будет работать гораздо быстрее, чем любой другой алгоритм. Однако стоит еще раз напомнить, что  алгоритм очень хрупок и любое его изменение может привести к нежелательным и неожиданным эффектам дл я некоторых входных данных.

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