Quick Sort
Quick sort is a divide-and-conquer algorithm that picks a pivot, partitions the array so that elements smaller than pivot are on the left and larger on the right, then recursively sorts the partitions. Average O(n log n), worst O(n²) (when pivot is smallest/largest). It is in-place and not stable.
Java implementation with Lomuto partition:
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
Two Minute Drill
- Quick sort: average O(n log n), worst O(n²) (rare with good pivot).
- In-place, not stable.
- Widely used due to good cache performance.
- Pivot selection (median-of-three) helps avoid worst case.
Need more clarification?
Drop us an email at career@quipoinfotech.com