WikiGalaxy
Quick Sort Algorithm
Introduction:
Quick Sort is a highly efficient sorting algorithm and is based on partitioning an array into smaller sub-arrays. A large array is partitioned into two arrays, one of which holds values smaller than a specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
public class QuickSort {
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n-1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
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);
}
}
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low-1);
for (int j=low; j
Explanation:
The above code demonstrates the Quick Sort algorithm. The function quickSort is a recursive function that sorts the array arr using the partitioning method. The partition function rearranges the elements based on the pivot and returns the index of the pivot element.
Console Output:
Sorted array: 1 5 7 8 9 10
Quick Sort with Random Pivot
Introduction:
Using a random pivot can sometimes improve the performance of Quick Sort, particularly in cases where the input array is sorted or nearly sorted.
import java.util.Random;
public class QuickSortRandomPivot {
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n-1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = randomPartition(arr, low, high);
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
static int randomPartition(int[] arr, int low, int high) {
Random rand = new Random();
int pivotIndex = low + rand.nextInt(high - low);
swap(arr, pivotIndex, high);
return partition(arr, low, high);
}
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low-1);
for (int j=low; j
Explanation:
In this example, a random pivot is chosen using a random number generator. The randomPartition function swaps the randomly chosen pivot with the last element and then calls the partition function.
Console Output:
Sorted array: 1 5 7 8 9 10
Quick Sort with Median of Three
Introduction:
The Median of Three method selects the pivot as the median of the first, middle, and last elements. This approach helps to avoid the worst-case scenario for sorted or nearly sorted arrays.
public class QuickSortMedianOfThree {
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n-1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = medianOfThreePartition(arr, low, high);
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
static int medianOfThreePartition(int[] arr, int low, int high) {
int mid = low + (high - low) / 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);
return partition(arr, low, high);
}
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low-1);
for (int j=low; j
Explanation:
The medianOfThreePartition function finds the median of the first, middle, and last elements, swaps it with the last element, and then calls the partition function. This method reduces the likelihood of encountering the worst-case time complexity.
Console Output:
Sorted array: 1 5 7 8 9 10
Quick Sort with Tail Call Optimization
Introduction:
Tail call optimization in Quick Sort reduces the stack space required by converting recursive calls into iterations. This is particularly useful for sorting large arrays.
public class QuickSortTailCallOptimization {
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n-1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
static void quickSort(int[] arr, int low, int high) {
while (low < high) {
int pi = partition(arr, low, high);
if (pi - low < high - pi) {
quickSort(arr, low, pi - 1);
low = pi + 1;
} else {
quickSort(arr, pi + 1, high);
high = pi - 1;
}
}
}
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low-1);
for (int j=low; j
Explanation:
The main idea behind tail call optimization is to eliminate the need for additional stack space by iterating over the larger partition. This reduces the depth of the recursive call stack.
Console Output:
Sorted array: 1 5 7 8 9 10
Quick Sort with Dual-Pivot
Introduction:
The Dual-Pivot Quick Sort uses two pivots to partition the array into three parts, which can be more efficient than the traditional single-pivot approach.
public class QuickSortDualPivot {
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
dualPivotQuickSort(arr, 0, n-1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
static void dualPivotQuickSort(int[] arr, int low, int high) {
if (low < high) {
int[] piv = partition(arr, low, high);
dualPivotQuickSort(arr, low, piv[0] - 1);
dualPivotQuickSort(arr, piv[0] + 1, piv[1] - 1);
dualPivotQuickSort(arr, piv[1] + 1, high);
}
}
static int[] partition(int[] arr, int low, int high) {
if (arr[low] > arr[high]) swap(arr, low, high);
int j = low + 1;
int g = high - 1;
int k = low + 1;
int p = arr[low];
int q = arr[high];
while (k <= g) {
if (arr[k] < p) {
swap(arr, k, j);
j++;
} else if (arr[k] >= q) {
while (arr[g] > q && k < g) g--;
swap(arr, k, g);
g--;
if (arr[k] < p) {
swap(arr, k, j);
j++;
}
}
k++;
}
j--;
g++;
swap(arr, low, j);
swap(arr, high, g);
return new int[]{j, g};
}
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void printArray(int[] arr, int size) {
for (int i=0; i
Explanation:
The Dual-Pivot Quick Sort algorithm partitions the array into three sections using two pivot elements. This can lead to better performance in certain cases compared to the traditional single-pivot Quick Sort.
Console Output:
Sorted array: 1 5 7 8 9 10
