14
O(n²) Sorting Algorithms
Written by Matei Suica, Kelvin Lau and Vincent Ngo
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.
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, and they only require constant O(1) additional memory space. For small data sets, these sorts compare favorably against more complex sorts. It’s usually not recommended to use O(n²) in production code, but you’ll need to start somewhere, and these algorithms are a great place to start.
In this chapter, you’ll look at the following sorting algorithms:
- Bubble sort.
- Selection sort.
- Insertion sort.
All of these are comparison-based sorting methods. In other words, they rely on a comparison method, such as the less than operator, to order elements. You measure a sorting technique’s general performance by counting the number of times this comparison gets called.
Bubble sort
One of the simplest sorts is the bubble sort. The bubble sort 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, and suppose you want to sort them in ascending order:
Implementation
To get started, open the starter project for this chapter. Because you already know that you’ll need to do a lot of swapping, the first thing you need to do is write an extension for ArrayList to swap elements.
fun <T> ArrayList<T>.swapAt(first: Int, second: Int) {
val aux = this[first]
this[first] = this[second]
this[second] = aux
}
fun <T : Comparable<T>> ArrayList<T>.bubbleSort(showPasses: Boolean = false) {
// 1
if (this.size < 2) return
// 2
for (end in (1 until this.size).reversed()) {
var swapped = false
// 3
for (current in 0 until end) {
if (this[current] > this[current + 1]) {
// 4
this.swapAt(current, current + 1)
swapped = true
}
}
// 5
if(showPasses) println(this)
// 6
if (!swapped) return
}
}
"bubble sort" example {
val list = arrayListOf(9, 4, 10, 3)
println("Original: $list")
list.bubbleSort(true)
println("Bubble sorted: $list")
}
---Example of bubble sort---
Original: [9, 4, 10, 3]
[4, 9, 3, 10]
[4, 3, 9, 10]
[3, 4, 9, 10]
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 only swaps at the end of each pass. You’ll see how that works in the following implementation.
Example
Assume you have the following hand of cards:
Implementation
In src ▸ selectionsort, create a new file named SelectionSort.kt. Since you added the swapAt() extension for the bubble sort, you’ll leverage it here too.
fun <T : Comparable<T>> ArrayList<T>.selectionSort(showPasses: Boolean = false) {
if (this.size < 2) return
// 1
for (current in 0 until (this.size - 1)) {
var lowest = current
// 2
for (other in (current + 1) until this.size) {
if (this[lowest] > this[other]) {
lowest = other
}
}
// 3
if (lowest != current) {
this.swapAt(lowest, current)
}
// 4
if(showPasses) println(this)
}
}
"selection sort" example {
val list = arrayListOf(9, 4, 10, 3)
println("Original: $list")
list.selectionSort(true)
println("Bubble sorted: $list")
}
---Example of selection sort---
Original: [9, 4, 10, 3]
[3, 4, 10, 9]
[3, 4, 10, 9]
[3, 4, 9, 10]
Bubble 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.
Example
The idea of insertion sort is like how you’d sort a hand of cards. Consider the following hand:
Implementation
In src ▸ selectionsort of your starter project, create a new file named InsertionSort.kt. Write the following inside of the file:
fun <T : Comparable<T>> ArrayList<T>.insertionSort(showPasses: Boolean = false) {
if (this.size < 2) return
// 1
for (current in 1 until this.size) {
// 2
for (shifting in (1..current).reversed()) {
// 3
if (this[shifting] < this[shifting - 1]) {
this.swapAt(shifting, shifting - 1)
} else {
break
}
}
// 4
if(showPasses) println(this)
}
}
"insertion sort" example {
val list = arrayListOf(9, 4, 10, 3)
println("Original: $list")
list.insertionSort(true)
println("Bubble sorted: $list")
}
---Example of insertion sort---
Original: [9, 4, 10, 3]
[4, 9, 10, 3]
[4, 9, 10, 3]
[3, 4, 9, 10]
Bubble sorted: [3, 4, 9, 10]
Generalization
In this section, you’ll generalize these sorting algorithms for list types other than ArrayList. Exactly which list types won’t matter, as long as they’re mutable since you need to be able to swap elements. The changes are small and simple but important. You always want your algorithms to be as generic as possible.
fun <T> MutableList<T>.swapAt(first: Int, second: Int)
fun <T : Comparable<T>> MutableList<T>.bubbleSort(showPasses: Boolean = false)
fun <T : Comparable<T>> MutableList<T>.selectionSort(showPasses: Boolean = false)
fun <T : Comparable<T>> MutableList<T>.insertionSort(showPasses: Boolean = false)
Challenges
Challenge 1: To the left, to the left
Given a list of Comparable elements, bring all instances of a given value in the list to the right side of the array.
Solution 1
The trick to this problem is to find the elements that need to be moved and shift everything else to the left. Then, return to the position where the element was before, and continue searching from there.
fun<T: Comparable<T>> MutableList<T>.rightAlign(element: T) {
// 1
if(this.size < 2) return
// 2
var searchIndex = this.size - 2
while(searchIndex >= 0) {
// 3
if(this[searchIndex] == element) {
// 4
var moveIndex = searchIndex
while(moveIndex < this.size - 1 &&
this[moveIndex + 1] != element) {
swapAt(moveIndex, moveIndex + 1)
moveIndex++
}
}
// 5
searchIndex--
}
}
Challenge 2: Duplicate finder
Given a list of Comparable elements, return the largest element that’s a duplicate in the list.
Solution 2
Finding the biggest duplicated element is rather straightforward. To make it even easier, you can sort the list with one of the methods you’ve already implemented.
fun<T: Comparable<T>> MutableList<T>.biggestDuplicate(): T? {
// 1
this.selectionSort()
// 2
for(i in (1 until this.size).reversed()) {
// 3
if(this[i] == this[i - 1]) {
return this[i]
}
}
return null
}
Challenge 3: Manual reverse
Reverse a list of elements by hand. Do not rely on reverse or reversed; you need to create your own.
Solution 3
Reversing a collection is also quite straightforward. Using the double reference approach, you start swapping elements from the start and end of the collection, making your way to the middle.
fun<T: Comparable<T>> MutableList<T>.rev() {
var left = 0
var right = this.size - 1
while (left < right) {
swapAt(left, right)
left++
right--
}
}
Key points
- n² algorithms often have a terrible 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 in sorted order. - Design your algorithms to be as generic as possible without hurting the performance.
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.
© 2022 Razeware LLC
