Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays. Quicksort is an O(nlogn) runtime sorting algorithm, and can be faster than Mergesort and Heapsort when implemented correctly.
Algorithm:
The base case of the recursion is arrays of size < 2, which are in order by definition, so they never need to be sorted.
The pivot selection and partitioning steps can be done in several different ways; the choice of specific implementation schemes greatly affects the algorithm's performance. We will always pick the pivot to be the middle element (not always most efficient way).
Solution (in java):
import java.util.Arrays;
public class QuickSort {
private static int partition(int[] arr, int left, int right) {
int i = left, j = right;
int tmp;
// pivot will be middle element
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
private static int[] quickSort(int[] arr, int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
return arr;
}
private static int[] quickSort(int[] arr) {
if (arr.length < 2)
return arr;
return quickSort(arr, 0, arr.length - 1);
}
public static void main(String[] args) {
int arr[] = {1, 2, 4, 90, 0, -1, 30};
System.out.println(Arrays.toString(quickSort(arr)));
}
}
output:
[-1, 0, 1, 2, 4, 30, 90]