How to resolve the algorithm Sorting algorithms/Heapsort step by step in the Seed7 programming language

Published on 12 May 2024 09:40 PM
#Seed7

How to resolve the algorithm Sorting algorithms/Heapsort step by step in the Seed7 programming language

Table of Contents

Problem Statement

Heapsort is an in-place sorting algorithm with worst case and average complexity of   O(n logn). The basic idea is to turn the array into a binary heap structure, which has the property that it allows efficient retrieval and removal of the maximal element. We repeatedly "remove" the maximal element from the heap, thus building the sorted list from back to front. A heap sort requires random access, so can only be used on an array-like data structure. Pseudocode:

Write a function to sort a collection of integers using heapsort.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Heapsort step by step in the Seed7 programming language

Source code in the seed7 programming language

const proc: downheap (inout array elemType: arr, in var integer: k, in integer: n) is func
  local
    var elemType: help is elemType.value;
    var integer: j is 0;
  begin
    if k <= n div 2 then
      help := arr[k];
      repeat
        j := 2 * k;
        if j < n and arr[j] < arr[succ(j)] then
          incr(j);
        end if;
        if help < arr[j] then
          arr[k] := arr[j];
          k := j;
        end if;
      until help >= arr[j] or k > n div 2;
      arr[k] := help;
    end if;
  end func;

const proc: heapSort (inout array elemType: arr) is func
  local
    var integer: n is 0;
    var integer: k is 0;
    var elemType: help is elemType.value;
  begin
    n := length(arr);
    for k range n div 2 downto 1 do
      downheap(arr, k, n);
    end for;
    repeat
      help := arr[1];
      arr[1] := arr[n];
      arr[n] := help;
      decr(n);
      downheap(arr, 1, n);
    until n <= 1;
  end func;

You may also check:How to resolve the algorithm Window creation step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Damm algorithm step by step in the BASIC programming language
You may also check:How to resolve the algorithm Hailstone sequence step by step in the uBasic/4tH programming language
You may also check:How to resolve the algorithm Factorions step by step in the Wren programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the App Inventor programming language