15 O(n²) Sorting Algorithms¶

O(n²) time complexity isn’t great performance, but the sorting algorithms in this category are easy to understand and useful in some scenarios. One advantage of these algorithms is that they have constant O(1) space complexity, making them attractive for certain applications where memory is limited. For small data sets, these sorting algorithms compare very favorably against more complex sorts.

In this chapter, you’ll learn about the following sorting algorithms:

Bubble sort
Selection sort
Insertion sort

All of these are comparison-based sorting methods since they rely on comparisons to order the elements. You can measure a sorting technique’s general performance by counting the number of times the sorting algorithm compares elements.

Bubble Sort¶

One of the most straightforward sorts is the bubble sort, which repeatedly compares adjacent values and swaps them, if needed, to perform the sort. Therefore, the larger values in the set will “bubble up” to the end of the collection.

Example¶

Consider the following hand of cards. The order is [9, 4, 10, 3]:

4433101099

In the first pass of the bubble-sort algorithm, you start at the beginning of the collection. Compare the first two elements: 9 and 4. Since 9 is larger than 4, these values need to be swapped. The collection then becomes [4, 9, 10, 3]:

4433101099

Move to the next index in the collection to compare 9 and 10. These are already in order, so move to the next index in the collection to compare 10 and 3. Since 10 is larger, these values need to be swapped. The collection then becomes [4, 9, 3, 10]:

4433101099

This completes the first pass. However, a single pass of the algorithm will seldom result in a complete ordering. It certainly didn’t for this example. It will, however, cause the largest value — 10 in this case — to bubble up to the end of the collection. Subsequent passes through the collection will do the same with the next highest numbers.

For the second pass, go back to the beginning of the collection and compare 4 and 9. These are already in order so there’s no need to swap anything. Go on to the next index and compare 9 and 3. Since 9 is larger, swap them. Now the collection becomes [4, 3, 9, 10]:

4433101099

There’s no need to compare 9 and 10 since the first pass already guaranteed that 10 is the largest value. Likewise, the second pass guaranteed that 9 is the second-largest value.

Time for the third pass. Go back to the beginning of the collection and compare 4 and 3. Since 4 is larger, swap them. This gives you [3, 4, 9, 10]:

4499331010

Now the list is completely sorted. No need to keep comparing the 4 with any other cards since those were already sorted in the earlier passes.

Here’s a summary:

Since there were four elements in the collection, you performed three passes. To generalize that, for a collection of length n, you need to do at most n - 1 passes. This is the worst case. If any single pass doesn’t require a swap, that means the list is sorted and bubble sort can terminate early.
The number of comparisons in each pass is one less than the pass before. In the example above you made three comparisons in the first pass, two comparisons in the second pass and one comparison in the last pass. This is because each pass moves the largest value to the end, and so it isn’t necessary to compare those sorted values again.

Implementation¶

Open up the starter project for this chapter and create a lib folder in the root of the project.

Adding a Swap Extension to List¶

All of the sorting algorithms in this chapter will require swapping values between two indices in a list. To make that more convenient, you can add an extension to List itself.

Create a new file called swap.dart in the lib folder. Then add the following extension:

extension SwappableList<E> on List<E> {
  void swap(int indexA, int indexB) {
    final temp = this[indexA];
    this[indexA] = this[indexB];
    this[indexB] = temp;
  }
}

Implementing Bubble Swap¶

Now create a new file in lib named bubble_sort.dart. Write the following inside the file:

import 'swap.dart';

void bubbleSort<E extends Comparable<dynamic>>(List<E> list) {
  // 1
  for (var end = list.length - 1; end > 0; end--) {
    var swapped = false;
    // 2
    for (var current = 0; current < end; current++) {
      if (list[current].compareTo(list[current + 1]) > 0) {
        list.swap(current, current + 1);
        swapped = true;
      }
    }
    // 3
    if (!swapped) return;
  }
}

Here’s the play-by-play:

The outer for loop counts the passes. 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 shorten the list by one with each pass.
The inner for loop handles the work of a single pass. It moves through the indices, comparing adjacent values and swapping them if the first value is larger than the second.
If no values were swapped during a pass, the collection must be sorted and you can exit early.

