February 20th, 2014

Recursive Sorts – Clwk 2/20 – Quick Sort Exercises Part 2
With a partner find 7 different integers to demonstrate
1. The worst case for the quick sort. (most number of swaps)
2. The best case for the quick sort. (least number of swaps)

Post both sets and the number of swaps here.

Recursive Sorts – Clwk 2/20 – Quick Sort Exercises Part 3
1. What is the difference between the quick sort original code and the one from the text book?

Homework:
Recursive Sorts – Hwk 2/20 – Quick Sort random pivot
Write a different quick sort program:
Selection of pivot: choose the first three numbers and randomly assign one of them to be the pivot.

Implementation for the assignments:

/********************************************************************
   ********************************************************************/
   public void quickSort (int[] data, int min, int max)
   {
      int indexofpartition;

      if (max - min  > 0)
      {
         /** Create partitions */
         indexofpartition = findPartition(data, min, max);

         quickSort(data, min, indexofpartition - 1);

         quickSort(data, indexofpartition + 1, max);
      }
   }

   /********************************************************************
   ********************************************************************/
   private int findPartition (int[] data, int min, int max)
   {
      int left, right;
      int temp, partitionelement;

      partitionelement = data[min]; 
      left = min;
      right = max;

         while (left partitionelement) 
            right--;

         if (left