Quicksort
4 September 2009, 11:06 PM
This article will be relying on the applet below. The basic idea for this sort is to first select a pivot, and then partitioning the array so anything smaller than the pivot comes before it and the one larger than the pivot comes after it, and lastly recursively partitioning the partitioned sub-arrays until there is no more sub-array to partition. The applet helps to visualize this process, take a look at it. The yellow bar is the pivot currently selected. At this time just observe how elements are swapped during the partitioning process. Also notice a new sub-array (bounded by blue and red vertical lines) is selected for partitioning whenever the yellow bar itself is swapped.
Applet: Basic quicksort animation. Deliberately slowed down to emphasize the exchanges.
There are quite a few ways for selecting the pivot. For simplicity we'll take the last element as the pivot instead. At first the whole array is the sub-array itself so the last element in the array becomes the first pivot. In the applet the pivot is represented by a yellow bar, and the current sub-array is bounded by the blue and red vertical line. To partition the sub-array, starting from the blue vertical line search forward to find an element larger than the pivot and mark this index as left (blue bar). Next starting from the red line search backward to find an element smaller than the pivot and mark the index as right (red bar). Now if left and right has not yet crossed, swap the two element. Keep looking forward and backward starting from the last left and right. When left and right crosses each other swap the pivot with the element currently pointed by left. This completes the partitioning process of a single sub-array. Now the array is already partitioned into two sub-arrays where one of it contains elements less than the pivot and the other one contains elements larger than the pivot. Continue by recursively partitioning on these sub-arrays until there is no more sub-arrays to partition.
Java implementation
Note that this is the very basic of quicksort implementation without any kind of improvement, as such the last element in a sub-array will always be selected as the pivot. The applet above used this method. There are two types of implementation here, the first a "normal" quicksort, and the second similar except without recursion.
1. Basic quicksort.
/** * Quicksort data. Sort starts from here. * * @param data Array to sort. */
public void quicksort(int[] data) {// starts by sorting the full array.
sort(data, 0, data.length-1) ; }/** * Sort a sub-array. * * @param a Array to sort. * @param l Partition left. * @param r Partition right. */
public void sort(int a[], int l, int r) { if (r <= l) return ;// start partitioning array using element at r as pivot
int i = l-1, j = r, pivot = a[r], v ; while (true) {// scan forward (left to right)
while (a[++i] < pivot) ;// scan backward (right to left)
while (pivot < a[--j]) if (j == l) break ;// stop when left and right crosses
if (i >= j) break ;// no crossing yet so we swap left-i and right-j
v = a[i] ; a[i] = a[j] ; a[j] = v ; }// swap pivot and left-most element
v = a[i] ; a[i] = a[r] ; a[r] = v ;// at this point partitioning is complete
// recursively sort left partition
sort(a, l, i-1) ;// recursively sort right partition
sort(a, i+1, r) ; }
2. Basic quicksort without recursion.
/** * Start quicksorting an array. * * @param data Array to sort. */
public void quicksort(int[] data) { quicksort(data, 0, data.length-1); }/** * Start quicksorting a sub-array. * * @param a Sub-array to sort. * @param l Left index. * @param r Right index. */
public void quicksort(int[] a, int l, int r) { Stack s = new Stack() ; s.push(l); s.push(r); int i, j, k, v, pivot ; while (!s.isEmpty()) { r = (Integer)s.pop(); l = (Integer)s.pop() ; if (r <= l) continue ;// start partitioning
i = l-1; j = r; pivot = a[r] ; while (true) {// scan forward (left to right)
while (a[++i] < pivot) ;// scan backward (right to left)
while (pivot < a[--j]) if (j == l) break ;// stop when left and right crosses
if (i >= j) break ; v = a[i] ; a[i] = a[j] ; a[j] = v ; } v = a[i] ; a[i] = a[r] ; a[r] = v ;// end partitioning
if (i-l > r-i) { s.push(l) ; s.push(i-1) ; } s.push(i+1) ; s.push(r) ; if (r-i >= i-l) { s.push(l); s.push(i-1) ; } } }
Last edited on 4 September 2009
Comments
Post a comment~
int i, j, k, v, pivot ;