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.

Support Runestone Academy Today

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.

CSP Framework
Big Idea 3: Algorithms and Programming (AAP)
Enduring Understanding AAP-2: The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.A: Express an algorithm that uses sequencing without using a programming language.
Skill 2.A AAP-2.A.2 AAP-2.A.4 Essential Knowledge AAP-2.A.2: Beyond visual and textual programming languages, algorithms can be expressed in a variety of ways, such as natural language, diagrams, and pseudocode. Essential Knowledge AAP-2.A.4: Every algorithm can be constructed using combinations of sequencing, selection, and iteration.
Learning Objective AAP-2.G: Express an algorithm that uses selection without using a programming language.
Skill 2.A AAP-2.G.1 Essential Knowledge AAP-2.G.1: Selection determines which parts of an algorithm are executed based on a condition being true or false.
Learning Objective AAP-2.J: Express an algorithm that uses iteration without using a programming language.
Skill 2.A AAP-2.J.1 Essential Knowledge AAP-2.J.1: Iteration is a repeating portion of an algorithm. Iteration repeats a specified number of times or until a given condition is met.

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
• Bubble Sort
• Merge Sort
• Bucket Sort
• Radix Sort

5.4.1. Learning Activities

Estimated Length: 45 minutes

• Hook/Motivation (5 minutes):
  • Sorting "Contest": Students should form groups of 2-4. 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!
  • Wrap-Up: 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.

• Quizly Solutions
• Portfolio Reflection Questions Solutions

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 In-class Activity

This could be a nice way to tie together algorithms and data representation. In particular, it provides a practical example of using base-4 arithmetic.

Introduction: In the video of the Korean kids on the track, they are performing a radix sort of 3-digit 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 base-10 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 base-4 radix sort.

The trick here is that base-4 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 base-4 1s digit. Then you by the base-4 4s digit.

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

2. 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.
3. 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.
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.
5. Now propose that you renumber the cards in base-4. 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

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.

Support Runestone Academy Today