Составьте подпрограмму, реализующую сортировку методом прочесывания - Free Pascal

Узнай цену своей работы

Формулировка задачи:

Помогите, пожалуйста! Задание: составьте подпрограмму, реализующую сортировку методом прочесывания

Решение задачи: «Составьте подпрограмму, реализующую сортировку методом прочесывания»

textual
Листинг программы
  1. {Используется алгоритм, предложенный создателями данной сортировки:}
  2. {Стефаном Лейси (Stephan Lacey) и Ричардом Боксом (Richard Box)    }
  3. procedure CombSort(var a: array of longint);
  4. var i, temp, gap: integer; {указатель, буфер, зазор между зубьями расчёски}
  5.     done: boolean; {флаг отсутствия обмена элементов}
  6. begin
  7.   gap := high(a); {для начала принимаем максимальный зазор}
  8.   repeat
  9.     done := true; {пока будем считать, что обменов не было}
  10.     gap := trunc(gap / 1.3); {вычисляем очередной зазор, 1.3 - от авторов}
  11.     if gap < 1 {корректировка зазора}
  12.       then gap := 1 {зазор меньше единицы быть не должен: будет зацикливание, естественно}
  13.       else if (gap = 9) or (gap = 10) {странно, но факт: при зазоре 9 или 10 сортировка медленнее}
  14.         then gap := 11; {поэтому вместо 9 или 10 принимается 11 - не я виноват, авторы так сказали}
  15.     for i := 0 to high(a) - gap do {обмен при необходимости двух элементов, номера которых различаются на gap}
  16.       begin
  17.        if a[i + gap] < a[i] {если элементы расположены неверно,}
  18.           then begin {то меняем их местами}
  19.             temp := a[i + gap];
  20.             a[i + gap] := a[i];
  21.             a[i] := temp;
  22.             done := false {был обмен: сбрасываем флаг отсутствия обмена}
  23.           end
  24.       end
  25.   until done and (gap = 1) {оканчиваем, когда не было обменов и зазор = 1}
  26. end;
  27.  
  28. {далее - вызывающая проверочная программа}
  29. const m = 100;
  30. var i: integer;
  31.     x: array [1..m] of longint;
  32. begin
  33.   randomize;
  34.   writeln('Source array:');
  35.   for i := 1 to m do
  36.     begin
  37.      x[i] := -99999 + random(199999);
  38.      write(x[i]:8)
  39.     end;
  40.   CombSort(x);
  41.   writeln('Sorted array:');
  42.   for i := 1 to m do write(x[i]:8);
  43.   readln
  44. 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

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы