5.4. Sorting Algorithms¶
This lesson introduces sorting algorithms, a frequently used algorithm in programming for processing data sets. It is also an introduction to the relative efficiencies of different algorithms that solve the same problem.
Professional Development
The Student Lesson: Complete the activities for Complete the activities for Mobile CSP Unit 5 Lesson 5.4: Sorting Algorithms.
Materials
 Decks of cards  can use 13 cards of one suit per student group, although one deck would be ideal.
 Alternatives: https://deck.of.cards/ or PlayingCards.io virtual playing cards (scroll down and select 'Other')
 Projection system
 Videos
5.4.1. Learning Activities¶
Estimated Length: 45 minutes
 Hook/Motivation (5 minutes):
 Sorting "Contest": Students should form groups of 24. Ask the students to discuss in their groups the fastest way to sort a deck of cards. Then distribute one deck of cards to each group (or one suit from a deck), leaving them face down. Start a timer and see which group can get their deck sorted the fastest. Once all the groups have completed, have each group share their strategy for sorting. Emphasize the point that there are different algorithms to solve the same problem, but that each has a different efficiency.(It might be helpful to have the students describe their sort in the form of a pseudocode algorithm  i.e., step by step.)
 Alternative Hook: Ask the students to sort themselves by their birthday (month and day). Have them make a line in class. Once completed, ask them to talk about strategies they used to sort themselves. It might be helpful here to ask the students whether their algorithm required them to compare their birthdays with each other (bubble sort, merge sort) or whether they could do it without comparisons (bucket sort).
 Experiences and Exploration (30 minutes):
 Bubble Sort (10 minutes): Play the video demonstrating the bubble sort and ask the students to hypothesize about how it's being solved. After the video, review the interactive question and the pseudocode for the bubble sort.
 Merge Sort (10 minutes): Play the video demonstrating the merge sort and ask the students to hypothesize about how it's being solved. After the video, review the interactive question and the pseudocode for the merge sort.
 Bucket and Merge Sort (10 minutes): Play the video demonstrating the bucket and radix sort and ask the students to hypothesize about how it's being solved. After the video, review the interactive question and the pseudocode for the bucket and radix sort.
 Rethink, Reflect, and Revise (10 minutes):
 Practice: Have the students practice each sort in their groups with the deck of cards
 Note: Bucket Sort Exercise: Sort By Rank and Suit  Suppose you wanted to sort the deck of cards by both rank and suit, so that all the clubs come before all the diamonds come before all the hearts come before all the spades. How would you do this?
Answer: Once the deck has been sorted by rank. You could sort it into suit using 4 buckets, one for each suit. Try it!  WrapUp: Have the students complete the interactive exercises and portfolio reflections for the lesson
AP Classroom
The College Board's AP Classroom provides a question bank and Topic Questions. You may create a formative assessment quiz in AP Classroom, assign the quiz (a set of questions), and then review the results in class to identify and address any student misunderstandings.The following are suggested topic questions that you could assign once students have completed this lesson.
Suggested Topic Questions:
Assessment Opportunities and Solutions
Solutions Note: Solutions are only available to verified educators who have joined the Teaching Mobile CSP Google group/forum in Unit 1.
Assessment Opportunities
You can examine students’ work on the interactive exercise and their reflection portfolio entries to assess their progress on the following learning objectives. If students are able to do what is listed there, they are ready to move on to the next lesson.
 Interactive Exercises:
 Portfolio Reflections:
LO X.X.X  Students should be able to ...  In the XXX App, look for:
Differentiation: More Practice
If students are struggling with lesson concepts, have them review the following resources:
 Computational Fairy Tales  includes a general sort tale as well as specific ones for bubble, insertion, and merge sorts
 VisuAlgo.net  interactive visualizations, including pseudocode, of bubble, merge, and radix sorts
 Comparison Sort  interactive visualizations
 Bucket Sort visualization
 Radix Sort visualization
 Sorting Algorithms  allows you to control how sorts work with different input sizes, varying the initial degree of sortedness, and type of sort algorithm
Differentiation: Enrichment
Optional Inclass Activity
This could be a nice way to tie together algorithms and data representation. In particular, it provides a practical example of using base4 arithmetic.
Introduction: In the video of the Korean kids on the track, they are performing a radix sort of 3digit numbers. The algorithm first sorts the numbers into buckets by their 1s digit, then by their 10s digit, and then by their 100s digit. This is an example of a base10 radix sort.
Activity: After watching and understanding that example, have the class watch this video (1:29) of radix sort with 13 cards and try to figure out together how it works. This is an example of a base4 radix sort.
The trick here is that base4 arithmetic is being used. So the cards are numbered as follows:
Card  2  3  4  5  6  7  8  9  10  J  Q  K  A 

Base 4  02  03  10  11  12  13  20  21  22  23  30  31  32 
In the video, the cards are first sorted into buckets by the base4 1s digit. Then you by the base4 4s digit.
 On the board, put up 4 buckets, labeled 0, 1, 2, and 3 in the following arrangement,
which corresponds to the arrangement in the video:
0 1 2 3
 Watch the video, pausing where necessary, and observe what buckets the dealer puts the cards into and then write their decimal values (J=10, Q=11, K=12, A=13) under the bucket numbers.
 You should see that on the first pass the cards are arranged modulo 4  i.e., by the remainder of dividing their numeric values by 4.
 Do the same for the second pass. This time the cards are arranged div 4  i.e., by the quotient of dividing their numeric values by 4.
 Now propose that you renumber the cards in base4. And perform sort by their 1s digit and then by their 4s digit.
Challenge Question: Can you sort a deck using some other base? Yes. A nice class exercise now is to work out the sort using, say, base 5 to represent the cards  or any other base.
Background Knowledge: Sorting Algorithms
These resources provide more information on sorting algorithms, including ones not covered in the lesson. Many of the visualizations are interactive or include pseudocode to help you understand them better.
 Comparison Sort  interactive visualizations
 Bucket Sort visualization
 Radix Sort visualization
 Computational Fairy Tales  includes a general sort tale as well as specific ones for bubble, insertion, and merge sorts
 Sorting Algorithms  allows you to control how sorts work with different input sizes, varying the initial degree of sortedness, and type of sort algorithm
 Sorting Algorithms Demo  similar to the previous but presented individually with Java source code (Requires Java browser plugin; doesn't work on Chrome)
5.4.2. Professional Development Reflection¶
Discuss the following questions with other teachers in your professional development program.

I am confident I can teach this lesson to my students.
 1. Strongly Agree
 2. Agree
 3. Neutral
 4. Disagree
 5. Strongly Disagree