Составьте подпрограмму, реализующую сортировку методом прочесывания - Free Pascal
Формулировка задачи:
Помогите, пожалуйста!
Задание: составьте подпрограмму, реализующую сортировку методом прочесывания
Решение задачи: «Составьте подпрограмму, реализующую сортировку методом прочесывания»
textual
Листинг программы
{Используется алгоритм, предложенный создателями данной сортировки:}
{Стефаном Лейси (Stephan Lacey) и Ричардом Боксом (Richard Box) }
procedure CombSort(var a: array of longint);
var i, temp, gap: integer; {указатель, буфер, зазор между зубьями расчёски}
done: boolean; {флаг отсутствия обмена элементов}
begin
gap := high(a); {для начала принимаем максимальный зазор}
repeat
done := true; {пока будем считать, что обменов не было}
gap := trunc(gap / 1.3); {вычисляем очередной зазор, 1.3 - от авторов}
if gap < 1 {корректировка зазора}
then gap := 1 {зазор меньше единицы быть не должен: будет зацикливание, естественно}
else if (gap = 9) or (gap = 10) {странно, но факт: при зазоре 9 или 10 сортировка медленнее}
then gap := 11; {поэтому вместо 9 или 10 принимается 11 - не я виноват, авторы так сказали}
for i := 0 to high(a) - gap do {обмен при необходимости двух элементов, номера которых различаются на gap}
begin
if a[i + gap] < a[i] {если элементы расположены неверно,}
then begin {то меняем их местами}
temp := a[i + gap];
a[i + gap] := a[i];
a[i] := temp;
done := false {был обмен: сбрасываем флаг отсутствия обмена}
end
end
until done and (gap = 1) {оканчиваем, когда не было обменов и зазор = 1}
end;
{далее - вызывающая проверочная программа}
const m = 100;
var i: integer;
x: array [1..m] of longint;
begin
randomize;
writeln('Source array:');
for i := 1 to m do
begin
x[i] := -99999 + random(199999);
write(x[i]:8)
end;
CombSort(x);
writeln('Sorted array:');
for i := 1 to m do write(x[i]:8);
readln
end.
Объяснение кода листинга программы
- Входные данные программы - массив
xразмеромm(100), заполненный случайными числами от -99999 до 99999. - Программа вызывает функцию
CombSort, передавая ей в качестве аргумента массивx. - Внутри функции
CombSortопределены следующие переменные:i,temp,gap: целочисленные переменные для работы алгоритма сортировки;done: логическое значение, служащее для контроля отсутствия обменов элементов.
- Переменная
gapинициализируется значениемhigh(a), гдеa- это входной массив. Значение переменнойgapиспользуется в качестве максимального размера зазора между элементами массива для начала работы алгоритма. - В цикле повторяется попытка уменьшить размер зазора между элементами массива. Если зазор становится меньше единицы, он устанавливается равным единице. Если зазор равен 9 или 10, он устанавливается равным 11 для предотвращения зацикливания алгоритма.
- Внутренний цикл проверяет необходимость обмена двух элементов, номера которых различаются на
gap. Если элементы расположены неверно, они меняются местами, устанавливается флагdoneравнымfalse, и выполняется выход из внутреннего цикла. - Цикл продолжается до тех пор, пока не будет выполнено условие: отсутствие обменов и размер зазора равен 1.
- После выполнения функции
CombSortвыводится отсортированный массивx. - Программа завершается чтением символа
readln.