Пирамидальная сортировка - Turbo Pascal
Формулировка задачи:
Нужна помощь, тема сложная улучшенные методы сортировки, метод пирамидальной сортировки, есть программа со всем необходимым, но не хватает процедуры сортировки.
Условие такое: Дан одномерный массив, первую его половину элементов отсортировать по возрастанию, а вторую по убыванию.
Добавить счётчик итераций(по возможности).
По возрастанию есть небольшой кусок кода(просто как пример), но его нужно как-то адаптировать к программе(к моему условию) и плюс ещё добавить сортировку второй части по убыванию
Решение задачи: «Пирамидальная сортировка»
textual
Листинг программы
Uses Crt; Const N = 50; Type T_Mas = Array [0..N] of Integer; Var Mas : T_Mas; Kol : Integer; Procedure Count (Var Kol:Integer); {Процедура определения размерности массива} Var IOR : Word; Begin Write('Введите размерность массива: '); Repeat {$I-} ReadLn(Kol); {$I+} IOR := IOResult; If odd(IOR) or not(Kol in [1..N]) Then WriteLn('Ошибка. Повторите ввод.') Until (Kol<=N) and (IOR=0) End; Procedure Filling (Kol:Integer; Var A: T_Mas); {Процедура заполнения массива} Var I : Integer; Begin Randomize; For I := 1 To Kol Do A[I] := Random(N) End; Procedure Print (Kol:Integer; A: T_Mas); {Процедура вывода массива} Var I : Integer; Begin For I:=1 to Kol do Write (A[I], ' ') End; {.......................пирамидальная сортировка........................} procedure Sort(Kol: integer; var A: T_mas); procedure Sort_1(var A: T_Mas; Count: Integer); procedure DownHeap(index, Count: integer; Current: integer); {Функция пробегает по пирамиде восстанавливая ее Также используется для изначального создания пирамиды Использование: Передать номер следующего элемента в index Процедура пробежит по всем потомкам и найдет нужное место для следующего элемента} var Child, k: Integer; begin k:= Kol div 2; for i:=1 to k-1 do begin while index < Count div 2 do begin Child := (index+1)*2-1; if (Child < Count-1) and (A[Child] < A[Child+1]) then Child:=Child+1; if Current >= A[Child] then break; A[index] := A[Child]; index := Child; end; A[index] := Current; end; procedure Sort_2(var A: T_Mas; Count: Integer); procedure DownHeap(index, Count: integer; Current: integer); {Функция пробегает по пирамиде восстанавливая ее Также используется для изначального создания пирамиды Использование: Передать номер следующего элемента в index Процедура пробежит по всем потомкам и найдет нужное место для следующего элемента} var Child, k: Integer; begin k:= Kol div 2; for i:=1 to k-1 do begin while index > Count div 2 do begin Child := (index+1)*2-1; if (Child > Count-1) and (A[Child] > A[Child+1]) then Child:=Child+1; if Current <= A[Child] then break; A[index] := A[Child]; index := Child; end; A[index] := Current; end; {Основная функция } var i: integer; Current: integer; begin {Собираем пирамиду} for i := (Count div 2)-1 downto 0 do DownHeap(i, Count, A[i]); {Пирамида собрана. Теперь сортируем} for i := Count downto 0 do begin Current := A[i];{перемещаем верхушку в начало отсортированного списка} A[i] := A[0]; DownHeap(0, i, Current);{находим нужное место в пирамиде для нового элемента} end; end; {......................................................................} Begin ClrScr; Count(Kol); Filling(Kol, Mas); WriteLn('Исходный массив'); Print (Kol, Mas); {................процедура пирамидальной сортировки..........} sort(Mas,Kol); WriteLn; WriteLn('Отсортированный массив'); Print (Kol, Mas); Repeat until KeyPressed End.
Объяснение кода листинга программы
Этот код написан на Turbo Pascal и выполняет пирамидальную сортировку массива. Давайте разберем его по шагам:
- Объявляются переменные:
Kol
- индекс размера массива, введенный пользователем.Mas
- массив для сортировки.IOR
- слово, используемое для чтения ввода пользователя.Count
- переменная, которая хранит количество элементов в массиве.I
- переменная, используемая в процедуреDownHeap
.Child
иk
- две переменные, используемые в процедуреDownHeap
.Current
- переменная, которая хранит текущий элемент, который нужно вставить в отсортированную часть массива.
- Заполняется массив
Mas
:- В процедуре
Filling
с помощью генератора случайных чисел заполняются все элементы массиваMas
.
- В процедуре
- Выводится исходный массив:
- В процедуре
Print
выводятся все элементы массиваMas
.
- В процедуре
- Выполняется пирамидальная сортировка:
- В процедуре
Sort
вызывается рекурсивно процедураDownHeap
, которая выполняет сортировку массиваMas
. - В процедуре
DownHeap
происходит следующее:- Перебираются все элементы массива
Mas
до тех пор, пока не будет найден подходящий элемент для вставки текущего элемента. - Если текущий элемент меньше или равен элементу в вершине пирамиды, он вставляется вместо него.
- Если текущий элемент больше вершины пирамиды, он становится новым вершиной пирамиды.
- Если текущий элемент уже находится в вершине пирамиды, он просто перемещается в начало отсортированной части массива.
- Перебираются все элементы массива
- В процедуре
- Выводится отсортированный массив:
- В процедуре
Print
выводятся все элементы массиваMas
.
- В процедуре
- Основной цикл программы:
- В процедуре
Sort
вызывается рекурсивно процедураDownHeap
, пока не будет выполнено условие завершения сортировки. - После этого выводится отсортированный массив.
- В процедуре
- Программа завершается, когда пользователь нажимает клавишу
KeyPressed
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д