ShellSort

struct ShellSort : SortMethod

Implements the Shell sort algorithm. Shell sort is an in-place comparison sort.

Sorting is done one “gap” at a time. A gap can be thought of as a number of interleaved lists, each individually sorted.

In this implementation, gap is taken to be the middle point of the array to sort.

Note that this method uses the SwappedItem Operation.move rather than Operation.swap – it moves the value in the first number to the index specified in the second number in SwappedItems. Using .swap operation is more common in the current implementations, as .move is used currently only by ShellSort.

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

  • The size of the array to sort.

    Declaration

    Swift

    let size: Int

  • The name of the sort method.

    Declaration

    Swift

    var name: String { get }

  • The description of the Shellsort method.

    Declaration

    Swift

    var description: String { get }

  • Declaration

    Swift

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

  • Inner loop index counter.

    Declaration

    Swift

    private var innerIndex: Int
  • gap

    The gap, divides the sorted array to sublist(s) to be sorted one at a time.

    Declaration

    Swift

    private var gap: Int

  • The value to move in the array.

    Declaration

    Swift

    private var movableValue: Int

  • State handling for ShellSort step by step sorting.

    The various loops in the realAlgorithm() implementation are “opened up” to nextStep(...) implementation using state variable. Depending on the state (which loop and which part of the loop) is executed, state is changed. See comments in realAlgorithm(...) for details.

    See more

    Declaration

    Swift

    private enum State

  • The state variable holding the current state of the sorting.

    Declaration

    Swift

    private var state: State

  • Initializes the sorter to handle arrays of specific size.

    Declaration

    Swift

    init(arraySize: Int)

    Parameters

    arraySize

    The size of the array that is sorted.

  • Restarts the sorter to start from beginning.

    Declaration

    Swift

    mutating func restart()

  • Performs a step in the sorting of the array. Caller will do the actual swapping of values in the array. See State and realAlgorithm() for explanations for the states.

    Declaration

    Swift

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

    Parameters

    array

    The array containing the elements to be sorted
    swappedItems

    Will hold the indexes to swap if any.

    Return Value

    Returns true if the array is sorted.

  • The tight loop implementation of Shell sort, sorting the array at one go.

    Declaration

    Swift

    mutating func realAlgorithm(array: inout [Int])

    Parameters

    array

    The array containing the elements to sort.