Previous Next

Overview Day 25

Code:  QuickSort.java

What Do You Think?

Date: Wed, 17 Nov 1999 17:27:55 -0700
From: Mark Phillips <HANDLE@SOMEWHERE.WHATEVER>
To: Gerald Thurman <thurmunit@inficad.com>
Subject: Asignments

Why not bag the rest of the assignments, and instead, enter the JAVA World contest described below?

http://www.javaworld.com/javaworld/codemasters/index.html?111599txt

Perhaps we could work as a team and design/code a singe entry entry. Or, each of us could do it on our own and then compare/contrast our approaches and then submit all the entries.

I am sure there is some application of data structures using Java needed here.....:)

Mark

QuickSort

QuickSort  was first developed by C.A.R. Hoare. It requires you to pick a partition element, then partially sort the array about the partition. You can then sort each of the two partitions by recursive application of the same technique. The algorithm can sort quite rapidly. It can also sort very slowly.

QuickSort is a fast divide-an-conquer algorithm.

The basic algorithm for QuickSort is recursive and consists of the following steps:

  1. If the number of elements is 0 or 1, return.
  2. Pick any element and call it the pivot.
  3. Partition remaining elements into two disjoint groups called L and R.
  4. Return the result of QuickSort(L), followed by the pivot, followed by QuickSort(R).
The pivot divides array elements into two groups: those smaller than the pivot and those larger than the pivot.

The partition step places every element except the pivot in one of two groups. 

   13  81 43  92  31  65  57  26  75  0

   Assume 65 is selected as the pivot.  Partition the elements.

    Left:  13  43  31  26  57  0
   Right:  81  92  75

   Quicksort the left items.  Quicksort the right items.
   0  13  26  31  43  57      75  81  92
                          65
Example: 
   Original list:
      8  1  4  9  6  3  5  2  7  0

   Select the pivot  6  and swap the pivot with the last element.

      8  1  4  9  0  3  5  2  7  6

   Run   i  from left-to-right, and  j  from right-to-left.
   When  i  sees a large element,  i  stops.  When  j  sees
   a small element,  j  stops.  If  i  and  j  have not
   crossed, swap their items and continue; otherwise, stop
   this loop.

      i  stops at element 8; j stops at element 2
      the 8 and 2 are swapped

   2  1  4  9  0  3  5  8  7  6

      i  stops at element 9; j stops at element 5
      the 9 and 5 are swapped

   2  1  4  5  0  3  9  8  7  6

      i  stops at element 9; j stops at element 3
      i and j have crossed -- swap pivot with
      i'th element (6 with 9)

   2  1  4  5  0  3  6  8  7  9
Picking the pivot is crucial to good performance. Never choose the first element as the pivot (you should also avoid the last element). The middle element is usually a reasonable choice. The perfect pivot is one that results in equally sized partitions.

The  median-of-three  is a popular technique for picking a pivot. Sort the first, middle and last elements of the list and use the median (in this case middle) value. Using this technique is good because while in the process of determining the pivot, you are also getting started on the sorting of the list (element 0 will be less than the pivot and element N-1 will be greater than the pivot).

QuickSort pseudo-code: 

   quickSort(T a[], int left, int right) 

      if (left >= right) return;
      SWAP (a, left, (left+right)/2);
      last = left;
      for (i = left+1; i <= right; i++) {
         if (COMPARE (a, i,  left) {
            ++last;
            SWAP (a, last, i);
         }
      }

      SWAP (a, left, last);

      quickSort(a, left, last-1);
      quickSort(a, last+1, right);

Previous Next

[an error occurred while processing this directive]