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.
-
A type that represents the collection of the elements that the algorithm is sorting.
Declaration
Swift
public typealias Elements = Array<Element>
-
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 }
-
Creates an algorithm to sort the given input using insertion sort.
Declaration
Swift
public init(input: Elements)
Parameters
input
The elements to sort.
-
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.
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.
-
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 thennil
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.