5.4. Sorting Algorithms

Time Estimate: 45 minutes

5.4.1. Introduction and Goals

This lesson will focus on different sorting algorithms and we will use a deck of cards in some of the examples. If you have a deck of cards handy, it may help you understand the algorithms better. Alternatively, you can use https://deck.of.cards/.

Sorting is a very important area of study in computer science. As we saw in the previous lesson on Search, it is much more efficient to search a collection if its elements are in order. Sorting is the process of putting objects in order. Sorting algorithms have been studied extensively by computer scientists.

Learning Objectives: I will learn to
  • apply sorting algorithms to given data sets
  • identify the strengths and weaknesses of the bubble sort, merge sort, and bucket sort algorithms
  • describe the difference between comparison sorts such as bubble sort and merge sort, and non-comparison sorts such as bucket sort.
Language Objectives: I will be able to
  • use target vocabulary, such as bubble sort, merge sort, bucket sort, and radix sort, while considering algorithms for sorting data sets, with the support of concept definitions and vocabulary notes from this lesson

5.4.2. Learning Activities

Bubble Sort

One of simplest sorting algorithms is the bubble sort. Here's a video that demonstrates a version of the bubble sort on a collection of 13 playing cards. As you watch it, see if you can discover the algorithm.

Bubble sort is an example of a comparison sort. It repeatedly compares two cards, placing the smaller one on the left pile. As you can see, bubble sort makes several passes through the cards?

The bubble sort is so-called because on each pass through the data, the highest value "bubbles" to the top. For example, in the video, after the first pass, the Ace is placed on the sorted pile. On the second pass, a Queen is placed on the sorted pile. And so on.

Pseudocode for Bubble Sort

Here is a pseudocode description of the bubble sort as seen in the video: 

To Bubble Sort a deck of N cards:
Place the unsorted deck, face down, in the right hand pile.
Repeat N times
    Put the top card of the right pile in your hand.
    Repeat until there are no more cards in the right pile.
        If the card in your hand > the top card on the right pile
            Place top card on the left pile.
        Else
            Place the hand card on the left pile.
    When the pass is finished, put the card left in your hand on the sorted pile.
    Move the left pile to the right pile.

Activity

Using a physical deck of cards or https://deck.of.cards/, try to use the bubble sort algorithm to sort a small part of the deck – six or seven cards.

Merge Sort

Merge sort is another comparison sorting algorithm, so called because it merges the cards into ever larger piles of cards. See if you can follow the algorithm.

As you can see, merge sort starts with the cards in piles of 1 card each. Then on each pass, it merges them into piles of 2 cards, then 4 cards, then 8 cards, and so on, until all the cards are merged into one sorted pile. You probably also noticed that it was quite a bit faster than bubble sort.

Pseudocode of Mergesort

Here is a pseudocode description of merge sort as seen in the video: 


To Merge Sort a deck of N cards:
Divide the cards into N piles containing one card each.
Repeat until there is 1 pile containing all N cards:
    Merge adjacent piles into new piles that are twice as big.

As you can see, Merge sort, like binary search, is another example of a divide and conquer approach to solving the problem, so-called, because it breaks the big problem into smaller problems and works on the smaller problems. In this case, the deck is divided into piles of 1 card each before merging the piles.

Activity

Using a physical deck of cards or https://deck.of.cards/, try sorting it using merge sort. If you try the algorithm on 16 cards, you will always have the same number of cards in each pile.

Bucket Sort: A Non Comparison Sort

Not all sorts are comparison sorts. One example of a non-comparison sort, is the bucket sort, which uses some feature of the values being sorted to place them into distinct buckets. The buckets are then combined together.

In this video, the buckets are the values of the cards -- i.e., 2, 3, Jack, Ace, and so on.



As you see, bucket sort does not compare one card with another. Rather, it uses the card's value to place it into the appropriate bucket. Once all the cards are in their buckets, they are collected together in order. This sort is the fastest of the three examples we've considered.

Pseudocode for Bucket Sort

In order for bucket sort to work, you would have to be able to perform some calculation that would convert the item being sorted into a number that can be used to identify its bucket. For example, we could use the following scheme to give numbers to our playing cards:

Card2345678 910JackQueenKingAce
Bucket2345678 91011121314

We have simply given numerical values (called ranks) to each of the face cards. Now if we have 13 buckets, numbered 2 through 14, then we could use the following algorithm to bucket sort them: 


To Bucket Sort a deck of N cards:
1. For each card in the deck, put it into the bucket indicated by its rank.
2. Starting with the lowest numbered bucket, collect all the cards together.

Activity

That's it. Pretty simple, eh? Using a physical deck of cards or https://deck.of.cards/, try it with the full 52-card deck. After step 1, bucket number 2 should contain all the 2s in the deck. Bucket number 14 should contain all the Aces. If you collect all the cards together in buckets 2, then 3, then 4, and so on, the deck will be completely sorted.

Radix Sort

Bucket sort is actually an example of a more general non-comparison sort called radix. The word radix is another word for base and the original idea behind radix sorting is to sort numbers by their digits.

For example, suppose we want to sort the following list of base 10 2-digit numbers. For convenience we will use leading 0s for numbers between 1 and 9: 

25 26 01 31 24 22 17 16 07 09

We begin by putting them in buckets based on their least significant digit – their rightmost digit.

Buckets0s1s2s3s4s5s6s7s 8s9s
Values 0122 242526 17 09
  31    16 07  

Now if we take the numbers out of the buckets from left to right and from top to bottom in each bucket we get the following list: 

01 31 22 24 25 26 16 17 07 09

Now let's put them into buckets by their left-most digit:

Buckets0s1s2s3s4s5s6s7s 8s9s
Values01162231       
 071724        
 09 25        
   26        
If we now take the numbers out of the buckets from left to right and from top to bottom we get the following sorted list: 
01  07 09 16 17 22 24 25 26 31

As you can probably see, we can sort numbers of any size by re-using the buckets as we sort them through successive passes starting with their rightmost digit and working to their leftmost digit.

Here's a really cool example of radix sort on the playground. In this example, the kids are sorting 3 digit numbers using 9 buckets. First the sort by the ones digit. Then regroup in order. Then by the tens digit. Then regroup in order. And then by the hundreds digit. Then regroup, at which point the numbers are sorted. (Notice there's no bucket for '0' in this example. So none of their numbers contain a 0.)

Recap

To review all of the sort algorithms explained above, try taking a look through some animations of each sort. Go to Sorting Algorithms Visualizations or on Visualgo.

5.4.3. Summary

In this lesson, you learned how to:

5.4.4. Still Curious?

  • This discussion of Merge Sort includes a nice animation.
  • An accessible analysis of Radix Sort.
  • Even President Obama knows about bubble sort:

5.4.5. Self-Check

5.4.6. Reflection: For Your Portfolio

Answer the following portfolio reflection questions as directed by your instructor. Questions are also available in this Google Doc where you may use File/Make a Copy to make your own editable copy.

You have attempted of activities on this page