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

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.

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:

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:

Card2345678 910JQKA
Base 402031011121320212223303132

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.

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