This algorithm is slightly faster than merge sort and heap sort on random data. Uses a divide-and-conquer approach.
The main idea of the algorithm is as follows:
- select an element from the array, we will call this element as “pivot”. This element can be any element, let’s take the rightmost element
- place elements that are smaller than the pivot value to the left side of the pivot
- place elements that exceed the pivot value to the right side of the pivot
- recursively call the sort function on the left subarray and the right subarray.
Time complexity (average): O(n log n)
Space complexity: O(n)
import java.util.Arrays;
public class ImplementQuickSort {
public static void quickSort(int[] array, int left, int right) {
if (right <= left) {
return;
}
int pivot = array[right];
int i = left;
for (int j = left; j < right; j++) {
if (array[j] < pivot) {
int buffer = array[i];
array[i] = array[j];
array[j] = buffer;
i++;
}
}
int temp = array[right];
array[right] = array[i];
array[i] = temp;
quickSort(array, left, i - 1);
quickSort(array, i + 1, right);
}
public static void main(String[] args) {
int[] array = {6, 5, 4, 3, 2, 1};
System.out.println(Arrays.toString(array));
quickSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
}