Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Sorting is the process of organizing materials in a logical order. We humans love to simplify our work by dividing it into smaller parts. Keeping this fact in mind, people have developed computer algorithms that follow the divide and conquer principle. One of these algorithms is the Quicksort algorithm for Java used to sort the elements in an array. 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. This algorithm is a more efficient and faster sorting method. Breaking down the problem into subproblems, solving the subproblems, and then merging the results to solve the main problem is divide and conquer.

What is Quicksort in Java?

Quicksort in Java uses a divide-and-conquer strategy.

Divide: To begin, select a pivot element. After that, divide or reorganize the array into two sub-arrays such that each element in the left sub-array is less than or equal to the pivot element and each element in the right sub-array is larger than the pivot element.

Conquer: Sort two subarrays recursively with Quicksort.

Combine: Combine the arrays that have already been sorted.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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).

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.

The left and right subarrays are divided using the same approach. This process is repeated until each subarray only has one element.

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:

quickSort(arr, beg, end)

if (beg < end)

pivotIndex = partition(arr,beg, end)

quickSort(arr, beg, pivotIndex)

quickSort(arr, pivotIndex + 1, end)

partition(arr, beg, end)

set end as pivotIndex

pIndex = beg - 1

for i = beg to end-1

if arr[i] < pivot

swap arr[i] and arr[pIndex]

pIndex++

swap pivot and arr[pIndex+1]

return pIndex + 1

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)); } }

Input:

[ 9, 8, 7 , 1, 2, 0, 6, 5 ]

Output:

[0, 1, 2, 5, 6, 7, 8, 9]

Quicksort in Java complexity

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

Base Case Time Complexity

O(n logn)

Average Case Time Complexity

O(n logn)

Worst Case Time Complexity

O(n^2)

Space Complexity

O(logn)

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

QuickSort and MergeSort are both popular sorting algorithms known for their efficiency and performance. QuickSort, a divide-and-conquer algorithm, selects a pivot element, partitions the array into two subarrays, and recursively sorts each subarray. It has an average time complexity of O(n log n), making it highly efficient for large datasets. However, its worst-case time complexity can degrade to O(n^2) if the pivot selection is poor, though this scenario is rare in practice.

On the other hand, MergeSort also employs a divide-and-conquer approach but guarantees a time complexity of O(n log n) in all cases. It divides the array into halves, recursively sorts each half, and then merges the sorted halves. While MergeSort is more stable and reliable than QuickSort, it requires additional memory space for the merge step, making it less memory-efficient for large datasets.

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.

We hope that this blog has helped you enhance your knowledge regarding Quicksort in Java and if you would like to learn more, check out our articles in the code360 library. Do upvote our blog to help other ninjas grow. Happy Coding!