Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 9 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 5 chapters
Show chapters Hide chapters

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

16. O(n²) Sorting Algorithms
Written by Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now

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]:

7 6 2 7 65 12 3 8

6 5 4 2 53 32 7 5

0 1 4 6 09 25 8 4

1 5 5 4 02 25 5 7

0 8 2 6 2 4 23 07

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

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<E>>(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;
  }
}

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 = <num>[9, 4, 10, 3];
  print('Original: $list');
  bubbleSort(list);
  print('Bubble sorted: $list');
}

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

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.

1 2 9 7 77 56 0 4

4 5 6 0 13 24 5 2

2 7 4 1 0 4 17 62

Implementation

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

import 'swap.dart';

void selectionSort<E extends Comparable<E>>(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);
    }
  }
}

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 = <num>[9, 4, 10, 3];
  print('Original: $list');
  selectionSort(list);
  print('Selection sorted: $list');
}

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.

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.

0 0 8 5 64 91 4 5

0 8 3 8 95 88 6 5

8 9 7 3 03 90 1 0

4 9 1 9 67 88 5 9

9 2 8 4 7 0 70 50

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<E>>(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;
      }
    }
  }
}

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 = <num>[9, 4, 10, 3];
  print('Original: $list');
  insertionSort(list);
  print('Insertion sorted: $list');
}

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

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.

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.

Challenge 1: Bubble Up

Here’s a list of randomly distributed elements:

[4, 2, 5, 1, 3]

Challenge 2: Select the Right One

Given the same list as above:

[4, 2, 5, 1, 3]

Challenge 3: Insert Here

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

[4, 2, 5, 1, 3]

Challenge 4: Already Sorted

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

[1, 2, 3, 4, 5]

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.
15. Priority Queues
17. Merge Sort
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 reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now