Before you keep reading...
Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.
Before you keep reading...
Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.
Time Estimate: 45 minutes
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.
- 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.
- 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
- YouTube Video Bubble Sort
- YouTube Video Merge Sort
- YouTube Video Bucket 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.
ActivityUsing 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 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 MergesortHere 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.
ActivityUsing 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:
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.
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.
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.
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:
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.)
In this lesson, you learned how to:
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.