Алгоритм быстрой сортировки.

Метод "быстрой" сортировки, предложенный К.Хоаром (C. Hoare), основан на разделении массива на два непустых непересекающихся подмножества элементов. При этом в одной части массива должны оказаться все элементы, которые не превосходят по значению некоторый предварительно выбранный элемент массива, а в другой части - все элементы, не меньшие его. Аналогично следует поступить с каждой из полученных групп (при этом элемент для разделения можно выбирать просто из "середины" группы). На определенном этапе массив окажется полностью отсортированным.

В подавляющем большинстве реальных случаев использование "быстрой" сортировки дает лучшие результаты по времени, чем все прочие методы.

Алгоритм разделения массива на две части показан на следующей блок-схеме. Исходными данными для этого алгоритма являются величины Left — номер элемента, который считается левой границей массива и Right — номер элемента, который считается правой границей массива. Они нужны для того, чтобы тот же алгоритм мог обработать как весь массив целиком, так и его части. Имя массива — m. В качестве разделяющего элемента выбран элемент из середины массива.

Удаление элементов из массива и вставка элементов в массив.

К сожалению, Turbo Pascal не имеет средств для создания массивов переменной длины. Длина массива указывается на этапе создания программы при описании массива. В ходе выполнения программы. Длина массива меняться не может. Поэтому при необходимости работы с массивами переменной длины описывают массив заведомо большего размера. Вместе с тем описывают целую переменную, смысл которой — фактическая длине массива, то есть размер используемой части массива. Хотя этот путь и нерационален, мы будем использовать его для работы с массивами переменной длины, чтобы отработать алгоритмы удаления и вставки элементов.

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

…………………………var mas: array[1..100] of real; {Описание массива} i: integer; {параметр цикла for} n: integer; {Фактический размер массива}…………………………for i:=g to n-1 do mas[i]:=mas[i+1];Dec(n); {Уменьшение n на 1}…………………………

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

…………………………for i:=n downto g do mas[i+1]:=mas[i];mas[g]:=…Inc(n); {Увеличение n на 1}…………………………

Дата добавления: 2015-08-13