Quick Sort in Java
Quick Sort in Java
In this article, we will explore Quick Sort in Java. We’ll understand how it works, analyze its performance, and implement it step by step using clear explanations and working code examples.
Sorting is a fundamental operation in computer science and plays a key role in improving the efficiency of searching and other operations. It is especially suitable for large datasets and often outperforms other sorting methods like Bubble Sort and Insertion Sort.
What is Quick Sort in Java?
Quick Sort is a divide and conquer sorting algorithm. It works by selecting a pivot element from the array and partitioning the other elements into two sub arrays:
- Elements less than the pivot go to the left.
- Elements greater than the pivot go to the right.
- Process is repeated recursively for both sub arrays until the entire array is sorted.
Quick Sort is an in-place sorting algorithm, which means it does not require extra space proportional to input size, making it memory-efficient.
1. Best Case: O (n log n)
2. Average Case: O(n log n)
3. Worst Case: O(n2)
- Best and average cases occur when the pivot divides the array into two roughly equal parts.
- Worst case occurs when the smallest or largest element is always chosen as the pivot, resulting in unbalanced partitions.
In place sorting, no extra array used for sorting.
Quick Sort Algorithm:
Let’s break the Quick Sort algorithm into simple steps using an example array:
Example: Array: [8, 4, 7, 3, 10, 2]
Step 1: Choose Pivot
Select a pivot element. Typically:
First element
Last element (we’ll use this)
Median or random (for better average case performance)
Let’s choose the last element as pivot → pivot = 2.
Step 2: Partitioning
Rearrange the array so that:
All elements less than pivot come before it.
All elements greater than pivot come after it.
We use two pointers:
i keeps track of the position where the smaller element should go.
j traverses from the start to one before the pivot.
Step 3: Recursively Apply to Subarrays
Apply the same steps to subarrays:
Left of pivot.
Right of pivot.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Implementation of Quick Sort in Java
Function Quick Sort Algorithm:
function quickSort(arr, low, high)
if low < high:
pivotIndex = partition(arr, low, high)
quickSort(arr, low, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, high)
function partition(arr, low, high)
pivot = arr[high]
i = low - 1
for j = low to high - 1:
if arr[j] < pivot:
i++
swap arr[i] and arr[j]
swap arr[i + 1] and arr[high]
return i + 1
Java Code for Quick Sort Implementation
public class QuickSortExample {
// Function to perform Quick Sort
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// Partition the array and get the pivot index
int pivotIndex = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
// Function to partition the array
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // Choosing the last element as pivot
int i = low - 1; // Index of smaller element
for (int j = low; j < high; j++) {
// If 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 element with the element at i+1 position
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // Return the partitioning index
}
// Utility function to print the array
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
// Main method to test the code
public static void main(String[] args) {
int[] array = {8, 4, 7, 3, 10, 2};
System.out.println("Original Array:");
printArray(array);
quickSort(array, 0, array.length - 1);
System.out.println("Sorted Array:");
printArray(array);
}
}
8 4 7 3 10 2
Sorted Array:
2 3 4 7 8 10
Conclusion
Quick Sort is one of the most powerful and widely used sorting algorithms due to its efficiency on large datasets and its in-place nature. While its worst case performance is O(n²), it can be optimized using better pivot selection strategies like randomized pivot or median of three.
- Quick Sort is based on divide and conquer.
- Partitioning is the key step.
- It sorts in-place with O(log n) space complexity.
- It is faster than bubble sort, insertion sort, and sometimes even merge sort for average cases.
Understanding Quick Sort not only helps in writing better sorting logic but also strengthens your fundamentals in recursion and algorithm optimization.
FAQ's related to Quick Sort in Java
Answer:
Quick Sort is faster because it reduces the problem size significantly with each recursive call through partitioning. Unlike Bubble or Insertion Sort, which make multiple passes through the entire array, Quick Sort partitions the array into smaller subarrays and sorts them independently, leading to an average time complexity of O(n log n).
Answer:
Quick Sort performs worst when the pivot selection results in highly unbalanced partitions (e.g., already sorted arrays and always choosing the first or last element as pivot). This leads to O(n²) time complexity.
To avoid this:
- Use a randomized pivot
- Use the median-of-three technique to choose a better pivot
Answer:
- No, Quick Sort is not stable by default. Stability means equal elements retain their original order after sorting. Since Quick Sort may swap distant elements during partitioning, it does not guarantee this behavior.
- For applications requiring stability, consider Merge Sort or implement a custom stable version of Quick Sort.
Answer:
No extra array is used for sorting, so it’s considered in-place. However, it uses the call stack for recursion, which takes O(log n) space in the best and average cases, and O(n) in the worst case.
Answer:
Yes, Quick Sort can be adapted to sort objects (like arrays of custom classes) using comparators. You just need to define the comparison logic using either Comparable or Comparator interfaces to guide the partitioning process.
Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment