CSC 216/s08/enjoy achievement: Difference between revisions

From Expertiza_Wiki
Jump to navigation Jump to search
 
(7 intermediate revisions by 3 users not shown)
Line 6: Line 6:
===The problem===
===The problem===


Describe what you are attempting to teach students by this exercise.
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===
===Participants and props===


How many students will participate? What else do you need (e.g., old tennis ball, Powerpoint slides, software).
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. There should be a means of displaying [http://people.engr.ncsu.edu/efg/216/s08/video/t9/QuickSort.swf this animation] created for the learning exercise.


===The script===
===The script===


Describe how to do your exercise.
====Setup====
#There should be a pseudocode description of the merge sort algorithm on a large display.
#The instructor should show and explain [http://people.engr.ncsu.edu/efg/216/s08/video/t9/QuickSort.html our animation].
#The students should place themselves in some unordered way
 
=====Pseudo Code=====
<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.
    }
}
</code>
 
====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.
#The first student in line acts as the first pivot.
#Students with values less than the pivot form a list.
#The rest of the non-pivot form the greater than list.
#These 2 new lists perform quick sorts on themselves.
#When 2 lists finish sorting, they merge back in the order of less than list, pivot, and greater than list.

Latest revision as of 19:10, 6 November 2008

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. There should be a means of displaying this animation created for the learning exercise.

The script

Setup

  1. There should be a pseudocode description of the merge sort algorithm on a large display.
  2. The instructor should show and explain our animation.
  3. 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.