Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Quicksort in Java?
3.
Quicksort Algorithm in Java
4.
Pseudo Code
5.
Java Program for QuickSort
5.1.
Java
6.
Quicksort in Java complexity
7.
QuickSort vs MergeSort
8.
Frequently Asked Questions
8.1.
How do you go about doing Quicksort in Java?
8.2.
What exactly does Quicksort in Java imply?
8.3.
What is the significance of the name “Quicksort”?
8.4.
Is Quicksort better than bubble sort in terms of speed?
8.5.
Is merge sorting preferable over Quicksort in Java?
9.
Conclusion
Last Updated: May 5, 2024
Easy

Java Program for QuickSort

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
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.

Java Program for QuickSort

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

  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:

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 ComplexityO(n logn)
Average Case Time ComplexityO(n logn)
Worst Case Time ComplexityO(n^2)
Space ComplexityO(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.

Recommended Problems - 


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!

Previous article
Selection Sort in C, C++, Java, Python & C#
Next article
Quick Sort Algorithm
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass