This Tutorial Explains the Quicksort Algorithm in Java, its illustrations, QuickSort Implementation in Java with the help of Code Examples:
Quicksort sorting technique is widely used in software applications. Quicksort uses a divide-and-conquer strategy like merge sort.
In the quicksort algorithm, a special element called “pivot” is first selected and the array or list in question is partitioned into two subsets. The partitioned subsets may or may not be equal in size.
The partitions are such that all the elements less than the pivot element are towards the left of the pivot and the elements greater than the pivot is at the right of the pivot. The Quicksort routine recursively sorts the two sub-lists. Quicksort works efficiently and also faster even for larger arrays or lists.
- Quicksort Partition Java
- Quicksort Algorithm Java
- Pseudocode For Quick Sort
- Quicksort Implementation In Java
- Recursive Quicksort
- Iterative Quicksort
- Frequently Asked Questions
- Recommended Reading
Quicksort Partition Java
Partitioning is the key process of the Quicksort technique. So what is partitioning?
Given an array A, we choose a value x called pivot such that all the elements lesser than x are before x, and all the elements greater than x are after x.
A pivot value can be any of the following:
- The first element in the array
- The last element in the array
- The mid element in the array
- Any random element in the array
This pivot value is then placed at its proper position in the array by partitioning the array. Thus the output of the ‘partitioning’ process is the pivot value at its proper position and the elements less than pivot on the left and elements greater than a pivot at the right.
Consider the following diagram that explains the partitioning process.
The above diagram shows the process of partitioning array by repeatedly selecting the last element in the array as a pivot. At each level, note that we partition the array into two sub-arrays by placing pivot at its correct position.
Next, we list the algorithm and pseudo-code for quicksort technique that also includes partition routine.
Quicksort Algorithm Java
The general algorithm for quicksort is given below.
Given below is the pseudo-code for the quicksort technique.
Pseudocode For Quick Sort
Following is the pseudo-code for a quick sort sorting technique. Note that we have provided the pseudo-code for quicksort and partitioning routine.
Let’s see the illustration of the quicksort algorithm. Take the following array as an example. Here we have selected the last element as pivot.
As shown, the first element is labeled low and the last element is high.
As evident in the above illustration, there are two pointers, high and low that respectively point to the last and first elements of the array. Both these pointers are moved as the quicksort progresses.
When the element pointed by the low pointer becomes greater than the pivot element and element pointed by the high pointer is lesser than the pivot element, we exchange the elements pointed by the low and high pointer, and each pointer advances by 1 position.
The above steps are carried out until both the pointers cross each other in the array. Once they cross, the pivot element gets its proper position in the array. At this point, the array is partitioned and now we can sort each sub-array independently by recursively applying a quick sort algorithm to each of the sub-array.
Quicksort Implementation In Java
QuickSort technique can be implemented in Java using either recursion or iteration. In this section, we will see both of these techniques.
We know that the basic technique of quicksort illustrated above uses recursion for sorting the array. In the recursive quicksort after partitioning the array, the quicksort routine is called recursively to sort the sub-arrays.
The below Implementation demonstrates the quicksort technique using recursion.
Original Array: [4, -1, 6, 8, 0, 5, -3]
Sorted Array: [-3, -1, 0, 4, 5, 6, 8]
In iterative quicksort, we use the auxiliary stack to place intermediate parameters instead of using recursion and sort partitions.
The following Java program implements iterative quicksort.
Original Array:[3, 2, 6, -1, 9, 1, -6, 10, 5]
Sorted Array:[-6, -1, 1, 2, 3, 6, 9, 10, 5]
Frequently Asked Questions
Q #1) How does a Quicksort work?
Answer: Quicksort uses a divide and conquers strategy. Quicksort first partitions an array around a pivot element selected and generates sub-arrays that are sorted recursively.
Q #2) What is the time complexity of Quicksort?
Answer: The time complexity of quicksort on an average is O (nlogn). In the worst case, it is O (n^2) the same as the selection sort.
Q #3) Where is Quicksort used?
Answer: Quicksort is mostly used in recursive applications. Quicksort is the part of C-library. Also, almost the programming languages that use built-in sorting implement quicksort.
Q #4) What is the advantage of Quicksort?
- Quicksort is an efficient algorithm and can easily sort even a huge list of elements.
- It is in-place sort and hence does not need extra space or memory.
- It is widely used and provides an efficient way to sort data sets of any length.
Q #5) Why is Quicksort better than the merge sort?
Answer: The main reason for which the quicksort is better than the merge sort is that quicksort is in-place sorting method and does not require additional memory space. Merge sort requires additional memory for intermediate sorting.
Quicksort is considered as the best arranging calculation fundamentally as a result of its proficiency to sort even a tremendous informational collection in O (nlogn) time.
Quicksort is also an in-place sort and doesn’t require additional memory space. In this tutorial, we have seen the recursive and iterative implementation of quicksort.