1
\$\begingroup\$

I have written selection sort in Swift.

Sort([2,4,23,268,9,0]).bySelection()

I am looking for ways to further improve this programme using Swift language features.

struct Sort {

        private var elements:[Int]

        init(_ unsortedElems: [Int]) {
            self.elements = unsortedElems
        }

        func bySelection() -> [Int] {
            return selectionSortAlgo(input: elements)
        }

      }


  typealias SelectionSort = Sort
  extension SelectionSort {

    fileprivate func selectionSortAlgo(input:[Int]) ->[Int] {
        var elements = input
        let size = input.count

        for (index, item) in elements.enumerated() {
            var minimumIndex = index

            for subindex in  (index+1)..<size {
                if elements[subindex] < elements[minimumIndex] {
                    minimumIndex = subindex
                }
            }

            if minimumIndex != index {
                elements[index] = elements[minimumIndex]
                elements[minimumIndex] = item
            }
        }
        return elements
    }
}
\$\endgroup\$
  • \$\begingroup\$ What kind of improvement are you looking for? As far as I can tell, your implementation of the logic is correct. Therefore your question is more about the architecture of your code and not the algorithm itself, right? Like struct versus class, protocols and extensions, not wasting computing resources, conforming to OOP/POP best practices, etc? Please explain with more details what you're looking for, otherwise I'm afraid your question is too broad in its current state. Thanks. :) \$\endgroup\$ – ayaio Sep 3 '17 at 15:26
  • \$\begingroup\$ Yes. correct. I am looking here more for architecture of code and OOPS best practices mainly. \$\endgroup\$ – manismku Sep 4 '17 at 6:26
  • \$\begingroup\$ He. That would make a damn long answer... Here's a few points: the typealias is not needed, it doesn't add any convenience. The computation is done each time you call bySelection(), you should instead cache the result. The public/private access architecture is weird, it's not clear what is really private and why it is so. Also, will you have several Sort instances? And will them be immutable objects, using the unique set of values they got when initialized? Or can they accept new values? Why not use class and inheritance? All these points could be discussed and solutions applied to your code.. \$\endgroup\$ – ayaio Sep 4 '17 at 10:01
  • \$\begingroup\$ And also: it looks like the Sort object will be able to call different sort implementations in the future. It may be interesting to think about how the current architecture would help (or not) achieving your goals. \$\endgroup\$ – ayaio Sep 4 '17 at 10:03
3
\$\begingroup\$

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:

  1. It can only compare Int elements
  2. 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 Sort Collection 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.