CSC 216/s08/enjoy achievement

Formatting Resources

Formatting Help Guide from MetaWiki

Quick Sort: Sort Quicker

The problem

Sorting an array of items efficiently can be a bit of a challenge, especially on very large arrays. When sorting an array, it is ideal to use an algorithm that can sort the items in the fewest steps possible. Quicksort is one potential sorting algorithm that could be used. It involves recursion and moving values around a pivot.

Participants and props

Seven students will participate in the exercise. They will need seven numbered note cards. Each student will hold a numbered note card to represent a value in the array.

The script

Setup

1. There should be a pseudocode description of the merge sort algorithm on a large display.
2. The students should place themselves in some unordered way

Pseudo Code

public int[] quickSort(int[] m) {
    if (m.length == 1) Return m
    else {
       int pivot = m[0];
       int[] lessThan;
       int[] greaterThan;
       for (int i = 1; i < m.length; i++) {
          if (m[i] < pivot) {
             add m[i] to lessThan;
          }
          else {
             add m[i] to greaterThan;
          }
       }
       return merge(quickSort(lessThan), pivot, quickSort(greaterThan)); //returns an array with the elements less than
the pivot first, followed by the pivot, with the greater values after.
    }
}

Activity

First, the seven numbered cards need to be assigned to the seven students. The students line up in some "random" fashion. From there, the students will act out a quick sort on themselves, inferring from the pseudocode.

1. The first student in line acts as the first pivot.
2. Students with values less than the pivot form a list.
3. The rest of the non-pivot form the greater than list.
4. These 2 new lists perform quick sorts on themselves.
5. When 2 lists finish sorting, they merge back in the order of less than list, pivot, and greater than list.