The Essence of the QuickSort Algorithm
QuickSort is a nifty little algorithm. It might seem a bit tricky for beginners, but its core principle is as old and simple as time itself: "divide and conquer". Here's the rundown:- First up, pick a pivot element in the array. The middle one's a common choice, but hey, why not live on the edge and pick it randomly? Or, if you're feeling lazy, just snag the first or last element.
- Time to partition! Split the array so that elements less than the pivot scooch to the left, and the bigger ones shuffle to the right.
- Keep on dividing. Repeat the process recursively for the left and right parts of the array until each part is just one element strong.

Before Implementing the Algorithm
Before you start coding, consider these key points about quicksort algorithm in Java: Watch the boundaries. Be careful with the array limits to avoid stepping out of bounds. In other words, make sure the range (low and high indexes) is legit before you partition or call QuickSort recursively. Stack overflow. No, not the website. With recursion, you might run into stack overflow issues, especially with big arrays. How to dodge this? Maybe start with the smaller of the two subarrays post-partition. Picking the pivot in QuickSort is like choosing the right spice — it can make or break your dish. Here are some popular methods:- First or last element. Easy peasy, but it might backfire in performance, especially if the array is already somewhat sorted.
- Middle element. Calculating the index as (low + high) / 2 can dodge some worst-case scenarios.
- Median of three. Choose the median of three elements (usually the first, middle, and last). This often leads to a more balanced split.
- Random element. This can reduce the chance of hitting the worst-case performance, especially for arrays that are already sorted or have a certain structure.
- For massive arrays, there's a method called "median of medians". It's complex and involves extra calculations but offers a more balanced pivot selection.
Implementing QuickSort in Java
Let's jump into implementing QuickSort in Java.
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] array = {17, 14, 15, 28, 6, 8, -6, 1, 3, 18};
System.out.println("Unsorted Array: " + Arrays.toString(array));
quickSort(array, 0, array.length - 1);
System.out.println(" Sorted Array: " + Arrays.toString(array));
}
public 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);
}
}
private static 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;
}
}
The output of the program is here:
Import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] array = {17, 14, 15, 28, 6, 8, -6, 1, 3, 18};
System.out.println("Unsorted Array: " + Arrays.toString(array));
quickSort(array, 0, array.length - 1);
System.out.println(" Sorted Array: " + Arrays.toString(array));
}
public 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);
}
}
private static int partition(int[] arr, int low, int high) {
// our pivot is the middle element of the array
int middle = low + (high - low) / 2;
int pivot = arr[middle];
// Swap the pivot element with the last one to use existing logic
int temp = arr[middle];
arr[middle] = arr[high];
arr[high] = temp;
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;
}
}
This approach might be faster than using the last element as the pivot on certain datasets, especially partially sorted arrays.
Iterative QuickSort Algorithm
Java's QuickSort doesn't just dance to the recursive tune; it can groove iteratively too. Let's try implementing that version. This one uses a stack to keep track of the indexes of subarrays that need sorting.
import java.util.Arrays;
import java.util.Stack;
public class QuickSort {
static void quickSort(int[] arr, int l, int h) {
if (arr == null || arr.length == 0)
return;
if (l >= h)
return;
Stack stack = new Stack<>();
stack.push(l);
stack.push(h);
while (!stack.isEmpty()) {
h = stack.pop();
l = stack.pop();
int pivotIndex = partition(arr, l, h);
if (pivotIndex - 1 > l) {
stack.push(l);
stack.push(pivotIndex - 1);
}
if (pivotIndex + 1 < h) {
stack.push(pivotIndex + 1);
stack.push(h);
}
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
int temp = arr[i];
arr[i] = arr[high];
arr[high] = temp;
return i;
}
public static void main(String[] args) {
int[] array = {17, 14, 15, 28, 6, 8, -6, 1, 3, 18};
System.out.println("Unsorted Array: " + Arrays.toString(array));
quickSort(array, 0, array.length - 1);
System.out.println(" Sorted Array: " + Arrays.toString(array));;
}
}
The output will be the same as in the previous cases.Detailed Breakdown of the Partitioning Process
The partitioning process is the cornerstone of the Quicksort algorithm. It divides the array into two sections based on a pivot element:
- Elements smaller than the pivot are placed on the left.
- Elements greater than the pivot are placed on the right.
Here’s a step-by-step explanation of how partitioning works:
Step-by-Step Partitioning
public class QuicksortPartition {
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // Choose the last element as the pivot
int i = low - 1; // Pointer for smaller elements
for (int j = low; j < high; j++) {
// If the current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap the pivot with the element at i + 1
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // Return the partition index
}
public static void main(String[] args) {
int[] array = {10, 80, 30, 90, 40, 50, 70};
int partitionIndex = partition(array, 0, array.length - 1);
System.out.println("Partitioned Array: " + java.util.Arrays.toString(array));
System.out.println("Partition Index: " + partitionIndex);
}
}
Output:
- Partitioned Array:
[10, 30, 40, 50, 70, 90, 80]
- Partition Index:
4
In this example, the pivot is 70
, and the elements are rearranged to place all smaller elements to its left and larger ones to its right.
Quicksort on Different Data Structures
Quicksort is most commonly applied to arrays, but its implementation and performance characteristics differ when applied to other data structures like linked lists.
Quicksort on Arrays
Arrays are contiguous memory structures, making swaps and index-based access efficient. This is why Quicksort is often used with arrays.
Quicksort on Linked Lists
Linked lists have non-contiguous memory, making element swapping inefficient. Instead, Quicksort uses pointers to rearrange nodes:
class ListNode {
int value;
ListNode next;
ListNode(int value) {
this.value = value;
this.next = null;
}
}
// Implementing Quicksort for linked lists requires partitioning by rearranging pointers rather than swapping data.
Note: For linked lists, Merge Sort is often preferred due to its pointer-based operations and stable sorting behavior.
Recursive Nature and Execution Flow of Quicksort
Quicksort relies heavily on recursion to divide and conquer. Here's a step-by-step explanation of its recursive execution:
Recursive Steps
- Choose a pivot and partition the array into two sections.
- Recursively apply Quicksort to the left section.
- Recursively apply Quicksort to the right section.
Example: Recursive Implementation
public class Quicksort {
public static void quicksort(int[] arr, int low, int high) {
if (low < high) {
// Partition the array
int pi = partition(arr, low, high);
// Recursively sort the left and right sections
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
int[] array = {10, 80, 30, 90, 40, 50, 70};
quicksort(array, 0, array.length - 1);
System.out.println("Sorted Array: " + java.util.Arrays.toString(array));
}
}
Output: Sorted Array: [10, 30, 40, 50, 70, 80, 90]
Visualization of Execution
At each recursive call:
- The pivot is selected and the array is partitioned.
- Left and right sections are sorted recursively.
- The recursion terminates when the subarray has one or no elements.
GO TO FULL VERSION