Quicksort Algorithm

Goals

Students will understand elements of the quicksort algorithm, which uses a pivot element to recursively sort a deck of cards quickly.

Video

Materials

One deck of Acorn cards.

Sample cards from the Acorn deck.

Setup

Shuffle the deck and deal each student 8 cards.

Each student will shuffle their 8 cards, and deal them face-down in a row in front of them, as shown below. These will define their initial collection of cards.

Algorithm

Flip up the right-most card of your current collection. This will be the local pivot element.

Now, use the Partition section below to divide your collection into two sub-collections, the cards lower than the pivot, and the cards higher than the pivot.

For each sub-collection that has more than once card, repeat this algorithm.

Now, flip all the cards face-up. They should be in sorted order!

Partition

To start, flip the left-most card of the sub-collection face-up to become the current card.

1. If the number on the current card is less than or equal to the number on the pivot card, swap it with the card immediately to the right of the shifted-up smaller cards. If there are no shifted-up cards, swap it with the left-most card in the collection. Flip the swapped-out card face-up, and the current card face-down. Since the current card is a smaller card, shift it up.

2. If there is a face-down card to the right of the face-up card, then flip this card face-up to become the new current card, flip the face-up card face-down, and repeat the previous step.

Finally, swap the pivot card with the card immediately to the right of the shifted-up smaller cards. If there are no shifted-up cards, swap it with the left-most card in the collection.

Example

Here is an example of this algorithm applied to the cards 25, 06, 47, 54, 29, 35, 67, and 41.

The right-most card 41 of our collection is flipped face-up as our pivot card.

41 flipped up as the pivot card of the collection.

The first current card is the left-most card of the collection 25. 25 is less than our pivot card 41 so it must be shifted up.

There is a face-down card to the right of our current card so we flip our current card 25 face-down and flip the card to the right face-up.

25 being compared to 41.

The current card 06 is less than our pivot card 41 so it must be shifted up.

There is a face-down card to the right of our current card so we flip our current card 06 face-down and flip the card to the right face-up.

06 being compared to 41.

The current card 47 is greater than our pivot card 41 so we continue.

There is a face-down card to the right of our current card so we flip our current card 47 face-down and flip the card to the right face-up.

47 being compared to 41.

The current card 54 is greater than our pivot card 41 so we continue.

There is a face-down card to the right of our current card so we flip our current card 54 face-down and flip the card to the right face-up.

54 being compared to 41.

The current card 29 is less than our pivot card 41 so it must be shifted up.

The card to the immediate right of our shifted-up cards is swapped into its place.

There is a face-down card to the right of where our current card was so we flip our current card 29 face-down and flip the card to the right face-up.

29 being compared to 41.

The current card 35 is less than our pivot card 41 so it must be shifted up.

The card to the immediate right of our shifted-up cards is swapped into its place.

There is a face-down card to the right of where our current card was so we flip our current card 35 face-down and flip the card to the right face-up.

35 being compared to 41.

The current card 67 is greater than our pivot card 41 so we continue.

There is no face-down card to the right of our current card so we stop and flip the current card face-down.

67 being compared to 41.

The card to the immediate right of our shifted-up cards is swapped with the pivot card.

41 swapping positions with the card to the right of the shifted-up cards.

The shifted up cards will become our current collection.

The right-most card 35 of our collection is flipped face-up as our pivot card.

35 flipped up as the pivot card of the collection.

The first current card is the left-most card of the collection 25. 25 is less than our pivot card 35 so it must be shifted up.

There is a face-down card to the right of our current card so we flip our current card 25 face-down and flip the card to the right face-up.

25 being compared to 35.

The current card 06 is less than our pivot card 35 so it must be shifted up.

There is a face-down card to the right of our current card so we flip our current card 06 face-down and flip the card to the right face-up.

06 being compared to 35.

The current card 29 is less than our pivot card 35 so it must be shifted up.

There is no face-down card to the right of our current card so we stop and flip the current card face-down.

29 being compared to 35.

The card to the immediate right of our shifted-up cards is swapped with the pivot card.

35 swapping positions with the card to the right of the shifted-up cards.

The shifted up cards will become our current collection.

The right-most card 29 of our collection is flipped face-up as our pivot card.

29 flipped up as the pivot card of the collection.

The first current card is the left-most card of the collection 25. 25 is less than our pivot card 29 so it must be shifted up.

There is a face-down card to the right of our current card so we flip our current card 25 face-down and flip the card to the right face-up.

25 being compared to 29.

The current card 06 is less than our pivot card 29 so it must be shifted up.

There is no face-down card to the right of our current card so we stop and flip the current card face-down.

06 being compared to 29.

The card to the immediate right of our shifted-up cards is swapped with the pivot card.

29 swapping positions with the card to the right of the shifted-up cards.

The shifted up cards will become our current collection.

The right-most card 06 of our collection is flipped face-up as our pivot card

06 flipped up as the pivot card of the collection.

The first current card is the left-most card of the collection 25. 25 is greater than our pivot card 06 so we continue.

There is no face-down card to the right of our current card so we stop and flip the current card face-down.

25 being compared to 06.

Since there are no shifted up cards, the left-most card in the collection is swapped with the pivot card.

29 swapping positions with left-most card.

There is only one card in the next collection, so it is flipped face-up.

25 flipped face-up.

The cards that have never been shifted-up become our current collection.

The right-most card 47 of our collection is flipped face-up as our pivot card

47 flipped up as the pivot card of the collection.

The first current card is the left-most card of the collection 54. 54 is greater than our pivot card 47 so we continue.

There is a face-down card to the right of our current card so we flip our current card 54 face-down and flip the card to the right face-up.

54 being compared to 47.

The current card 67 is greater than our pivot card 47 so we continue.

There is no face-down card to the right of our current card so we stop and flip the current card face-down.

67 being compared to 47.

Since there are no shifted up cards, the left-most card in the collection is swapped with the pivot card.

47 swapping positions with left-most card.

The cards that have never been shifted-up become our current collection.

The right-most card 54 of our collection is flipped face-up as our pivot card

54 flipped up as the pivot card of the collection.

The first current card is the left-most card of the collection 67. 67 is greater than our pivot card 54 so we continue.

There is no face-down card to the right of our current card so we stop and flip the current card face-down.

67 being compared to 54.

Since there are no shifted up cards, the left-most card in the collection is swapped with the pivot card.

54 swapping positions with left-most card.

There is only one card in the next collection, so it is flipped face-up.

67 flipped face-up.

Finished

Now all the cards should be flipped up and in sorted order.

Exercises

Evaluation