Quick Sort DC
Quick sort is a divide-and-conquer sorting algorithm that picks a pivot, partitions the array into elements less than pivot and greater than pivot, then recursively sorts the partitions. Average O(n log n), worst O(n²) (rare with good pivot selection). It's in-place and not stable.
Algorithm steps:
1. Choose a pivot (e.g., last element).
2. Partition the array so that elements less than pivot are left, greater are right.
3. Recursively sort left and right partitions.
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 picks pivot and partitions.
- Average O(n log n), worst O(n²).
- In-place, not stable.
- Good cache performance; widely used.
Need more clarification?
Drop us an email at career@quipoinfotech.com