How to write a Quick Sort program in Java ?

By | July 21, 2020

In this post, we will learn How to write a quicksort program in Java.

Quicksort is usually considered the fastest in-memory sorting algorithm in most of the situations. Just like Merge sort, It is also a divide and conquer algorithm. which works on the idea to partition the large list into smaller lists around a chosen value (pivot) so that all the smaller values than the pivot value are on the left and all the higher values than the pivot value are on the right. Quicksort then recursively sorts the list with smaller values and the list with higher values by further partitioning it around a pivot.

Steps to implement the quicksort are as follows-

First chose a pivot value (it must be one of the elements from the list that has to sort).

Partition the list in such a way that all the elements having a value less than the pivot value come before the pivot and all the elements having a value higher than the pivot value come after the pivot. After this partitioning is done pivot value is at its final position.

Finally, we call recursively the above steps separately for the smaller element list and for the higher element list.

We can choose any random value as the pivot while implementing a quick sort like.

  1. The first element in the list as a pivot.
  2. Last element in the list as a pivot
  3. A middle element as pivot.
  4. Median of the items being sorted.

 Understanding the quicksort program

In the program, we have a quickSort method which is called recursively with the two arrays. One sub-array contains the elements smaller than the pivot and another sub-array contains the elements greater than the pivot. To partition the elements, we have a partition method.

To swap the elements we will start at both ends of the array. From the left, we move towards right looking for an element greater than pivot value, and from the right, we move towards left looking for an element smaller than the pivot.

Complete Source Code:

The output of this program:

Original input Array:[50, 25, 92, 16, 76, 30, 43, 54, 19]
Array Sorted After Quick Sort:[16, 19, 25, 30, 43, 50, 54, 76, 92]

Performance of quicksort:

The average time complexity of quicksort is O(n log n). In the worst case, it can be O(n2). Every recursive call required its own stack space so space complexity of quicksort is O(n).

You May Also Like :

What is Sorting and why is Sorting Necessary?
Classification of Sorting Algorithms
Java program for Bubble Sort using Iterative Approach
Java program for Bubble Sort using recursive Approach
How to Write a Java program for Selection Sort in Java
How to Write a Java program for Insertion Sort in java?
How to write a Merge sort program in Java
How to write a Radix sort program in Java
Tree Sort Using Binary Search Tree in Java

That’s all about How to write a Quick Sort program in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply

Your email address will not be published. Required fields are marked *