Составьте подпрограмму, реализующую сортировку методом прочесывания - 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
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д