InsertionSort

public struct InsertionSort<Element> : Identifiable
extension InsertionSort: SortingAlgorithm
extension InsertionSort: Codable where Element: Codable
extension InsertionSort: Equatable where Element: Equatable
extension InsertionSort: Hashable where Element: Hashable

A simple sorting algorithm that sorts its elements one at a time.

See also

https://en.wikipedia.org/wiki/Insertion_sort

  • A type that represents the collection of the elements that the algorithm is sorting.

    Declaration

    Swift

    public typealias Elements = Array<Element>
  • id

    The stable identity of the algorithm.

    Declaration

    Swift

    public let id: UUID

  • The given elements that the algorithm is sorting.

    This value is constant and will not change after instantiation.

    Declaration

    Swift

    public let input: Elements

  • 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.

    See also

    outputAfterTransactions

    Declaration

    Swift

    public private(set) var output: Elements { get }

  • The position (in output) of the element that is currently being sorted.

    Declaration

    Swift

    public private(set) var sortingElementIndex: Elements.Index { get }

  • The position (in output) that is one greater than the last sorted element in output.

    output is sorted when this value is equal to output.endIndex.

    Declaration

    Swift

    public private(set) var sortedEndIndex: Elements.Index { get }

Public Initialization

  • Creates an algorithm to sort the given input using insertion sort.

    Declaration

    Swift

    public init(input: Elements)

    Parameters

    input

    The elements to sort.

Public Static Interface

  • The runtime complexity of the algorithm.

    Declaration

    Swift

    public static var complexity: Complexity { get }

  • The unique name of the sorting algorithm.

    Declaration

    Swift

    public 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.

    See also

    http://watson.latech.edu/book/algorithms/algorithmsSorting2.html

    Declaration

    Swift

    public 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.

Public Instance Interface

  • 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

    public 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

    public 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

    public func peekAtElement(for answer: Comparison<InsertionSort<Element>>.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.