LampSort

struct LampSort : SortMethod

LampSort implements the non-recursive version of QuickSort.

The algorithm uses two stacks to keep lower and higher indexes between which sorting happens, and sorts these ranges. See the animation in action on how this method behaves.

For more information, see e.g. https://medium.com/concerning-pharo/lampsort-a-non-recursive-quicksort-implementation-4d4891b217bd

  • Declaration

    Swift

    let size: Int

  • Holds the indexes to the lower indexes of areas to sort.

    Declaration

    Swift

    private var lows: Stack<Int>

  • Holds the indexes to the higher indes values to sort.

    Declaration

    Swift

    private var highs: Stack<Int>

  • The state variable used in step by step sorting.

    See more

    Declaration

    Swift

    private enum State

  • The name of the sort method.

    Declaration

    Swift

    var name: String { get }

  • Short description for the sort method.

    Declaration

    Swift

    var description: String { get }

  • Declaration

    Swift

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

  • Initializes the sorting method.

    Declaration

    Swift

    init(arraySize: Int)

  • Restarts the method by resetting all members to initial state.

    Declaration

    Swift

    mutating func restart()

  • Peforms a step in Lampsort. Caller will do the actual moving/swapping of values in the array.

    Declaration

    Swift

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

    Parameters

    array

    The array containing the elements to sort.
    swappedItems

    The object which will have the indexes to swap after step has been executed.

    Return Value

    Returns true if after this step, the array has been sorted.

  • Executes the “real” Lampsort algoritm in one go using loops.

    Declaration

    Swift

    mutating func realAlgorithm(array: inout [Int])

    Parameters

    array

    The array to sort.