Testing it Out¶

Head back to bin/starter.dart and replace the contents of the file with the following:

import 'package:starter/bubble_sort.dart';

void main() {
  final list = [9, 4, 10, 3];
  print('Original: $list');
  bubbleSort(list);
  print('Bubble sorted: $list');
}

Run that and you should see the output below:

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.

Note

Bubble sort may be slow, but there are slower ones still. How about if you keep randomly shuffling the elements of the list until you finally get a list that just happens to be sorted? This “algorithm” is known as bogosort. It has an average time complexity of O(n × n!), and factorial time complexities are much worse than quadratic ones.

Selection Sort¶

Selection sort follows the basic idea of bubble sort but improves this algorithm by reducing the number of swap operations. Selection sort will only swap at the end of each pass. You’ll see how that works in the following example.

Example¶

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

Assume you have the following hand of cards represented by the list [9, 4, 10, 3]:

4433101099

In the first pass, selection sort starts at the beginning of the collection and sees the 9. So far that’s the lowest value. The index moves to 4. This is lower than 9 so 4 becomes the new lowest value. Then index moves on to 10. That’s not lower than 4, so the index moves on to 3. Three is lower than 4, so 3 is the new lowest value.

Since you’ve reached the end of the list, you swap the lowest value 3 with the first card in the pass, which was 9. Now you have [3, 4, 10, 9]:

4433101099

Time for the second pass. You can skip card 3 since it’s already sorted. Start with 4. Compare 4 to 10 and then to 9, but 4 remains the lowest value in this pass. Since it’s already in the right location, you don’t need to swap anything.

For the third pass, start with 10. Ten starts as the lowest value, but after you compare it to 9, you find that 9 is lower. There isn’t anything else to compare, so swap the lowest value 9 with the first value 10. That finishes up pass three with [3, 4, 9, 10], and the list is sorted:

4499331010

Implementation¶

Now that you know on a mental level how selection sort works, have a go at implementing it in Dart.

Create a new file named selection_sort.dart in the lib folder. Then add the following code inside the file:

import 'swap.dart';

void selectionSort<E extends Comparable<dynamic>>(List<E> list) {
  // 1
  for (var start = 0; start < list.length - 1; start++) {
    var lowest = start;
    // 2
    for (var next = start + 1; next < list.length; next++) {
      if (list[next].compareTo(list[lowest]) < 0) {
        lowest = next;
      }
    }
    // 3
    if (lowest != start) {
      list.swap(lowest, start);
    }
  }
}

Here’s what’s going on:

The outer for loop represents the passes, where start is the index the current pass should begin at. Since the lowest value is moved to start at the end of every pass, start increments by one each time.
In every pass, you go through the remainder of the collection to find the element with the lowest value.
If a lower value was found, then swap it with the value at the start index.

Testing it Out¶

Back in bin/starter.dart, replace the contents of the file with the following code:

import 'package:starter/selection_sort.dart';

void main() {
  final list = [9, 4, 10, 3];
  print('Original: $list');
  selectionSort(list);
  print('Selection sorted: $list');
}

Run that and you should see the following output in your console:

Original: [9, 4, 10, 3]
Selection sorted: [3, 4, 9, 10]

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.

Dart itself uses the insertion sort. For lists with 32 or fewer elements, the sort method defaults to an insertion sort. Only for larger collections does Dart make use of a different sorting algorithm.

Example¶

The idea of insertion sort is similar to how many people sort a hand of cards. You start with the card at one end and then go through the unsorted cards one at a time, taking each one as you come to it and inserting it in the correct location among your previously sorted cards.

Consider the following hand of [9, 4, 10, 3]:

4433101099

Insertion sort will start at the left where the 9 is. The next card is 4, which is smaller than 9, so you swap the 4 and the 9, giving you [4, 9, 10, 3]. This is the first pass. The first two cards are now sorted:

4433101099

For the second pass, you take the third card, 10. You need to insert it in the right location, so you begin by comparing 10 with the previous card, 9. Well, what do you know? Ten is bigger so it’s already in the right location. You can skip the rest of the comparisons in this pass. This shows how insertion sort can save time when some elements are already sorted.

