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