SortingAlgorithm

public protocol SortingAlgorithm : Identifiable

A sorting algorithm, implemented statefully.

The algorithm is responsible for sorting input into output given the answers to the comparisons returned from callAsFunction().

The elements that are sorted do not need to conform to Comparable because the evaluation of the comparison is left to the caller.

Associated Types

  • A type that represents the element that the algorithm is sorting.

    Declaration

    Swift

    associatedtype Element

Static Interface

  • The runtime complexity of the algorithm.

    Declaration

    Swift

    static var complexity: Complexity { get }

  • The unique label of the algorithm.

    Declaration

    Swift

    static var label: SortingAlgorithmLabel { get }

  • Returns the number of comparisons that the algorithm will perform, in the worst case, given an input with n elements.

    The algorithm may require fewer total comparisons than returned depending on the state of the input and the answers to the comparisons. The algorithm is guaranteed to not require more comparisons than returned.

    This value is provably correct and precise. It is not an estimate.

    Declaration

    Swift

    static func calculateMaximumNumberOfComparisonsInWorstCase(for n: Int) -> Int

    Parameters

    n

    The number of elements.

    Return Value

    The number of comparisons that the algorithm will perform in the worst case.

Instance Interface

  • The given elements that the algorithm is sorting.

    This value is constant and will not change after instantiation.

    Declaration

    Swift

    var input: [Element] { get }

  • The current result of applying the sorting algorithm to input.

    This value is “live” and will change as the algorithm is executed. When the algorithm is finished this value will contain the sorted result of input. It is primarily exposed to allow the internals of the algorithm to be observed.

    This value should not be used as the final output of the algorithm unless it is known that the algorithm has finished. It may be easier to perform callAsFunction() and respond to the step that is returned – the output will be reported through that function if the algorithm is finished.

    Declaration

    Swift

    var output: [Element] { get }

  • Answers the current comparison with the given side.

    The algorithm is advanced to the state that follows the answer.

    If the algorithm is not at a point of comparison then this function will have no effect.

    Declaration

    Swift

    mutating func answer(_ answer: Comparison<Self>.Side)

    Parameters

    answer

    The answer to the current comparison.

  • Executes the algorithm in its current state and, if possible, advances it to the next state and returns the step to the caller.

    When the algorithm is not finished this function will return the next comparison that needs to be answered to continue the algorithm. When the algorithm is finished this function will return the sorted output.

    This function is idempotent: for a given state of the algorithm, calling this function will always produce the same result and will always leave the algorithm in the same – possibly new – state. Performing this function consecutively on the same algorithm will have no additional affect.

    Declaration

    Swift

    mutating func callAsFunction() -> SortingAlgorithmStep<Self>

    Return Value

    The next step in the algorithm: either the next comparison to answer, or the sorted output.

  • Returns the element that represents the given side of the current comparison.

    If the algorithm is not at a point of comparison then nil will be returned. For example, if the algorithm has not started or is finished then nil will be returned.

    Declaration

    Swift

    func peekAtElement(for answer: Comparison<Self>.Side) -> Element?

    Parameters

    answer

    The answer that represents the side of the comparison to peek at.

    Return Value

    The element that represents the given side of the current comparison, or nil if the algorithm is not at a point of comparison.

Public Instance Interface

  • The number of comparisons that the algorithm will perform in the worst case.

    The algorithm may require fewer total comparisons than returned depending on the state of the input and the answers to the comparisons. The algorithm is guaranteed to not require more comparisons than returned.

    Declaration

    Swift

    public var numberOfComparisonsInWorstCase: Int { get }
  • answering(_:) Extension method

    Returns the current algorithm after answering the current comparison with the given answer.

    The algorithm is advanced to the state that follows the answer.

    If the algorithm is not at a point of comparison then this function will return itself.

    Declaration

    Swift

    public func answering(_ answer: Comparison<Self>.Side) -> Self

    Parameters

    answer

    The answer to the current comparison.

    Return Value

    The algorithm after applying the answer to the current comparison.