For the third pass, you need to insert the fourth card, 3, in its proper location. Begin by comparing 3 with the previous card, which is 10. Since 10 is larger, swap them. Now, you’ve got [4, 9, 3, 10]:

4433101099

Keep going. Compare the 3 to the next card to the left, 9. Since 9 is larger, swap 9 and 3, leaving you [4, 3, 9, 10]:

4433101099

You’re not done yet. The 3 needs to keep shifting left until it’s in its correct sort order. So compare 3 with the next card to the left, which is 4. Four is also larger, so swap them to give you [3, 4, 9, 10]:

4499331010

The third pass is now finished, and you’ve got a sorted hand.

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

Implementation¶

Create a new file named insertion_sort.dart in the lib folder. Add the following code inside the file:

import 'swap.dart';

void insertionSort<E extends Comparable<dynamic>>(List<E> list) {
  // 1
  for (var current = 1; current < list.length; current++) {
    // 2
    for (var shifting = current; shifting > 0; shifting--) {
      // 3
      if (list[shifting].compareTo(list[shifting - 1]) < 0) {
        list.swap(shifting, shifting - 1);
      } else {
        break;
      }
    }
  }
}

Here’s what you have:

Insertion sort requires you to iterate from left to right once, which is the job of this outer for loop. At the beginning of the loop, current is the index of the element you want to sort in this pass.
Here, you run backward from the current index so you can shift left as needed.
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.

Testing it Out¶

Head back to bin/starter.dart and replace the code there with the following:

import 'package:starter/insertion_sort.dart';

void main() {
  var list = [9, 4, 10, 3];
  print('Original: $list');
  insertionSort(list);
  print('Insertion sorted: $list');
}

Run that and you should see the following console output:

Original: [9, 4, 10, 3]
Insertion sorted: [3, 4, 9, 10]

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

Stability¶

A sorting algorithm is called stable if the elements of the same type retain their order after being sorted. For example, say you had an unsorted deck of cards in which the 5 of clubs comes before the 5 of diamonds. If you then sort the cards by number only, the 5 of clubs would still come before the 5 of diamonds in a stable sort. That would not necessarily be true for an unstable sorting algorithm.

Of the three sorting algorithms in this chapter, bubble sort and insertion sort are both stable. Selection sort, on the other hand, is not stable because the swapping used in the algorithm can change the relative position of the cards. Take a few cards and see for yourself!

Most of the time it doesn’t matter if a sort is stable or not. However, there are situations when it does matter. For example, say you sort a list of cities from around the world into alphabetical order. If you then sort that same list again by country, the cities within each country will still be in alphabetical order as long as the sort was stable. Using an unstable sort, on the other hand, would result in the cities potentially losing their sort order.

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

Challenges¶

To really get a grasp on how sorting algorithms work, it helps to think through step by step what’s happening. The challenges in this chapter will allow you to do that.

Grab a deck of cards or some paper and a pencil to help yourself out. Sprinkling a few print statements in the code might also help.

You can find the answers in the Challenge Solutions section as well as in the supplemental materials that come with the book.

Challenge 1: Bubble Up¶

Here’s a list of randomly distributed elements:

[4, 2, 5, 1, 3]

Work out by hand the steps that a bubble sort would perform on this list.

Challenge 2: Select the Right One¶

Given the same list as above:

[4, 2, 5, 1, 3]

Work out by hand the steps that a selection sort would perform on this list.

Challenge 3: Insert Here¶

Again, using the same initial list as in the previous challenges:

[4, 2, 5, 1, 3]

Work out by hand the steps that an insertion sort would take to sort this list.

Challenge 4: Already Sorted¶

When you have a list that’s already sorted like the following:

[1, 2, 3, 4, 5]

Are bubble sort, selection sort and insertion sort still O(n²)? How do the algorithms take shortcuts to finish more quickly?

Key Points¶

O(n²) algorithms often have a terrible reputation. Still, some of these algorithms have some redeeming qualities. Insertion sort can sort in O(n) time if the collection is already in sorted order and gradually scales down to O(n²) the more unsorted the collection is.
Insertion sort is one of the best sorts in situations where you know ahead of time that your data is already mostly sorted.