27. O(n²) Sorting Challenges

Written by Kelvin Lau

Challenge 1: Group elements

Given a collection of Equatable elements, bring all instances of a given value in the array to the right side of the array.

Challenge 2: Find a duplicate

Given a collection of Equatable (and Hashable) elements, return the first element that is a duplicate in the collection.

Challenge 3: Reverse a collection

Reverse a collection of elements by hand. Do not rely on the reverse or reversed methods.

Solutions

Solution to Challenge 1

The trick to this problem is to control two references to manage swapping operations. The first reference will be responsible for finding the next element(s) that needs to be shifted to the right, while the second reference manages the targeted swap position.

extension MutableCollection
  where Self: BidirectionalCollection, Element: Equatable {

  mutating func rightAlign(value: Element) {
    var left = startIndex
    var right = index(before: endIndex)

    while left < right {
      while self[right] == value {
        formIndex(before: &right)
      }
      while self[left] != value {
        formIndex(after: &left)
      }

      guard left < right else {
        return
      }
      swapAt(left, right)
    }
  }
}

The tricky part here is to understand what sort of capabilities you need. Since you need to make changes to the underlying storage, this function is only available to MutableCollection types.

To complete this algorithm efficiently, you need backwards index traversal, which is why you also constrain against the BidirectionalCollection protocol.

Finally, you also need the elements to be Equatable to target the appropriate values.

The time complexity of this solution is O(n).

Solution to Challenge 2

Finding the first duplicated element is quite straightforward. You use a Set to keep track of the elements you’ve encountered so far.

extension Sequence where Element: Hashable {

  var firstDuplicate: Element? {
    var found: Set<Element> = []
    for value in self {
      if found.contains(value) {
        return value
      } else {
        found.insert(value)
      }
    }
    return nil
  }
}

The constraints for this solution is on Sequence, since it relies on iterating the elements. Each element must also be Hashable, so that you can store it in a set.

The time complexity of this solution is O(n).

Solution to Challenge 3

Reversing a collection is also quite straightforward. Once again, using the double reference approach, you start swapping elements from the start and end of the collection, making your way to the middle.

Once you’ve hit the middle, you’re done swapping, and the collection is reversed.

extension MutableCollection
  where Self: BidirectionalCollection {

  mutating func reverse() {
    var left = startIndex
    var right = index(before: endIndex)

    while left < right {
      swapAt(left, right)
      formIndex(after: &left)
      formIndex(before: &right)
    }
  }
}

For this solution, you constrain against MutableCollection since you need to mutate the collection to reverse.

You also constrain against BidirectionalCollection to utilize backwards index traversal.

The time complexity of this solution is O(n).