Quicksort

Part:   1  2 

This chapter helps you to understand:

• Basic Idea
• Java Implementation
• Performance
• Improvements

Basic Idea

The basic idea of Quicksort is to:

1. Select an element as a pivot element.

2. Data elements are grouped into two sections: one with elements that are in lower order than the pivot element, one with element that are in higher order than the pivot element.

3. Sort the two sections separately by repeating step 1 and 2.

Obviously, this is a recursive idea, where a problem is divided into smaller problems. And the division will be repeated to make the smaller problems even smaller, until they are smaller enough so that the solutions are obvious.

Java Implementation

Here is my Java implementation of Selection Sort algorithm:

/**
 * HyArrays.java
 * This class contains sorting methods similar to java.util.Arrays.
 * All sorting methods should have a signiture of 
 * %Sort(Object[] a, int fromIndex, int toIndex)
 * where "fromIndex" is inclusive, and "toIndex" is exclusive.
 * Copyright (c) 1999 by Dr. Herong Yang
 */
public class HyArrays {
   public static void quickSort(Object[] a, int fromIndex, 
      int toIndex) {
      Object d;
      if (toIndex-1>fromIndex) {
         int j = fromIndex;
         for (int i=j+1; i<toIndex; i++) {
            if (((Comparable)a[fromIndex]).compareTo(a[i])>0) {
               j++;
               d = a[i];
               a[i] = a[j];
               a[j] = d;
            }
         }
         d = a[j];
         a[j] = a[fromIndex];
         a[fromIndex] = d;
         quickSort(a, fromIndex, j+1);
         quickSort(a, j+1, toIndex);
      }
   }
}

The following diagram illustrates how this implementation works:

                               53---------------
                                   39  ... 92   |  67  ...         42
                                    |       |   |   |               |
        +---+-----------+---+---+---+-------+---+---+---------------+
        |   |           |   |   |                
       36  29    ...   17  24   ---------------11                       
        |                   |                   |                   |
fromIndex                   j                   i           toIndex-1

• Elements to be sorted are stored from "fromIndex" to "toIndex-1" inclusive.
• At the beginning of each iteration of loop, elements from "fromIndex+1" to "j" are lower in order than element at "fromIndex".
• At the beginning of each iteration of loop, elements from "j+1" to "i-1" are higher than or equal to element at "fromIndex" in order.
• If the element at "i" is lower than element at "fromIndex", we need to place it in the "lower" section by swapping it with element at "j+1".

(Continued on next part...)

Part:   1  2 

This site Web