WikiGalaxy
Introduction to Quick Sort
Concept Overview:
Quick Sort is a highly efficient sorting algorithm and is based on partitioning an array into sub-arrays. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
public class QuickSort {
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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
public static void main(String args[]) {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n - 1);
System.out.println("Sorted array: ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
Console Output:
Sorted array: 1 5 7 8 9 10
Quick Sort with First Element as Pivot
Pivot Selection Strategy:
In this variation, the first element of the array is chosen as the pivot. This strategy can lead to poor performance if the array is already sorted or has many duplicate elements.
public class QuickSortFirstPivot {
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low + 1;
for (int j = low + 1; j <= high; j++) {
if (arr[j] < pivot) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
int temp = arr[low];
arr[low] = arr[i - 1];
arr[i - 1] = temp;
return i - 1;
}
void sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
public static void main(String args[]) {
int arr[] = {3, 6, 8, 10, 1, 2, 1};
int n = arr.length;
QuickSortFirstPivot ob = new QuickSortFirstPivot();
ob.sort(arr, 0, n - 1);
System.out.println("Sorted array: ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
Console Output:
Sorted array: 1 1 2 3 6 8 10
Quick Sort with Last Element as Pivot
Pivot Selection Strategy:
This implementation uses the last element as the pivot. It is similar to the standard Quick Sort but might face inefficiencies if the array is sorted in reverse order.
public class QuickSortLastPivot {
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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
public static void main(String args[]) {
int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
int n = arr.length;
QuickSortLastPivot ob = new QuickSortLastPivot();
ob.sort(arr, 0, n - 1);
System.out.println("Sorted array: ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
Console Output:
Sorted array: 2 3 5 6 7 9 10 11 12 14
Quick Sort with Random Pivot
Pivot Selection Strategy:
Choosing a random element as the pivot can help avoid the worst-case performance of Quick Sort, which occurs when the smallest or largest element is always chosen as the pivot.
import java.util.Random;
public class QuickSortRandomPivot {
int partition(int arr[], int low, int high) {
Random rand = new Random();
int pivotIndex = low + rand.nextInt(high - low);
int pivot = arr[pivotIndex];
int temp = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = temp;
pivotIndex = high;
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
public static void main(String args[]) {
int arr[] = {4, 5, 3, 7, 2, 9, 1, 8, 6};
int n = arr.length;
QuickSortRandomPivot ob = new QuickSortRandomPivot();
ob.sort(arr, 0, n - 1);
System.out.println("Sorted array: ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
Console Output:
Sorted array: 1 2 3 4 5 6 7 8 9
Quick Sort with Median-of-Three Pivot
Pivot Selection Strategy:
The median-of-three method selects the pivot as the median of the first, middle, and last elements. This can help balance the partitioning process and improve performance on average.
public class QuickSortMedianPivot {
int medianOfThree(int arr[], int low, int high) {
int mid = (low + high) / 2;
if (arr[low] > arr[mid]) swap(arr, low, mid);
if (arr[low] > arr[high]) swap(arr, low, high);
if (arr[mid] > arr[high]) swap(arr, mid, high);
swap(arr, mid, high - 1);
return arr[high - 1];
}
void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int partition(int arr[], int low, int high) {
int pivot = medianOfThree(arr, low, high);
int i = low, j = high - 1;
while (true) {
while (arr[++i] < pivot);
while (arr[--j] > pivot);
if (i >= j) break;
swap(arr, i, j);
}
swap(arr, i, high - 1);
return i;
}
void sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
public static void main(String args[]) {
int arr[] = {24, 8, 42, 75, 29, 77, 38, 57};
int n = arr.length;
QuickSortMedianPivot ob = new QuickSortMedianPivot();
ob.sort(arr, 0, n - 1);
System.out.println("Sorted array: ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
Console Output:
Sorted array: 8 24 29 38 42 57 75 77
