This Tutorial Explains the Quicksort Algorithm in Java, its illustrations, QuickSort Implementation in Java with the help of Code Examples:
Quicksort sorting technique is widely used in software applications. Quicksort uses a divide-and-conquer strategy like merge sort.
In the quicksort algorithm, a special element called “pivot” is first selected and the array or list in question is partitioned into two subsets. The partitioned subsets may or may not be equal in size.
=> Read Through The Easy Java Training Series.
The partitions are such that all the elements less than the pivot element are towards the left of the pivot and the elements greater than the pivot is at the right of the pivot. The Quicksort routine recursively sorts the two sub-lists. Quicksort works efficiently and also faster even for larger arrays or lists.
What You Will Learn:
Quicksort Partition Java
Partitioning is the key process of the Quicksort technique. So what is partitioning?
Given an array A, we choose a value x called pivot such that all the elements lesser than x are before x, and all the elements greater than x are after x.
A pivot value can be any of the following:
- The first element in the array
- The last element in the array
- The mid element in the array
- Any random element in the array
This pivot value is then placed at its proper position in the array by partitioning the array. Thus the output of the ‘partitioning’ process is the pivot value at its proper position and the elements less than pivot on the left and elements greater than a pivot at the right.
Consider the following diagram that explains the partitioning process.
The above diagram shows the process of partitioning array by repeatedly selecting the last element in the array as a pivot. At each level, note that we partition the array into two sub-arrays by placing pivot at its correct position.
Next, we list the algorithm and pseudo-code for quicksort technique that also includes partition routine.
Quicksort Algorithm Java
The general algorithm for quicksort is given below.
quicksort(Arr, low, high) begin Declare array Arr[N] to be sorted low = 1st element; high = last element; pivot if(low < high) begin pivot = partition (Arr,low,high); quicksort(Arr,low,pivot-1) quicksort(Arr,pivot+1,high) end end
Given below is the pseudo-code for the quicksort technique.
Pseudocode For Quick Sort
Following is the pseudo-code for a quick sort sorting technique. Note that we have provided the pseudo-code for quicksort and partitioning routine.
//pseudocode for quick sort main algorithm
procedure quickSort(arr[], low, high)
arr = list to be sorted
low – first element of the array
high – last element of array
begin
if (low < high)
{
// pivot – pivot element around which array will be partitioned
pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1); // call quicksort recursively to sort sub array before pivot
quickSort(arr, pivot + 1, high); // call quicksort recursively to sort sub array after pivot
}
end procedure
//partition routine selects and places the pivot element into its proper position that will partition the array.
//Here, the pivot selected is the last element of the array
procedure partition (arr[], low, high)
begin
// pivot (Element to be placed at right position)
pivot = arr[high];
i = (low - 1) // Index of smaller element
for j = low to high
{
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap arr[i] and arr[j]
}
}
swap arr[i + 1] and arr[high])
return (i + 1)
end procedure
Illustration
Let’s see the illustration of the quicksort algorithm. Take the following array as an example. Here we have selected the last element as pivot.
As shown, the first element is labeled low and the last element is high.
As evident in the above illustration, there are two pointers, high and low that respectively point to the last and first elements of the array. Both these pointers are moved as the quicksort progresses.
When the element pointed by the low pointer becomes greater than the pivot element and element pointed by the high pointer is lesser than the pivot element, we exchange the elements pointed by the low and high pointer, and each pointer advances by 1 position.
The above steps are carried out until both the pointers cross each other in the array. Once they cross, the pivot element gets its proper position in the array. At this point, the array is partitioned and now we can sort each sub-array independently by recursively applying a quick sort algorithm to each of the sub-array.
Quicksort Implementation In Java
QuickSort technique can be implemented in Java using either recursion or iteration. In this section, we will see both of these techniques.
Recursive Quicksort
We know that the basic technique of quicksort illustrated above uses recursion for sorting the array. In the recursive quicksort after partitioning the array, the quicksort routine is called recursively to sort the sub-arrays.
The below Implementation demonstrates the quicksort technique using recursion.
import java.util.*;
class QuickSort {
//selects last element as pivot, pi using which array is partitioned.
int partition(int intArray[], int low, int high) {
int pi = intArray[high];
int i = (low-1); // smaller element index
for (int j=low; j<high; j++) {
// check if current element is less than or equal to pi
if (intArray[j] <= pi) {
i++;
// swap intArray[i] and intArray[j]
int temp = intArray[i];
intArray[i] = intArray[j];
intArray[j] = temp;
}
}
// swap intArray[i+1] and intArray[high] (or pi)
int temp = intArray[i+1];
intArray[i+1] = intArray[high];
intArray[high] = temp;
return i+1;
}
//routine to sort the array partitions recursively
void quick_sort(int intArray[], int low, int high) {
if (low < high) {
//partition the array around pi=>partitioning index and return pi
int pi = partition(intArray, low, high);
// sort each partition recursively
quick_sort(intArray, low, pi-1);
quick_sort(intArray, pi+1, high);
}
}
}
class Main{
public static void main(String args[]) {
//initialize a numeric array, intArray
int intArray[] = {4,-1,6,8,0,5,-3};
int n = intArray.length;
//print the original array
System.out.println("Original Array: " + Arrays.toString(intArray));
//call quick_sort routine using QuickSort object
QuickSort obj = new QuickSort();
obj.quick_sort(intArray, 0, n-1);
//print the sorted array
System.out.println("\nSorted Array: " + Arrays.toString(intArray));
}
}
Output:
Original Array: [4, -1, 6, 8, 0, 5, -3]
Sorted Array: [-3, -1, 0, 4, 5, 6, 8]
Iterative Quicksort
In iterative quicksort, we use the auxiliary stack to place intermediate parameters instead of using recursion and sort partitions.
The following Java program implements iterative quicksort.
import java.util.*;
class Main {
//partitions the array around pivot=> last element
static int partition(int numArray[], int low, int high) {
int pivot = numArray[high];
// smaller element index
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// check if current element is less than or equal to pivot
if (numArray[j] <= pivot) {
i++;
// swap the elements
int temp = numArray[i];
numArray[i] = numArray[j];
numArray[j] = temp;
}
}
// swap numArray[i+1] and numArray[high] (or pivot)
int temp = numArray[i + 1];
numArray[i + 1] = numArray[high];
numArray[high] = temp;
return i + 1;
}
//sort the array using quickSort
static void quickSort(int numArray[], int low, int high)
{
//auxillary stack
int[] intStack = new int[high - low + 1];
// top of stack initialized to -1
int top = -1;
// push initial values of low and high to stack
intStack[++top] = low;
intStack[++top] = high;
// Keep popping from stack while is not empty
while (top >= 0) {
// Pop h and l
high = intStack[top--];
low = intStack[top--];
// Set pivot element at its correct position
// in sorted array
int pivot = partition(numArray, low, high);
// If there are elements on left side of pivot,
// then push left side to stack
if (pivot - 1 > low) {
intStack[++top] = low;
intStack[++top] = pivot - 1;
}
// If there are elements on right side of pivot,
// then push right side to stack
if (pivot + 1 < high) {
intStack[++top] = pivot + 1;
intStack[++top] = high;
}
}
}
public static void main(String args[])
{
//define array to be sorted
int numArray[] = { 3,2,6,-1,9,1,-6,10,5 };
int n = 8;
System.out.println("Original Array:" + Arrays.toString(numArray));
// call quickSort routine to sort the array
quickSort(numArray, 0, n - 1);
//print the sorted array
System.out.println("\nSorted Array:" + Arrays.toString(numArray));
}
}
Output:
Original Array:[3, 2, 6, -1, 9, 1, -6, 10, 5]
Sorted Array:[-6, -1, 1, 2, 3, 6, 9, 10, 5]
Frequently Asked Questions
Q #1) How does a Quicksort work?
Answer: Quicksort uses a divide and conquers strategy. Quicksort first partitions an array around a pivot element selected and generates sub-arrays that are sorted recursively.
Q #2) What is the time complexity of Quicksort?
Answer: The time complexity of quicksort on an average is O (nlogn). In the worst case, it is O (n^2) the same as the selection sort.
Q #3) Where is Quicksort used?
Answer: Quicksort is mostly used in recursive applications. Quicksort is the part of C-library. Also, almost the programming languages that use built-in sorting implement quicksort.
Q #4) What is the advantage of Quicksort?
Answer:
- Quicksort is an efficient algorithm and can easily sort even a huge list of elements.
- It is in-place sort and hence does not need extra space or memory.
- It is widely used and provides an efficient way to sort data sets of any length.
Q #5) Why is Quicksort better than the merge sort?
Answer: The main reason for which the quicksort is better than the merge sort is that quicksort is in-place sorting method and does not require additional memory space. Merge sort requires additional memory for intermediate sorting.
Conclusion
Quicksort is considered as the best sorting algorithm mainly because of its efficiency to sort even a huge data set in O (nlogn) time.
Quicksort is also an in-place sort and doesn’t require additional memory space. In this tutorial, we have seen the recursive and iterative implementation of quicksort.
In our upcoming tutorial, we will continue with sorting methods in Java.
=> Take A Look At The Java Beginners Guide Here.