I'll review this in two steps: first the body of selectionSortAlgo and then the higher level structure/architecture.
The selection sort implementation
Swapping elements
First of all, there is a bug (the only one I could find) in the code that swaps two elements that sometimes loses elements while swapping them. The smallest example where I can reproduce this is by sorting [1, 0, 0] which results in [0, 0, 0], losing the 1.
Looking at this code:
if minimumIndex != index { elements[index] = elements[minimumIndex] elements[minimumIndex] = item }
I see that you're reading the item from the array as you're enumerating it and writing that at the minimumIndex, presumably to avoid having to get a tempItem to swap the two elements:
if minimumIndex != index { let tempItem = elements[index] elements[index] = elements[minimumIndex] elements[minimumIndex] = tempItem }
The problem is that — because of array's value semantics — this doesn't account for changes that happen to the array since you started enumerating it. In short, you're swapping in a stale value from before you started sorting the array.
Now, what you're really doing here is swapping the elements at two indices, and that is best done with swapAt(_:_:). It's also documented to have no effect if the two indices are the same, so you can get rid of the surrounding if-statment:
elements.swapAt(minimumIndex, index)
If you're following along step-by-step you'll notice that the item of the enumerated array is now unused, so you can change it to only loop over the indices:
for index in elements.indices { ... }
Finding the index of the smallest element
I'll make two small syntactical changes to the code that finds the minimumIndex, partly to leverage Swift features but also to prepare the code to be generic (which I'll discuss later).
First, I'd like to describe what this loop is doing as "iterating through the indices of the slice of elements starting from the current index". In code I'd translate that into:
for subIndex in elements[index...].indices { ... }
Other than the minor syntactical difference, this means that the type of subIndex is an associated type of the collection being enumerated. This has no benefit for arrays, but will be important if you want to be able to sort other collections.
Secondly, since the loop body is only executed when the element at that subIndex is smaller than the element at the current minimumIndex I would possibly move the inner if-statement to a where clause:
var minimumIndex = index for subIndex in elements[index...].indices where elements[subIndex] < elements[minimumIndex] { minimumIndex = subIndex }
This change is only syntactical.
Going even further
Realistically I would probably stop here, but I'm going to continue to show more of this process and other implementations.
Considering the goal of that loop, what it's really doing it "finding the index of the minimum element in the rest of the elements".
There is two ways we can approach this goal. The first approach is by first finding the minimum element, and then finding the index of that element:
// The slice will never be empty, so it will always have a smallest element let minimumElement = elements[index...].min()! // This is one of the elements, so it will always have an index let minimumIndex = elements[index...].index(of: minimumElement)!
In both of these lines it's safe to force-unwrap the results because:
- the array slice will never be empty, so there will always be "some" smallest element
- the smallest element comes from
elements, so it will always have an index.
This alternative works, if it's a style that you prefer. However, it's iterating the slice twice; once to find the element and once to find the index.
To address that I'll use a zip to iterate over both the elements and the indices at the same time and find the minimum element-index-pair by comparing the elements. Since only the minimum index is needed to swap the elements I'll use tuple destructuring to only reference the minimumIndex once it's found.
// The slice will never be empty, so it will always have a smallest element let (_, minimumIndex) = zip(elements[index...], index...).min(by: { $0.0 < $1.0 })!
For the same reason as before, it's safe to force-unwrap here. The slice will never be empty.
Higher level structure/architecture
At a high level there are two limitations to the Sort struct and its underlying implementations:
- It can only compare
Int elements - It can only sort arrays.
The first is pretty straightforward to address, by making the struct generic over an Element type that is constrained to be Comparable and by using arrays of that Element type:
struct Sort<Element: Comparable> { private var elements : [Element] ... }
The second one is a bit trickier and highlights some constraints in how Sort can be extended to support other sorting algorithms. To make Sort support any kind of collection, it would be natural to also make it generic over a Collection type that is a Swift collection:
struct Sort<Collection: Swift.Collection, Element: Comparable> where Collection.Element == Element { private var unsortedElements : Collection }
However, with this change the selection sort algorithm can no longer be used because swapAt(_:_:) is a method of MutableCollection rather than Collection. It's possible to constrain the SortCollection to be a mutable collection, but what if another algorithm has another requirement? With this strategy we would end up constraining Sort more and more to the sum of all the different algorithms requirements.
A better alternative is to keep Sort as broad as possible, but to supply no sorting algorithms by default. Instead each sorting algorithm would be added as an extension only where the generic placeholder types satisfy those requirements:
extension Sort where Collection: MutableCollection { func bySelection() -> Collection { var elements = unsortedElements for index in elements.indices { let slice = elements[index...] let (_, minIndex) = zip(slice, slice.indices) .min(by: { $0.0 < $1.0 })! // The slice will never be empty, so it will always have a smallest element elements.swapAt(minIndex, index) } return elements } }
This change was greatly simplified because I had already moved away from the assumption of Int indices and instead got the index type from the collections associated Index type (implicitly). In other words, here minIndex is of the type Collection.Index rather than Int.
With this strategy each sorting algorithm can be added separately with the type constraints it needs, and a user of this API would have access to only the sorting algorithms that are available for the type of collection they are using.
At this point I don't see any value in the wrapping Sort struct, since these algorithm could be added as extensions to the collection itself in the same way. This solutions also has a more convenient and more "swifty" call site syntax
[2, 4, 23, 268, 9, 0].selectionSorted()
In the end, this is probably the solution that I'd end up with (without the Sort struct):
extension MutableCollection where Element: Comparable { func selectionSorted() -> Self { var elements = self for index in indices { let slice = elements[index...] let (_, minIndex) = zip(slice, slice.indices) .min(by: { $0.0 < $1.0 })! // The slice will never be empty, so it will always have a smallest element elements.swapAt(minIndex, index) } return elements } }
It's flexible in that it works with any mutable collection of any comparable element type. It's convenient in that it will show up immediately on the collection types where it's supported. I also feel that it's "swifty" in its style and conventions – both in its implementation and at its call site.
