Basic comparison sorting

Bubble sort

Intuition

Imagine a line of warriors. We want to rank all the warriors from the weakest to the strongest.

We start with a pass through the line to decide the strongest warrior.

Then, the first battle is between the warrior at the start of the line and the warrior to the right of him. If the warrior at the start of the line beats the warrior to the right of him, the warrior at the start of the line advances by swapping places with the warrior to the right of him. Otherwise, they don’t swap places and the warrior to the right takes over battling.

Each battle is between a warrior and the warrior to the right until we get to the end of the line. The warrior who ends up at the end of the line is the winner.

Then, we repeat the whole process again to decide the 2nd strongest warrior and again for the 3rd strongest and so on.

All the winners stay at the end of line out of the fray after they’ve secured their position.

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] >= arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

def test_bubble_sort():
    arr = [1, 5, 3, -4, -10, 0]
    bubble_sort(arr)
    assert arr == [-10, -4, 0, 1, 3, 5], arr
    
test_bubble_sort()

Insertion sort

Implementation

  • You need to save the value of the focus card at the beginning, because it will change as you shift the other cards to the right.

Intuition

Suppose you have the following poker hand (with all of the same suit for simplicity and giving you a flush!):

2 8 J K 7

How would you sort this hand from the smallest card to the largest?

You might naturally follow a process like this one.

First, you take the 2nd card out of your hand:

  8
2   J K 7

And look to see if the 2nd card is less than the 1st card:

 8
2   J K 7

8 is greater than 2, so you put the card back in the same place in your hand:

2 8 J K 7

Then you might take out the 3rd card:

    J  
2 8   K 7

And look to see if the 3rd card is less than the 2nd card:

   J  
2 8   K 7

Jack is greater than 8 so you would put the card back in the same place in your hand:

2 8 J K 7

Similarly with the 4th card and then finally the 5th card:

       7
2 8 J K

The 7 is smaller than the King, so you move the King over to the right and you compare the 7 to the Jack:

     7
2 8 J  K

Again the 7 is smaller, so you move the Jack to the right and compare the 7 to the 8:

   7
2 8  J K

Again the 7 is smaller, so you move the 8 to the right and compare the 7 to the 2:

 7
2  8 J K

In this case, 7 is bigger, so you put that card back in your hand after the 2:

2 7 8 J K

And the cards are sorted.

def insertion_sort(hand):
    for focus_index in range(1, len(hand)):
        # The act of pulling it out of your hand can correspond to saving its value.
        focus_card = hand[focus_index]
        
        # Start by comparing to the card immediately to the left.
        comparison_index = focus_index - 1
        
        # Keep going until we reach the beginning or the card to the left is smaller than the focus card.
        while comparison_index >= 0 and focus_card < hand[comparison_index]:
            # If the card to the left is bigger than the focus card, then move that comparison card to the right.
            hand[comparison_index + 1] = hand[comparison_index]
            
            # And compare the focus card to the next card to the left.
            comparison_index -= 1
        
        # Remember that this is (comparison_index + 1)
        # When focus_index = 1, focus_card = hand[1], comparison_index = 0,
        # we want hand[1] = hand[1]
        # Put the focus card back in your hand.
        hand[comparison_index + 1] = focus_card
        
def test_insertion_sort():
    arr = [1, 5, 3, -4, -10, 0]
    insertion_sort(arr)
    assert arr == [-10, -4, 0, 1, 3, 5], arr
    
test_insertion_sort()

Selection sort

Implementation

  • You do not need a separate variable for tracking the min value. You can just look it up in the array.

Efficiency

  • Efficient in the number of writes to memory. Some memory, like Flash drives, have a lifetime limit in the number of writes after which the memory degrades. But there are other algorithms like cycle sort that are better in that case.

  • More comparisons than insertion sort

  • More efficient than merge sort for small lists (5-50)

Intuition

Similarly to the insertion sort, suppose you have a poker hand:

8 K 4 2 J

A natural way you might approach sorting your hand (other than insertion sort) is to start at the first card and scan all the cards in your hand looking for the smallest card. And then swap the smallest card with the first card or do nothing if the smallest card is the first card.

In this case, the smallest card is 2, so we swap it with 8:

2 K 4 8 J

Then, we look for the smallest card starting at the 2nd card and scanning to the left. We find that the smallest card is 4 and swap it with the King:

2 4 K 8 J

And so on until the cards are sorted.

def selection_sort(hand):
    for start_index in range(len(hand)):
        min_index = start_index
        for index in range(start_index + 1, len(hand)):
            if hand[index] < hand[min_index]:
                min_index = index
        # Remember to swap here instead of just setting equal
        hand[min_index], hand[start_index] = hand[start_index], hand[min_index]
        
def test_selection_sort():
    arr = [1, 5, 3, -4, -10, 0]
    selection_sort(arr)
    assert arr == [-10, -4, 0, 1, 3, 5], arr
    
test_selection_sort()