Java Program for QuickSort

Why Use QuickSort Over Other Sorting Algorithms?

QuickSort is often preferred over other sorting algorithms due to its efficient time complexity, in-place sorting capability, and practical real-world performance. Compared to Bubble Sort and Insertion Sort, which have an average and worst-case time complexity of O(n²), QuickSort typically performs much faster with an average time complexity of O(n log n). Even though MergeSort also offers O(n log n) performance, QuickSort has a significant edge in terms of space efficiency. MergeSort requires additional memory for temporary arrays, while QuickSort is in-place, meaning it sorts the array without extra space.

For large datasets where memory optimization is critical, QuickSort is often the better choice. It is widely used in system libraries and real-world applications like database sorting because of its fast practical performance despite its worst-case scenario being O(n²), which can often be mitigated with optimized pivot selection techniques.

Quicksort Algorithm in Java

In this section, We will learn about Quicksort Algorithm for Java. A pivot element divides an array into subarrays (element selected from the array).

1. When dividing the array, the pivot element should be positioned so that items smaller than the pivot are kept on the left side of the pivot and elements larger than the pivot are kept on the right side of the pivot.
2. The left and right subarrays are divided using the same approach. This process is repeated until each subarray only has one element.
3. At this step, the elements have already been sorted. Finally, the elements are combined to form a sorted array.

Pseudo Code

Quicksort in Java can only be implemented quickly if a good pivot is chosen. However, determining a proper pivot . 

The following are some of the options for selecting a pivot.

• Pivots can be chosen at random, i.e., from an array of pivots.
• Pivot can be either the array's rightmost element or its leftmost element.
• As the pivot element, choose median.

Following is the Pseudo Code for Quicksort in Java:

Java Program for QuickSort

Now, we will see the Java Program for QuickSort:

• Java

Java

// Java Program for QuickSort
import java.util.Arrays;
class QuickSortClass {
 // method to find the partition position
 static int partitionPosition(int arr[], int lo, int hi) {
   // choose the rightmost element as pivot
   int pivot = arr[hi];
   // pointer for greater element
   int i = (lo - 1);
   // traversing through all elements and comparing each element with pivot
   for (int j = lo; j < hi; j++) {
       // if element smaller than pivot is found, we swap it with the greater element pointed by i
     if (arr[j] <= pivot) {
       i++;
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
     }
   }
   // swapping the pivot element with the greater element specified by i
   int temp = arr[i + 1];
   arr[i + 1] = arr[hi];
   arr[hi] = temp;
   // returning the position from where partition is done
   return (i + 1);
 }
 static void quickSortInJava(int arr[], int lo, int hi) {
   if (lo < hi) {
     // finding pivot element 
     int pi = partitionPosition(arr, lo, hi);
     // recursively calling on the left of the pivot
     quickSortInJava(arr, lo, pi - 1);
     // recursively calling on the right of the pivot
     quickSortInJava(arr, pi + 1, hi);
   }
 }
}
// Main class
class Main {
 public static void main(String args[]) {
   int[] data = { 9, 8, 7 , 1, 2, 0, 6, 5 };
   int size = data.length;
   // calling quicksort on data 
   QuickSortClass.quickSortInJava(data, 0, size - 1);
   System.out.println(Arrays.toString(data));
 }
}

You can also try this code with Online Java Compiler

Run Code

Input:

Output:

Quicksort in Java complexity

Following table shows the Time complexity and Space Complexity for QuickSort in Java: 

If you’ve come this far, don’t quit now. Try out QuickSort on Coding Ninjas Studio and get it accepted right away.

QuickSort vs MergeSort: A Detailed Comparison

When comparing QuickSort vs MergeSort, both are popular and efficient sorting algorithms, but they differ significantly in approach, performance, and use cases. Understanding these differences helps developers choose the right sorting method based on the situation.

Overview of QuickSort

QuickSort is a pivot-based sorting algorithm that follows the divide-and-conquer approach. It selects a pivot element and partitions the array into two sub-arrays: elements smaller than the pivot and elements greater than the pivot. The process is recursively applied to the sub-arrays.
QuickSort’s average time complexity is O(n log n), but in the worst case (poor pivot selection), it can degrade to O(n²). Despite this, it is widely preferred for its in-place sorting and high practical performance.

Overview of MergeSort

MergeSort is a divide-and-conquer sorting algorithm that splits the array into two halves, sorts them recursively, and then merges the sorted halves.
Unlike QuickSort, MergeSort offers a consistent time complexity of O(n log n) in all cases, making it more predictable. However, MergeSort requires O(n) auxiliary space because it uses temporary arrays during the merging process. One key advantage of MergeSort is that it is stable, meaning it preserves the order of duplicate elements.

Time Complexity

QuickSort usually performs faster in practice because its inner loops are shorter and memory accesses are more localized.

Space Complexity

• QuickSort: In-place sorting, requires only O(log n) extra space for the recursive stack.
• MergeSort: Requires O(n) extra space for merging.

Stability and Use Cases

• QuickSort is not stable, which means the order of duplicate elements may change after sorting.
• MergeSort is stable and is preferred when element order matters, such as sorting records by multiple fields.

When to Use:

• Use QuickSort when you need fast, in-place sorting and stability is not a concern (e.g., large datasets, low-memory environments).
• Use MergeSort when stability is required or when working with linked lists, where memory overhead is less of an issue.

QuickSort vs MergeSort: Pros and Cons Table

Frequently Asked Questions

How do you go about doing Quicksort in Java?

In Quicksort, we first choose a pivot, from which we make comparisons to create two partitions. The same procedure is followed for both partitions until the array has been sorted.

What exactly does Quicksort in Java imply?

Quicksort in Java implies a divide-and-conquer sorting algorithm that selects a pivot, partitions the array, and recursively sorts subarrays. It's known for its average time complexity of O(n log n).

What is the significance of the name “Quicksort”?

Quicksort is named quick because it is faster than other sorting algorithms.

Is Quicksort better than bubble sort in terms of speed?

Yes, Quicksort is generally faster than bubble sort due to its average-case time complexity of O(n log n) compared to bubble sort's O(n^2) worst-case time complexity.

Is merge sorting preferable over Quicksort in Java?

Whether merge sorting is preferable over Quicksort in Java depends on factors like stability and memory usage. Merge sort offers stable sorting and predictable performance but requires more memory.

Conclusion

In this article, we have extensively discussed Quicksort and have seen its intuition, algorithm and implementation. Quicksort in Java is a popular sorting algorithm that uses (n log n) comparisons to sort an array of n elements in the average situation.

Recommended Problems - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array