Quicksort - Java Implementation

This section provides a tutorial on how to implement the Quicksort algorithm in Java. An implementation diagram is also provided.

Here is my Java implementation of Quicksort algorithm:

```/**
* HyArrays.java
* This class contains sorting methods similar to java.util.Arrays.
* All sorting methods should have a signature of
* %Sort(Object[] a, int fromIndex, int toIndex)
* where "fromIndex" is inclusive, and "toIndex" is exclusive.
* Copyright (c) 2011 by Dr. Herong Yang, herongyang.com
*/
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".

Last update: 2011.