Quick Sort

Quick Sort is very popular and widely used sort algorithm. Quick Sort is generally unstable. But there are ways to make quick sort stable, it depends on the actual implementation.

A sorting algorithm is stable if it maintains the relative order of the items in the final output i.e. Two objects with equal keys should appear in the same order in the sorted output as they appear in the input array to be sorted.

Quick Sort is divide and conquer type of an algorithm and key part of the quick sort is the partitioning implementation. Partitioning basically divides the input list into multiples parts and sorts each one of them recursively. Quick Sort is in place sort i.e. no extra storage space (variables) are required for quick sort algorithm.

Quick Sort algorithm works as follows:

For a given list
1. Pick a "pivot" element
2. "Partition" the array into three parts:
   i. All elements in this part are less than the pivot
  ii. The pivot itself (one element)
 iii. All elements in this part are greater than or equal to pivot
3. Apply the quick sort algorithm to the first and the third part recursively.

Partitioning is the most crucial part of quick sort and it should be done in place. There are different techniques for choosing a pivot element and partitioning.

Best and average case performance for quick sort is O(nlogn). Its worst case performance is O(n^2).
Again quick sort is very widely used algorithm. If we do random shuffling of the list at the beginning of quick sort, then it almost guarantees O(nlogn) performance.

Simplest implementation of Quick Sort in java is as follows:

package computer.science;

import java.util.Random;

public class QuickSort {

public static void sort(int a[]) {

quicksort(a, 0, a.length - 1);

}

private static void quicksort(int[] a, int lo, int hi) {

int i = lo;

int j = hi;

int pivot = a[(lo + hi) / 2];

// partition

while (i <= j) {

while (a[i] < pivot)

i++;

while (a[j] > pivot)

j--;

if (i <= j) {

if (i != j) // optimization

swap(a, i, j);

i++;

j--;

}

}

// quick sort left side

if (lo < j)

quicksort(a, lo, j);

// quick sort right side

if (i < hi)

quicksort(a, i, hi);

}

private static void swap(int[] a, int x, int y) {

int t = a[x];

a[x] = a[y];

a[y] = t;

}

public static void main(String[] args) {

final int LENGTH = 100;

int[] a = new int[LENGTH];

Random random = new Random();

for (int i = 0; i < LENGTH; i++) {

a[i] = random.nextInt(100);

}

System.out.println("Before sort : ");

display(a);

long startTime = System.nanoTime();

sort(a);

long endTime = System.nanoTime();

System.out.println("After sort : ");

display(a);

double sortTime = (endTime - startTime) / 1000000.0;

System.out.println("Estimated Time for Sort: " 

                                 + sortTime + " milliseconds.");

}

private static void display(int[] a) {

for (int i = 0; i < a.length; i++) {

System.out.print(a[i]);

System.out.print(" ");

}

System.out.println();

}

}