26.
O(n²) Sorting Algorithms
Written by Kelvin Lau
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
Unlock now
O(n²) time complexity is not great performance, but the sorting algorithms in this category are easy to understand and useful in some scenarios. These algorithms are space efficient; they only require constant O(1) additional memory space. For small data sets, these sorts compare very favorably against more complex sorts.
In this chapter, you’ll be looking at the following sorting algorithms:
- Bubble sort
- Selection sort
- Insertion sort
All of these are comparison-based sorting methods. They rely on a comparison method, such as the less-than operator, to order the elements. The number of times this comparison gets called is how you can measure a sorting technique’s general performance.
Bubble sort
One of the simplest sorts is the bubble sort, which repeatedly compares adjacent values and swaps them, if needed, to perform the sort. The larger values in the set will therefore “bubble up” to the end of the collection.
Example
Consider the following hand of cards:
Implementation
Open up the Swift playground for this chapter to get started. In the Sources directory of your playground, create a new file named BubbleSort.swift. Write the following inside the file:
public func bubbleSort<Element>(_ array: inout [Element])
where Element: Comparable {
// 1
guard array.count >= 2 else {
return
}
// 2
for end in (1..<array.count).reversed() {
var swapped = false
// 3
for current in 0..<end {
if array[current] > array[current + 1] {
array.swapAt(current, current + 1)
swapped = true
}
}
// 4
if !swapped {
return
}
}
}
example(of: "bubble sort") {
var array = [9, 4, 10, 3]
print("Original: \(array)")
bubbleSort(&array)
print("Bubble sorted: \(array)")
}
---Example of bubble sort---
Original: [9, 4, 10, 3]
Bubble sorted: [3, 4, 9, 10]
Selection sort
Selection sort follows the basic idea of bubble sort, but improves upon this algorithm by reducing the number of swapAt operations. Selection sort will only swap at the end of each pass. You’ll see how that works in the following example and implementation.
Example
Assume you have the following hand of cards:
Implementation
In the Sources directory of your playground, create a new file named SelectionSort.swift. Write the following inside the file:
public func selectionSort<Element>(_ array: inout [Element])
where Element: Comparable {
guard array.count >= 2 else {
return
}
// 1
for current in 0..<(array.count - 1) {
var lowest = current
// 2
for other in (current + 1)..<array.count {
if array[lowest] > array[other] {
lowest = other
}
}
// 3
if lowest != current {
array.swapAt(lowest, current)
}
}
}
example(of: "selection sort") {
var array = [9, 4, 10, 3]
print("Original: \(array)")
selectionSort(&array)
print("Selection sorted: \(array)")
}
---Example of selection sort---
Original: [9, 4, 10, 3]
Selection sorted: [3, 4, 9, 10]
Insertion sort
Insertion sort is a more useful algorithm. Like bubble sort and selection sort, insertion sort has an average time complexity of O(n²), but the performance of insertion sort can vary. The more the data is already sorted, the less work it needs to do. Insertion sort has a best time complexity of O(n) if the data is already sorted. The Swift standard library sort algorithm uses a hybrid of sorting approaches with insertion sort being used for small (<20 element) unsorted partitions.
Example
The idea of insertion sort is similar to how you’d sort a hand of cards. Consider the following hand:
Implementation
In the Sources directory of your playground, create a new file named InsertionSort.swift. Write the following inside the file:
public func insertionSort<Element>(_ array: inout [Element])
where Element: Comparable {
guard array.count >= 2 else {
return
}
// 1
for current in 1..<array.count {
// 2
for shifting in (1...current).reversed() {
// 3
if array[shifting] < array[shifting - 1] {
array.swapAt(shifting, shifting - 1)
} else {
break
}
}
}
}
example(of: "insertion sort") {
var array = [9, 4, 10, 3]
print("Original: \(array)")
insertionSort(&array)
print("Insertion sorted: \(array)")
}
---Example of insertion sort---
Original: [9, 4, 10, 3]
Insertion sorted: [3, 4, 9, 10]
Generalization
In this section, you’ll generalize these sorting algorithms for collection types other than Array. Exactly which collection types, though, depends on the algorithm:
public func bubbleSort<T>(_ collection: inout T)
where T: MutableCollection, T.Element: Comparable {
guard collection.count >= 2 else {
return
}
for end in collection.indices.reversed() {
var swapped = false
var current = collection.startIndex
while current < end {
let next = collection.index(after: current)
if collection[current] > collection[next] {
collection.swapAt(current, next)
swapped = true
}
current = next
}
if !swapped {
return
}
}
}
public func selectionSort<T>(_ collection: inout T)
where T: MutableCollection, T.Element: Comparable {
guard collection.count >= 2 else {
return
}
for current in collection.indices {
var lowest = current
var other = collection.index(after: current)
while other < collection.endIndex {
if collection[lowest] > collection[other] {
lowest = other
}
other = collection.index(after: other)
}
if lowest != current {
collection.swapAt(lowest, current)
}
}
}
public func insertionSort<T>(_ collection: inout T)
where T: BidirectionalCollection & MutableCollection,
T.Element: Comparable {
guard collection.count >= 2 else {
return
}
for current in collection.indices {
var shifting = current
while shifting > collection.startIndex {
let previous = collection.index(before: shifting)
if collection[shifting] < collection[previous] {
collection.swapAt(shifting, previous)
} else {
break
}
shifting = previous
}
}
}
Key points
- n² algorithms often have a bad reputation, but some of these algorithms usually have some redeeming points.
insertionSortcan sort in O(n) time if the collection is already in sorted order and gradually scales down to O(n²). -
insertionSortis one of the best sorts in situations wherein you know, ahead of time, that your data is mostly in a sorted order.