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

Объяснение кода листинга программы

  1. Входные данные программы - массив x размером m (100), заполненный случайными числами от -99999 до 99999.
  2. Программа вызывает функцию CombSort, передавая ей в качестве аргумента массив x.
  3. Внутри функции CombSort определены следующие переменные:
    • i, temp, gap: целочисленные переменные для работы алгоритма сортировки;
    • done: логическое значение, служащее для контроля отсутствия обменов элементов.
  4. Переменная gap инициализируется значением high(a), где a - это входной массив. Значение переменной gap используется в качестве максимального размера зазора между элементами массива для начала работы алгоритма.
  5. В цикле повторяется попытка уменьшить размер зазора между элементами массива. Если зазор становится меньше единицы, он устанавливается равным единице. Если зазор равен 9 или 10, он устанавливается равным 11 для предотвращения зацикливания алгоритма.
  6. Внутренний цикл проверяет необходимость обмена двух элементов, номера которых различаются на gap. Если элементы расположены неверно, они меняются местами, устанавливается флаг done равным false, и выполняется выход из внутреннего цикла.
  7. Цикл продолжается до тех пор, пока не будет выполнено условие: отсутствие обменов и размер зазора равен 1.
  8. После выполнения функции CombSort выводится отсортированный массив x.
  9. Программа завершается чтением символа readln.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 4.067 из 5
Похожие ответы