In-Place Quick Sort of An Integer Array

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists. [From wiki]
The steps are:

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

Time Complexity: for n entries,
   Θ(n log(n)) in the average case.
   Θ(n^2) in the worst case.

Space Complexity:
   Θ(log(n)) in the average case.
   Θ(n log(n)) when the input array is very large. the space is needed for storing variables like left, right and pivot. .

Java code for in-place Quick Sort here:

public void quickSort(int input[], int left, int right) {
int pivot = input[(left +right)/2];
int i = left, j = right;
int temp;


while (i <= j){
while(input[i] < pivot && i < right)
i++;
while(input[j] > pivot && j > left)
j--;

if (i <= j ) {
temp = input[j];
input[j] = input[i];
input[i] = temp;
i++; j--;
}
}

if (left <j)
quickSort(input, left, j);
if (i < right)
quickSort(input, i, right);
}

Posted in Java, Programming, qsort, Quick Sort, quicksort, Search Algorithm, sorting algorithm