The Three Basic N^2 Sorting Algorithms

In this post, we'll have a look at the three basic O(n^2) sorting algorithms:

1. Bubble Sort
2. Insertion Sort
3. Selection Sort

Note: I'll cover QuickSort, MergeSort and HeapSort in separate posts.

Bubble Sort

The idea of bubble sort is to compare every item to every other item, swapping as needed and then repeating these steps n number of times (where n is the total number of items in a given array).

def bubbleSort(array):
  n = len(array)
  for i in range(n):
    for j in range(n-1):
      if array[j] > array[j+1]:
        array[j], array[j+1] = array[j+1], array[j]
  return array

For Example:

Array: [4 2 6 5 3 9]

Outer Loop 1:
4 2 6 5 3 9 -- (4>2? Yes, swap)
2 4 6 5 3 9 -- (4>6? No)
2 4 6 5 3 9 -- (6>5? Yes, swap)
2 4 5 6 3 9 -- (6>3? Yes, swap)
2 4 5 3 6 9 -- (6>9? No)

Outer Loop 2:
2 4 5 3 6 9 -- (2>4? No)
2 4 5 3 6 9 -- (4>5? No)
2 4 5 3 6 9 -- (5>3? Yes, swap)
2 4 3 5 6 9 -- (5>6? No)
2 4 3 5 6 9 -- (6>9? No)

Outer Loop 3:
2 4 3 5 6 9 -- (2>4? No)
2 4 3 5 6 9 -- (4>3? Yes, swap)
2 3 4 5 6 9 -- (4>5? No)
2 3 4 5 6 9 -- (5>6? No)
2 3 4 5 6 9 -- (6>9? No)

Now the array is sorted but we will still have outer loops 4, 5 and 6 because the length of the array is 6.

Complexity:

Time complexity: O(n^2)
Space complexity: O(1)

Insertion Sort

The idea here is to imagine you are holding the items as cards in your left and right hand.

1. Initially you have no cards in your left hand, all the cards are in your right hand.
2. You insert one card from the right hand to the left hand in one iteration.
3. Once you move a card to the left, you immediately sort the cards in your left hand.
4. Then you repeat the process by adding another card to your left hand.

def insertionSort(array):
  n = len(array)
  for i in range(n):
      for j in range(i):
          if array[j] > array[i]:
              array[j], array[i] = array[i], array[j]
  return array

For Example:

Array: [4 2 6 5 3 9]

Step 0

Left hand:
Empty

Right hand:
4 2 6 5 3 9

Step 1

Left hand:
4

Right hand:
2 6 5 3 9

Step 2

Left hand:
4 2 -- (4>2? Yes, swap)
2 4

Right hand:
6 5 3 9

Step 3

Left hand:
2 4 6 -- (2>6? No)
2 4 6 -- (4>6? No)
2 4 6

Right hand:
5 3 9

Step 4

Left hand:
2 4 6 5 -- (2>5? No)
2 4 6 5 -- (4>5? No)
2 4 6 5 -- (6>5? Yes, swap)
2 4 5 6

Right hand:
3 9

Step 5

Left hand:
2 4 5 6 3 -- (2>3? No)
2 4 5 6 3 -- (4>3? Yes, swap)
2 3 5 6 4 -- (5>4? Yes, swap)
2 3 4 6 5 -- (6>5? Yes, swap)
2 3 4 5 6

Right hand:
9

Step 6

Left hand:
2 3 4 5 6 9 -- (2>9? No)
2 3 4 5 6 9 -- (3>9? No)
2 3 4 5 6 9 -- (4>9? No)
2 3 4 5 6 9 -- (5>9? No)
2 3 4 5 6 9 -- (6>9? No)
2 3 4 5 6 9

Right hand:
Empty

The array is sorted at this point.

Complexity:

Time complexity: O(n^2)
Space complexity: O(1)

Selection Sort

In selection sort, we select the correct item for the current position and then move to the next.

def selectionSort(array):
  n = len(array)
  for i in range(n):
    for j in range(i+1, n):
      if array[i] > array[j]:
        array[i], array[j] = array[j], array[i]
  return array

For Example:

Array: [4 2 6 5 3 9]

Outer Loop 1:
4 2 6 5 3 9 -- (4>2? Yes, swap)
2 4 6 5 3 9 -- (2>6? No)
2 4 6 5 3 9 -- (2>5? No)
2 4 6 5 3 9 -- (2>3? No)
2 4 6 5 3 9 -- (2>9? No)

Outer Loop 2:
2 4 6 5 3 9 -- (4>6? No)
2 4 6 5 3 9 -- (4>6? No)
2 4 6 5 3 9 -- (4>5? No)
2 4 6 5 3 9 -- (4>3? Yes, swap)
2 3 6 5 4 9 -- (3>9? No)

Outer Loop 3:
2 3 6 5 4 9 -- (6>5? Yes, swap)
2 3 5 6 4 9 -- (5>4? Yes, swap)
2 3 4 6 5 9 -- (4>9? No)

Outer Loop 4:
2 3 4 6 5 9 -- (6>5? Yes, swap)
2 3 4 5 6 9 -- (5>9? No)

Outer Loop 5:
2 3 4 5 6 9 -- (6>9? No)

The sorted array is: 2 3 4 5 6 9.

Complexity:

Time complexity: O(n^2)
Space complexity: O(1)

All these algorithms have a worst case time complexity of O(n^2). We can do better with QuickSort or MergeSort where the average case time complexity would be O(n log n).