26. O(n²) Sorting Algorithms

Written by Kelvin Lau

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:

A single pass of the bubble-sort algorithm would consist of the following steps:

• Start at the beginning of the collection. Compare 9 and 4. These values need to be swapped. The collection then becomes [4, 9, 10, 3].
• Move to the next index in the collection. Compare 9 and 10. These are in order.
• Move to the next index in the collection. Compare 10 and 3. These values need to be swapped. The collection then becomes [4, 9, 3, 10].

A single pass of the algorithm will seldom result in a complete ordering, which is true for this collection. It will, however, cause the largest value — 10 — to bubble up to the end of the collection.

Subsequent passes through the collection will do the same for 9 and 4 respectively:

The sort is only complete when you can perform a full pass over the collection without having to swap any values. At worst, this will require n-1 passes, where n is the count of members in the collection.

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

Here’s the play-by-play:

1. There is no need to sort the collection if it has less than two elements.
2. A single-pass bubbles the largest value to the end of the collection. Every pass needs to compare one less value than in the previous pass, so you essentially shorten the array by one with each pass.
3. This loop performs a single pass; it compares adjacent values and swaps them if needed.
4. If no values were swapped this pass, the collection must be sorted, and you can exit early.

Try it out! Head back into the main playground page and write the following:

example(of: "bubble sort") {
  var array = [9, 4, 10, 3]
  print("Original: \(array)")
  bubbleSort(&array)
  print("Bubble sorted: \(array)")
}

You should see the following output:

---Example of bubble sort---
Original: [9, 4, 10, 3]
Bubble sorted: [3, 4, 9, 10]

Bubble sort has a best time complexity of O(n) if it’s already sorted, and a worst and average time complexity of O(n²), making it one of the least appealing sorts in the known universe.

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:

During each pass, selection sort will find the lowest unsorted value and swap it into place:

1. First, 3 is found as the lowest value. It is swapped with 9.
2. The next lowest value is 4. It’s already in the right place.
3. Finally, 9 is swapped with 10.

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

Here’s what’s going on:

1. You perform a pass for every element in the collection, except for the last one. There is no need to include the last element, since if all other elements are in their correct order, the last one will be as well.
2. In every pass, you go through the remainder of the collection to find the element with the lowest value.
3. If that element is not the current element, swap them.

Try it out! Head back to the main playground page and add the following:

example(of: "selection sort") {
  var array = [9, 4, 10, 3]
  print("Original: \(array)")
  selectionSort(&array)
  print("Selection sorted: \(array)")
}

You should see the following output in your console:

---Example of selection sort---
Original: [9, 4, 10, 3]
Selection sorted: [3, 4, 9, 10]

Just like bubble sort, selection sort has a best, worst and average time complexity of O(n²), which is fairly dismal. It’s a simple one to understand, though, and it does perform better than bubble sort!

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:

Insertion sort will iterate once through the cards, from left to right. Each card is shifted to the left until it reaches its correct position.

1. You can ignore the first card, as there are no previous cards to compare it with.

2. Next, you compare 4 with 9 and shift 4 to the left by swapping positions with 9.

3. 10 doesn’t need to shift, as it’s in the correct position compared to the previous card.

4. Finally, 3 is shifted all the way to the front by comparing and swapping it with 10, 9 and 4, respectively.

It’s worth pointing out that the best case scenario for insertion sort occurs when the sequence of values are already in sorted order, and no left shifting is necessary.

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

Here’s what you did above:

1. Insertion sort requires you to iterate from left to right, once. This loop does that.
2. Here, you run backwards from the current index so you can shift left as needed.
3. Keep shifting the element left as long as necessary. As soon as the element is in position, break the inner loop and start with the next element.

Head back to the main playground page and write the following at the bottom:

example(of: "insertion sort") {
  var array = [9, 4, 10, 3]
  print("Original: \(array)")
  insertionSort(&array)
  print("Insertion sorted: \(array)")
}

You should see the following console output:

---Example of insertion sort---
Original: [9, 4, 10, 3]
Insertion sorted: [3, 4, 9, 10]

Insertion sort is one of the fastest sorting algorithm, if the data is already sorted. That sounds obvious, but it isn’t true for all sorting algorithms. In practice, a lot of data collections will already be largely — if not entirely — sorted, and insertion sort will perform quite well in those scenarios.

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:

• Insertion sort traverses the collection backwards when shifting elements. As such, the collection must be of type BidirectionalCollection.
• Bubble sort and selection sort really only traverse the collection front to back, so they can handle any Collection.
• In any case, the collection must be a MutableCollection as you need to be able to swap elements.

Head back to BubbleSort.swift and update the function to the following:

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

The algorithm stays the same; you simply update the loop to use the collection’s indices. Head back to the main playground page to verify that bubble sort still works the way it should.

Selection sort can be updated as follows:

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

And insertion sort becomes:

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

With just a bit of practice, generalizing these algorithms becomes a fairly mechanical process.

In the next chapters, you’ll take a look at sorting algorithms that perform better than O(n²). Up next is a sorting algorithm that uses a classical algorithm approach known as divide and conquer — merge sort!

Key points

• n² algorithms often have a bad reputation, but some of these algorithms usually have some redeeming points. insertionSort can sort in O(n) time if the collection is already in sorted order and gradually scales down to O(n²).
• insertionSort is one of the best sorts in situations wherein you know, ahead of time, that your data is mostly in a sorted order.