RadixSort

struct RadixSort : SortMethod

Radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix.

For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered.

For this reason, radix sort has also been called bucket sort and digital sort.

This method implements the LSD algorithm (Least Significant Digit). Implementation has places for optimization, exercise left for the reader.

The algorithm is a port from code implemented in another language from Stackoverflow. See comment on realAlgorithm() for details.

  • The states of the algorithm. Basically, as with other methods, the realAlgorigthm was sliced into pieces where no loops exist within nextStep. Well, in this case, one loop creating an array needed for the algo is, but the rest is not.

    Declaration

    Swift

    private enum State

  • Declaration

    Swift

    init(arraySize: Int)

  • Declaration

    Swift

    let size: Int

  • Declaration

    Swift

    var name: String { get }

  • Declaration

    Swift

    var description: String { get }

  • Declaration

    Swift

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

  • Declaration

    Swift

    mutating func restart()

  • Declaration

    Swift

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

  • Sorts a copy of the array in the paramenter using the sorting method in one go. Implementation is based on sample code by Alexander Shostak’s comment from https://stackoverflow.com/questions/15306665/radix-sort-for-negative-integers discussion.

    Declaration

    Swift

    mutating func realAlgorithm(array: inout [Int])