If you are learning Java, understanding sorting algorithms is an essential step toward becoming a proficient programmer. Sorting allows you to arrange data in a meaningful order, which is crucial for tasks like displaying search results, managing databases, or processing large datasets efficiently. Quick Sort is one of the most popular sorting algorithms because it is fast and works well for most real-world scenarios.
with hands-on learning.
get the skills and confidence to land your next move.
Quick Sort uses a divide-and-conquer approach. It selects a pivot element, partitions the array around that pivot, and recursively sorts the resulting subarrays. Learning Quick Sort helps you write efficient code and introduces you to important concepts like recursion, partitioning, and algorithm optimization. In this article, we will explore multiple ways to implement Quick Sort in Java, making it easy for beginners to understand and apply.
Program 1: Quick Sort Using Recursion
This first program demonstrates the classic recursive approach to Quick Sort. It selects the last element as the pivot, partitions the array, and recursively sorts each subarray.
public class QuickSortRecursive {
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;
}
public static void main(String[] args) {
int[] numbers = {10, 7, 8, 9, 1, 5};
System.out.println("Original Array: ");
for (int num : numbers) System.out.print(num + " ");
quickSort(numbers, 0, numbers.length - 1);
System.out.println("\nSorted Array: ");
for (int num : numbers) System.out.print(num + " ");
}
}In this program, the pivot divides the array into smaller and larger elements. The recursive calls sort each partition, and the process continues until the array is completely sorted. Beginners can understand the power of recursion and how dividing a problem into smaller parts simplifies sorting.
Program 2: Quick Sort Using Iteration
Although recursion is elegant, iterative Quick Sort is sometimes preferred for very large arrays to avoid stack overflow issues. This version uses a stack to simulate the recursive calls and sorts the array using loops.
import java.util.Stack;
public class QuickSortIterative {
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public 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++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
public static void quickSortIterative(int[] arr, int l, int h) {
Stack<Integer> stack = new Stack<>();
stack.push(l);
stack.push(h);
while (!stack.isEmpty()) {
h = stack.pop();
l = stack.pop();
int p = partition(arr, l, h);
if (p - 1 > l) {
stack.push(l);
stack.push(p - 1);
}
if (p + 1 < h) {
stack.push(p + 1);
stack.push(h);
}
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 6, 9, 1, 3};
System.out.println("Original Array:");
for (int num : arr) System.out.print(num + " ");
System.out.println();
quickSortIterative(arr, 0, arr.length - 1);
System.out.println("Sorted Array:");
for (int num : arr) System.out.print(num + " ");
}
}In this iterative approach, we use a manual stack to keep track of subarrays that need to be sorted. The partition logic remains the same as in the recursive version, but the recursion is replaced by a loop that processes subarrays from the stack. Beginners can use this approach to understand how recursion works internally and how it can be replaced with iteration for efficiency.
Program 3: Quick Sort with First Element as Pivot
This variation selects the first element as the pivot. It demonstrates how pivot choice can slightly affect the sorting process and efficiency.
public class QuickSortFirstPivot {
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[low];
int i = low + 1;
int j = high;
while (true) {
while (i <= j && arr[i] <= pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
} else {
break;
}
}
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
return j;
}
public static void main(String[] args) {
int[] numbers = {4, 2, 6, 9, 3};
System.out.println("Original Array: ");
for (int num : numbers) System.out.print(num + " ");
quickSort(numbers, 0, numbers.length - 1);
System.out.println("\nSorted Array: ");
for (int num : numbers) System.out.print(num + " ");
}
}Selecting the first element as pivot introduces beginners to the idea that pivot choice can influence performance. This program is useful to demonstrate that Quick Sort is flexible while still achieving the same final sorted array.
Program 4: Quick Sort in Descending Order
Quick Sort can be modified to sort arrays in descending order. This program shows how changing the comparison logic adapts the algorithm to different needs.
public class QuickSortDescending {
public static void quickSortDescending(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSortDescending(arr, low, pi - 1);
quickSortDescending(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;
}
public static void main(String[] args) {
int[] numbers = {12, 4, 7, 19, 3};
System.out.println("Original Array: ");
for (int num : numbers) System.out.print(num + " ");
quickSortDescending(numbers, 0, numbers.length - 1);
System.out.println("\nSorted Array in Descending Order: ");
for (int num : numbers) System.out.print(num + " ");
}
}By reversing the comparison operator, the array is sorted from largest to smallest. This teaches beginners how small changes in logic can achieve different sorting orders without rewriting the entire algorithm.
Program 5: Quick Sort with Middle Element as Pivot
Using the middle element as a pivot helps avoid worst-case performance when dealing with already sorted arrays. This version demonstrates a balanced approach.
public class QuickSortMiddlePivot {
public static void quickSortMiddlePivot(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSortMiddlePivot(arr, low, pi - 1);
quickSortMiddlePivot(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int mid = low + (high - low) / 2;
int pivot = arr[mid];
int i = low;
int j = high;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
return i - 1;
}
public static void main(String[] args) {
int[] numbers = {9, 3, 7, 5, 6, 2};
System.out.println("Original Array: ");
for (int num : numbers) System.out.print(num + " ");
quickSortMiddlePivot(numbers, 0, numbers.length - 1);
System.out.println("\nSorted Array: ");
for (int num : numbers) System.out.print(num + " ");
}
}Choosing the middle element helps distribute the data more evenly during partitioning. Beginners can understand how pivot selection affects performance and learn the importance of handling edge cases in algorithms.
Program 6: Quick Sort Using Generics
Quick Sort can be implemented for generic lists in Java, allowing sorting of integers, doubles, or strings. This shows the flexibility of the algorithm.
public class QuickSortGeneric {
public static <T extends Comparable<T>> void quickSortGeneric(T[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSortGeneric(arr, low, pi - 1);
quickSortGeneric(arr, pi + 1, high);
}
}
private static <T extends Comparable<T>> int partition(T[] arr, int low, int high) {
T pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j].compareTo(pivot) < 0) {
i++;
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
T temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
String[] words = {"banana", "apple", "cherry", "date"};
System.out.println("Original Array: " + java.util.Arrays.toString(words));
quickSortGeneric(words, 0, words.length - 1);
System.out.println("Sorted Array: " + java.util.Arrays.toString(words));
}
}This generic implementation allows Quick Sort to handle multiple data types. Beginners can see how using generics makes algorithms more versatile and reusable for different scenarios.
Program 7: Quick Sort for Linked Lists
Quick Sort is not limited to arrays; it can also sort linked lists efficiently. The approach is similar: pick a pivot, partition the list, and recursively sort sublists. This is useful when working with dynamic data structures where arrays may not be ideal.
public class QuickSortLinkedList {
Node head;
Node getTail(Node node) {
while (node != null && node.next != null)
node = node.next;
return node;
}
Node partition(Node head, Node end, Node[] newHeadTail) {
Node pivot = end;
Node prev = null, cur = head, tail = pivot;
Node newHead = null, newEnd = tail;
while (cur != pivot) {
if (cur.data < pivot.data) {
if (newHead == null)
newHead = cur;
prev = cur;
cur = cur.next;
} else {
if (prev != null)
prev.next = cur.next;
Node tmp = cur.next;
cur.next = null;
tail.next = cur;
tail = cur;
cur = tmp;
}
}
if (newHead == null)
newHead = pivot;
newHeadTail[0] = newHead;
newHeadTail[1] = tail;
return pivot;
}
Node quickSortRecur(Node head, Node end) {
if (head == null || head == end)
return head;
Node[] newHeadTail = new Node[2];
Node pivot = partition(head, end, newHeadTail);
Node newHead = newHeadTail[0];
Node newEnd = newHeadTail[1];
if (newHead != pivot) {
Node tmp = newHead;
while (tmp.next != pivot)
tmp = tmp.next;
tmp.next = null;
newHead = quickSortRecur(newHead, tmp);
tmp = getTail(newHead);
tmp.next = pivot;
}
pivot.next = quickSortRecur(pivot.next, newEnd);
return newHead;
}
void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args) {
QuickSortLinkedList list = new QuickSortLinkedList();
list.head = new Node(3);
list.head.next = new Node(5);
list.head.next.next = new Node(8);
list.head.next.next.next = new Node(5);
list.head.next.next.next.next = new Node(10);
list.head.next.next.next.next.next = new Node(2);
System.out.println("Linked List before sorting:");
list.printList(list.head);
list.head = list.quickSortRecur(list.head, list.getTail(list.head));
System.out.println("\nLinked List after sorting:");
list.printList(list.head);
}
}
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}In this linked list version, the pivot helps divide the list into two sublists, which are sorted recursively and combined. This method is memory-efficient for linked lists because it doesn’t require extra arrays. Beginners can practice this to understand how Quick Sort adapts to different data structures.
Frequently Asked Questions (FAQ)
Quick Sort is widely used, but beginners often have questions about it. Here are some common queries and answers.
Q1: What is the time complexity of Quick Sort?
Quick Sort has an average time complexity of O(n log n), but in the worst case, it can be O(n²). Proper pivot selection usually avoids the worst-case scenario.
Q2: Is Quick Sort stable?
No, Quick Sort is not stable by default. Equal elements may change their relative order during sorting.
Q3: Can Quick Sort be used on linked lists?
Yes, but Merge Sort is often preferred for linked lists because it handles pointers efficiently.
Q4: How does Quick Sort compare to Merge Sort?
Quick Sort is generally faster and uses less memory, but Merge Sort guarantees O(n log n) performance and is stable.
Q5: Can Quick Sort be implemented iteratively?
Yes, iterative Quick Sort is possible using a stack to simulate recursion, useful for very large arrays.
Conclusion
Quick Sort is an essential algorithm for Java programmers. It introduces recursion, partitioning logic, and efficient problem-solving strategies. In this article, we explored multiple implementations, including recursion, descending order, different pivot selections, and generic types.
For beginners, practicing Quick Sort, experimenting with pivot choices, and sorting different data types will improve understanding and coding skills. Mastering Quick Sort provides a strong foundation for tackling more advanced programming challenges.
