HeapSort

struct HeapSort : SortMethod

Heapsort is an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.

Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure (binary tree) to more quickly find the largest element in each step.

Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort.

See https://en.wikipedia.org/wiki/Heapsort

  • Initializes the Heapsort with the size of the array to sort.

    Declaration

    Swift

    init(arraySize: Int)

  • The array size.

    Declaration

    Swift

    var size: Int

  • Name of the sorting method.

    Declaration

    Swift

    var name: String { get }

  • Description of the sorting method.

    Declaration

    Swift

    var description: String { get }

  • Weblinks to read more information.

    Declaration

    Swift

    var webLinks: [(String, String)] { get }

  • Restarts the sorting method by giving intial values to member variables.

    Declaration

    Swift

    mutating func restart()

  • Executes a step of the sorting.

    Declaration

    Swift

    mutating func nextStep(array: [Int], swappedItems: inout SwappedItems) -> Bool

  • States of the step-by-step algorithm.

    See more

    Declaration

    Swift

    private enum State

  • The state of the step-by-step algorithm.

    Declaration

    Swift

    private var state: State

  • To which state to return after sifting down.

    Declaration

    Swift

    private var stateBeforeSifting: State

  • The real algorithm without step-by-step execution.

    Declaration

    Swift

    mutating func realAlgorithm(array: inout [Int])

  • Heapify

    Declaration

    Swift

    private func heapify(_ array: inout [Int], _ count: Int)

  • Sifts the values to their correct places in the heap.

    Declaration

    Swift

    private func siftDown(_ array: inout [Int], start: Int, end: Int)

  • Heap utility method to get the parent node of an index.

    Declaration

    Swift

    private func parent(_ index: Int) -> Int

  • Heap utility method to get the left child node of an index.

    Declaration

    Swift

    private func leftChild(_ index: Int) -> Int

  • Heap utility method to get the right child node of an index.

    Declaration

    Swift

    private func rightChild(_ index: Int) -> Int