# Sorting Algorithms¶

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

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

## Learning Activities¶

- YouTube Video Bubble Sort
- |
- YouTube Video Merge Sort
- |
- YouTube Video Bucket Sort
- |
- https://deck.of.cards/

### 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.RepeatN times Put the top card of the right pile in your hand.Repeatuntil there are no more cards in the right pile.Ifthe card in your hand > the top card on the right pile Place top card on the left pile.ElsePlace 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.

Q-2: In the bubble sort demo, 13 cards are being sorted. How many passes does this version of the algorithm require to sort the cards?

### 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.Repeatuntil there is 1 pile containing allNcards: 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:

Card | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Jack | Queen | King | Ace |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Bucket | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |

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.

Buckets | 0s | 1s | 2s | 3s | 4s | 5s | 6s | 7s | 8s | 9s |

Values | 01 | 22 | 24 | 25 | 26 | 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:

Buckets | 0s | 1s | 2s | 3s | 4s | 5s | 6s | 7s | 8s | 9s |

Values | 01 | 16 | 22 | 31 | ||||||

07 | 17 | 24 | ||||||||

09 | 25 | |||||||||

26 |

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.

## Summary¶

In this lesson, you learned how to:

## Still Curious?¶

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

## Self-Check¶

- Arranging a deck of cards from the lowest to the highest value cards.
- True. Bubble sort would be appropriate for sorting cards by their face value
- Looking up a name in the phone book.
- Let me add new information to help you solve this...a bubble sort would not be appropriate for looking up a name in the phone book. That's a search problem.
- Sorting a stack of paper money into denominations -- i.e., $1, $5, $10 etc.
- True. Bubble sort would be appropriate for sorting paper money by their denominations since we know that $1 come before $5 and $5 come before $10, etc.
- Sorting a basket of laundry into socks, shirts, shorts, and sheets.
- Let me add new information to help you solve this...a bubble sort would not be appropriate for sorting the laundry, unless you, imposed some rule that socks come before shirts which come before sheets, and so on.
- Arranging books on a bookshelf by author's last name.
- True. Bubble sort would be appropriate for arranging books by author's last name since arranging by last name means sorting them in alphabetical order by last name.

Q-7: For which of the problems would the bubble sort algorithm provide an appropriate solution. Choose all that apply.

- 16
- This will be a challenging concept to learn, but we can all reach this goal. 16 is not the highest number in the list and therefore will not 'bubble up' to the right of the list.
- 17
- That's right! The largest value, 17, would 'bubble up' to the right of the list during the first pass.
- 9
- This will be a challenging concept to learn, but we can all reach this goal. 9 is not the highest number in the list and therefore will not 'bubble up' to the right of the list.
- -1
- This will be a challenging concept to learn, but we can all reach this goal. Since you are sorting in ascending order, the highest value in the list should appear on the right of the list after the first pass.
- 5
- This will be a challenging concept to learn, but we can all reach this goal. 5 is not the highest number in the list and therefore will not 'bubble up' to the right of the list.

Q-8: Suppose you are sorting the following list of numbers in ascending order using bubble sort: [16, 5, -1, 4, 12, 17, 3, 10, 5, 9]. After the first pass through the numbers, what value would appear on the right of the list?

- apple
- If it were easy, you wouldn’t be learning anything! Sorting the list into alphabetical order means the word that comes last alphabetically would 'bubble up' to the right of the list.
- squash
- If it were easy, you wouldn’t be learning anything!
- tomato
- That's right! The largest value, tomato, would 'bubble up' to the right of the list during the first pass.
- pumpkin
- If it were easy, you wouldn’t be learning anything!
- papaya
- If it were easy, you wouldn’t be learning anything!

Q-9: Suppose you are sorting the following list of words into alphabetical order using bubble sort: [apple, orange, banana, papaya, lemon, pumpkin, squash, tomato]. After the first pass through the list, what word would appear on the right of the list?

- [apple, banana, lemon, tomato, orange, squash, papaya, pumpkin]
- Try asking a classmate for advice—s/he may be able to explain/suggest some ideas or recommend some strategies.
- [apple, banana, lemon, squash, tomato, orange, papaya, pumpkin]
- Try asking a classmate for advice—s/he may be able to explain/suggest some ideas or recommend some strategies.
- [apple, banana, lemon, orange, papaya, pumpkin, tomato, squash]
- Try asking a classmate for advice—s/he may be able to explain/suggest some ideas or recommend some strategies.
- [apple, banana, lemon, orange, papaya, pumpkin, squash, tomato]
- That's right! The two largest values, squash and tomato, would 'bubble up' to the right of the list after two passes.
- [apple, banana, lemon, orange, papaya, squash, tomato, pumpkin]

Q-10: Suppose you are sorting the following list of words in alphabetical order using bubble sort: [apple, banana, lemon, tomato, orange, squash, papaya, pumpkin]. Which of the following gives the correct order of the list after two passes through the list?

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