## Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

#### Before You Begin

Section 0: 6 chapters

#### Section I: Introduction

Section 1: 3 chapters

#### Section II: Elementary Data Structures

Section 2: 6 chapters

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

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

### Challenge 1: Group elements

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

### 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 using `swapAt()`. 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 relatively 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 relatively 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.
© 2024 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now