Table of Contents 📚
- Introduction to Quick Sort
- Understanding the Partition Mechanism
- Quicksort Implementation in Java
- Time and Space Complexity
- Summary
Introduction to Quick Sort 🌟
Quick Sort is a divide-and-conquer sorting algorithm that works by selecting a ‘pivot’ element and partitioning the array into two sub-arrays: elements smaller than the pivot and elements greater than the pivot. The algorithm then sorts the sub-arrays recursively. Quick Sort is known for its efficiency, particularly for large datasets.
Understanding the Partition Mechanism Used by Quick Sort 🔀
The core idea behind Quick Sort is the partitioning step, where you choose a pivot element and rearrange the elements such that those smaller than the pivot come before it and those larger come after it. The choice of the pivot can be the first element, the last element, a random element, or even the median element.
There are two popular partitioning techniques:
- Lomuto’s Partitioning: In Hoare’s partitioning, we select the first element as the pivot. We then do two scans of the array: one from the left end and one from the right end, swapping elements when necessary.
- Hoare’s Partitioning: In Lomuto’s partitioning, we usually select the last element as the pivot. We then traverse the array and swap elements to ensure that elements less than the pivot come before elements greater than the pivot.
Quick Sort Implementation in Java 🖥️
public class QuickSortExample {
// Lomuto's Partitioning
public static int lomutoPartition(int[] array, int low, int high) {
int pivot = array[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (array[j] <= pivot) {
i++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
return (i + 1);
}
// Hoare's Partitioning
public static int hoarePartition(int[] array, int low, int high) {
int pivot = array[low];
int i = low - 1, j = high + 1;
while (true) {
do {
i++;
} while (array[i] < pivot);
do {
j--;
} while (array[j] > pivot);
if (i >= j) {
return j;
}
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// Quick Sort Function
public static void quickSort(int[] array, int low, int high, String method) {
if (low < high) {
int pivotIndex;
if ("lomuto".equalsIgnoreCase(method)) {
pivotIndex = lomutoPartition(array, low, high);
quickSort(array, low, pivotIndex - 1, method);
quickSort(array, pivotIndex + 1, high, method);
} else {
pivotIndex = hoarePartition(array, low, high);
quickSort(array, low, pivotIndex, method);
quickSort(array, pivotIndex + 1, high, method);
}
}
}
public static void main(String[] args) {
int[] arrayLomuto = {3, 1, 4, 1, 5, 9, 2, 6, 5};
int[] arrayHoare = {3, 1, 4, 1, 5, 9, 2, 6, 5};
// Using Lomuto's Partitioning
quickSort(arrayLomuto, 0, arrayLomuto.length - 1, "lomuto");
System.out.println("Sorted array using Lomuto's partitioning: " + java.util.Arrays.toString(arrayLomuto));
// Using Hoare's Partitioning
quickSort(arrayHoare, 0, arrayHoare.length - 1, "hoare");
System.out.println("Sorted array using Hoare's partitioning: " + java.util.Arrays.toString(arrayHoare));
}
}Time and Space Complexity of Quick Sort ⏳
- Time Complexity: O(nlogn) on average and best-case scenarios, while O(n2) on the worst-case.
- Space Complexity: O(logn) for the stack space needed for recursion.
Summary
Quick Sort is a powerful sorting algorithm that performs well in real-world scenarios. Both Lomuto’s and Hoare’s partitioning methods work effectively, but Hoare’s method usually results in more balanced partitions and fewer swaps. Hoare’s partition is generally more efficient because it does three times fewer swaps on average and creates more balanced partitions.
If you find this guide useful, please share with others, and spread the knowledge!