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

Published on 12 May 2024 09:40 PM
#Haxe

How to resolve the algorithm Sorting algorithms/Heapsort step by step in the Haxe 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 Haxe programming language

Source code in the haxe programming language

class HeapSort {
  @:generic
  private static function siftDown<T>(arr: Array<T>, start:Int, end:Int) {
    var root = start;
    while (root * 2 + 1 <= end) {
      var child = root * 2 + 1;
      if (child + 1 <= end && Reflect.compare(arr[child], arr[child + 1]) < 0)
        child++;
      if (Reflect.compare(arr[root], arr[child]) < 0) {
        var temp = arr[root];
        arr[root] = arr[child];
        arr[child] = temp;
        root = child;
      } else {
        break;
      }
    }
  }

  @:generic
  public static function sort<T>(arr:Array<T>) {
    if (arr.length > 1)
    {
      var start = (arr.length - 2) >> 1;
      while (start > 0) {
        siftDown(arr, start - 1, arr.length - 1);
        start--;
      }
    }

    var end = arr.length - 1;
    while (end > 0) {
      var temp = arr[end];
      arr[end] = arr[0];
      arr[0] = temp;
      siftDown(arr, 0, end - 1);
      end--;
    }
  } 
}

class Main {
  static function main() {
    var integerArray = [1, 10, 2, 5, -1, 5, -19, 4, 23, 0];
    var floatArray = [1.0, -3.2, 5.2, 10.8, -5.7, 7.3, 
                      3.5, 0.0, -4.1, -9.5];
    var stringArray = ['We', 'hold', 'these', 'truths', 'to', 
                       'be', 'self-evident', 'that', 'all', 
                       'men', 'are', 'created', 'equal'];
    Sys.println('Unsorted Integers: ' + integerArray);
    HeapSort.sort(integerArray);
    Sys.println('Sorted Integers:   ' + integerArray);
    Sys.println('Unsorted Floats:   ' + floatArray);
    HeapSort.sort(floatArray);
    Sys.println('Sorted Floats:     ' + floatArray);
    Sys.println('Unsorted Strings:  ' + stringArray);
    HeapSort.sort(stringArray);
    Sys.println('Sorted Strings:    ' + stringArray);
  }
}

You may also check:How to resolve the algorithm Show the epoch step by step in the Arturo programming language
You may also check:How to resolve the algorithm Rock-paper-scissors step by step in the Racket programming language
You may also check:How to resolve the algorithm 9 billion names of God the integer step by step in the Clojure programming language
You may also check:How to resolve the algorithm Vector products step by step in the Plain English programming language
You may also check:How to resolve the algorithm Conditional structures step by step in the Nemerle programming language