Home iOS & Swift Books Data Structures & Algorithms in Swift

27
O(n²) Sorting Challenges Written by Kelvin Lau

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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)
    }
  }
}

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
  }
}

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.

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)
    }
  }
}

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.