Quick Sort in Java
Quicksort algorithm is based on the divide and conquer approach where an array is divided into subarrays by selecting a pivot element.The pivot element is positioned in such a way that elements less than pivot are kept on the left side and elements greater than pivot are on the right side.The same process is continued for both left and right subarrays. Finally, sorted elements are combined to form a sorted array.
Quick Sort Algorithm Steps
Step 1 : Select a pivot element from the array. The pivot element is a random element which can be the first element, last element, random element, or median.
Step 2 : Partition the array and rearrange it. After partitioning, all elements smaller than the pivot will be on its left, and all elements greater than the pivot will be on its right. The pivot is then in its sorted index, and we obtain the index of the pivot.
Step 3 : Recursively apply the same process to the two partitioned sub-arrays (left and right of the pivot).
Step 4 : The recursion stops when there is only one element left in the sub-array, as a single element is already sorted.
Quick Sort Algorithm Syntax
quickSort(array, lowIndex, highIndex)
if (lowIndex < highIndex)
pivotIndex <- partitionFunction(array,lowIndex, highIndex)
quickSort(array, lowIndex, pivotIndex - 1)
quickSort(array, pivotIndex, highIndex)
partitionFunction(array, lowIndex, highIndex)
set highIndex as pivotIndex
storeIndex <- lowIndex - 1
for i <- lowIndex + 1 to highIndex
if element[i] < pivotElement
swap element[i] and element[storeIndex]
storeIndex++
swap pivotElement and element[storeIndex+1]
return storeIndex + 1Quicksort complexity :
Time Complexity :
Best Case : O(n*logn)
In Quicksort, the best-case occurs when the pivot element is the middle element or near to the middle element. The best-case time complexity of quicksort is O(n*logn).
Average Case : O(n*logn)
It occurs when the array elements are in jumbled order(neither in ascending nor descending order). The average case time complexity of quicksort is O(n*logn).
Worst Case : O(n2)
The worst case occurs when the pivot element is either greatest or smallest element. Suppose, if the pivot element is always the last element of the array, the worst case would occur when the given array is sorted already in ascending or descending order. The worst-case time complexity of quicksort is O(n2).
Space Complexity :
Best-case scenario: O(log n)
As a result of balanced partitioning leading to a balanced recursion tree with a call stack of size O(log n).
Average Case : O(log n)
Worst-case scenario: O(n)
Due to unbalanced partitioning leading to a skewed recursion tree requiring a call stack of size O(n).
Stable : NO
Advantages of Quick Sort :
1) It is a divide-and-conquer algorithm making it easier to solve problems.
2) It is efficient on large data sets.
3) It has a low overhead, and only requires a small amount of memory to function.
4) It is Cache Friendly which work on the same array to sort and do not copy data to any auxiliary array.
5) It is the fastest general purpose algorithm for large data when stability is not required.
6) It is tail recursive and hence all the tail call optimization can be done.
Disadvantages of Quick Sort :
1) When the pivot is chosen poorly,it has the worst-case time complexity of O(n2)
2) It is not a good choice for small data sets.
3) It is not a stable sort, where if two elements have the same key, their relative order will not be preserved in the sorted output in case of quick sort, because here we are swapping elements according to the pivot’s position (without considering their original positions).
Applications of Quick Sort :
1) It is efficient for sorting large datasets where average-case time complexity is O(n log n)
2) It is used in partitioning problems like finding the kth smallest element or dividing arrays by pivot.
3) Integral to randomized algorithms, offering better performance.
4) Quick Sort is applied in cryptography for generating random permutations and unpredictable encryption keys.
5) Partitioning step can be parallelized for improved performance in multi-core or distributed systems.
6) Quick Sort is widely used in theoretical computer science for analyzing average-case complexity and developing new techniques.
Program 1 : Quick Sort in Java
public class QuickSortProg {
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
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);
}
}
public static void main(String[] args) {
int[] arr = {14, 6, 23, 42, 19, 37};
System.out.println("Unsorted Array");
for (int val : arr) {
System.out.print(val + " ");
}
int arr_size = arr.length;
quickSort(arr, 0, arr_size - 1);
System.out.println("\n\n" + "Sorted Array in Ascending Order: ");
for (int val : arr) {
System.out.print(val + " ");
}
}
}Output :
Unsorted Array
14 6 23 42 19 37
Sorted Array in Ascending Order:
6 14 19 23 37 42 Program 2 : Quick Sort in Java using mid element as Pivot
public class QuickSortProg2 {
static int partition(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
return i;
}
static void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
}
public static void main(String[] args) {
int[] arr = {14, 6, 23, 42, 19, 37};
System.out.println("Unsorted Array");
for (int val : arr) {
System.out.print(val + " ");
}
int arr_size = arr.length;
quickSort(arr,0,arr_size - 1);
System.out.println("\n\n" + "Sorted Array in Ascending Order: ");
for (int val : arr) {
System.out.print(val + " ");
}
}
}Output :
Unsorted Array
14 6 23 42 19 37
Sorted Array in Ascending Order:
6 14 19 23 37 42