Написать программу, которая упорядочивает вещественный массив из 500 элементов методом быстрой сортировки.

Под сортировкой понимается упорядочивание в соответствии с каким-либо критерием – чаще всего по возрастанию или убыванию. Существует множество методов сортировки, различающихся по поведению, быстродействию, требуемому объему памяти, а также ограничениям, накладываемым на исходные данные. Одним из наиболее простых методов является сортировка выбором. Он характеризуется квадратичной зависимостью времени сортировки t от количества элементов N:

.

Здесь a и b – константы, зависящие от программной реализации алгоритма. Иными словами, для сортировки массив требуется просмотреть порядка N раз. Существуют алгоритмы и с лучшими характеристиками, самый известный из которых предложен Ч.Э.Хоаром и называется алгоритмом быстрой сортировки. Для него зависимость имеет вид

Рассмотрим этот алгоритм. Его идея состоит в следующем. К массиву применяется так называемая процедура разделения относительно среднего элемента. Вообще-то в качестве «среднего» можно взять любой элемент массива, но для наглядности будет выбираться элемент примерно из середины интервала. Процедура разделения делит массив на две части. В левую помещаются элементы, меньшие элемента, выбранного в качестве среднего, а в правую – большие. Это достигается путем просмотра массива попеременно с обоих концов, причем каждый элемент сравнивается с выбранным средним и элементы, находящиеся в «неподходящей» части, меняются местами. После завершения процедуры разделения средний элемент оказывается на своем окончательном месте, т.е. его «судьба» определена. Далее процедуру разделения необходимо повторить отдельно для левой и правой частей: в каждой части выбирается среднее, относительно которого она делится на две, и т.д. Понятно, что одновременно процедура не может заниматься и левой, и правой частями, поэтому необходимо каким-то образом запомнить на обработку одной из двух частей (например, правой) и заняться оставшейся частью (например, левой). Так продолжается до тех пор, пока не окажется, что очередная обрабатываемая часть содержит ровно один элемент. Тогда нужно вернуться к последнему из необработанных запросов, применить к нему все ту же процедуру разделения и т.д. В конце концов массив будет полностью упорядочен. Для хранения границ еще не упорядоченных частей массива более всего подходит структура данных, называемая стеком. Можно представить себе длинный туннель, в который въезжает вереница машин. Ширина туннеля позволяет ехать только в один ряд. Если окажется, что выезд из туннеля закрыт и придется ехать обратно задним ходом, машина, ехавшая первой, сможет покинуть туннель в самую последнюю очередь. Это и есть стек, принцип организации которого – «первым пришел, последним ушел».

В приведенной программе, стек реализуется в виде двух массивов stackl и stackr, а также переменной sp, используемой как «указатель» на вершину стека (она хранит номер последнего заполненного элемента массива).

 

 

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

 

{***************************************************}

{Программа: QUICK_SORT. }

{Программист: Иванов И.И. }

{Дата выполнения: 10 апреля 2006 г. }

{***************************************************}

Program QUICK_SORT;

Const n = 500;

Var arr: array [1.. n] of real;

middle: real; {средний элемент}

temp: real; {буферная переменная для обмена двух значений в массиве}

sp: integer; {указатель на вершину стека}

i, j: integer;

stackl, stackr: array [1.. n] of integer; {стеки границ фрагментов}

left, right: integer; {границы сортируемого фрагмента}

Begin

Writeln(‘Ввести элементы массива’);

For i: =1 to n do

Begin

Writeln(‘arr[‘, i: 2, ‘]=’);

Read(arr[i])

End;

sp: = 1; { 1 }

stackl[1]: = 1; { 1 }

stackr[1]: = n; { 1 }

while sp > 0 do begin { 2 }

left: = stackl[sp]; { 3 }

right: = stackr[sp]; { 4 }

dec(sp); { 5 }

while left < right do begin { 6 }

i: = left; { 7 }

j: = right; { 7 }

middle: = arr[(left + right) div 2]; { 8 }

while i < j do begin { 9 }

while arr[i] < middle do inc(i); { 10}

while middle < arr[j] do dec(j); { 11}

if i < = j then begin

temp: = arr[i];

arr[i]: = arr[j];

arr[j]: = temp;

inc(i);

dec(j)

end

end;

if i < right then begin { 12}

inc(sp);

stackl[sp]: = i;

stackr[sp]: = right

end;

right: = j { 13}

end

end;

Writeln(‘Упорядоченный массив: ’);

For I: = 1 to n do write(‘arr[‘, i: 2, ‘]=’, arr[i]: 8: 2);

writeln

End. { QUICK_SORT }

 

На каждом шаге сортируется один фрагмент массива. Левая граница фрагмента хранится в переменной left, а правая – в переменной right. Сначала фрагмент устанавливается размером с массив целиком (операторы 1). В операторе 8 выбирается «средний» элемент фрагмента. Для продвижения по массиву слева направо в цикле 10 используется переменная I, справа налево – переменная j (в цикле 11). Их начальные значения устанавливаются в операторе 7. После того как оба счетчика «сойдутся» где-то в средней части массива, происходит выход цикла 9 на оператор 12, в котором заносятся в стек границы правой части фрагмента. В операторе 13 устанавливаются новые границы левой части для сортировки на следующем шаге. Если сортируемый фрагмент уже настолько мал, что сортировать его не требуется, происходит выход из цикла 6, после чего выполняется выборка из стека границ еще не отсортированного фрагмента (операторы 3 и 4). Если стек пуст, происходит выход из главного цикла 2. Массив отсортирован.

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

 

Примечание.

⇐ Предыдущая12345

Поделиться: