Quicksort algorithm is one of the most used sorting algorithm, especially to sort large list and most of the programming languages, library have implemented it in one or another way. In Java, Arrays.sort() method sorts primitive data types using double pivot Quicksort algorithm, authored by Joshua Bloach and others. This implementation provides better performance for lot of data sets, where traditional quicksort algorithm reduced into quadratic performance. This method also uses MergeSort, another good sorting algorithm, to sort objects. QuickSort implementations are also available in C++ STL library. Have you ever thought

###

Quicksort is a divide and conquer algorithm, which means original list is divided into multiple list, each of them is sorted individually and then sorted output is merged to produce the sorted list. Here is step by step explanation of how quicksort algorithm works.

Steps to implement Quick sort algorithm in place:

1) Choose an element, called pivot, from the list or array. Generally pivot is the middle element of array.

2) Reorder the list so that all elements with values less than the pivot come before the pivot, and all elements with values greater than the pivot come after it (equal values can go either way). This is also known as

3) Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values. If the array contains only one element or zero elements then the array is sorted.

Following GIF image will help you to understand working of Quick sort algorithm little better. In this image we have an array of integers which is not sorted and we need to sort them in ascending order. Our array is {6, 5, 3, 1, 8, 7, 2, 4} and we first choose 3 as pivot. Now partitioning starts and we pick 6 on left side of side, because its greater than 3. Now on right side, we leave 4 because its greater than 3, and pick 2 for swapping with 6. After swapping our list look like {2, 5, 3, 1, 8, 7, 6, 4}. Now we pick 5 on left side, and 1 on right side because it's greater than 3 and swap them again. Now, our array looks like {2, 1, 3, 5, 8, 7, 6, 4}. Since we are done with all elements with respect to 3 as pivot, we can now take the sub-array at left side of 3 and apply same procedure. This will sort the left array. Now on right side, we choose 4 as pivot, and repeat same procedure, which result in 4 swapped against 5. Now we take right side again with 6 as pivot and apply same procedure.

###

Here is a Java program to sort an array of integers using QuickSort algorithm. It is an in-place, recursive implementation of QuickSort. Logic is encapsulated in QuickSort class, and method quickSort(int low, int high). This method is called recursively to sort the array. This algorithm work exactly as explained in above GIF image, so if you understand the logic there, its very easy to write by your own.

###

Now we know how quick sort works and how to implement quicksort in Java, its time to revise some of the important points about this popular sorting algorithm.

1) QuickSort is a divide and conquer algorithm. Large list is divided into two and sorted separately (conquered), sorted list is merge later.

2) On "in-place" implementation of quick sort, list is sorted using same array, no additional array is required. Numbers are re-arranged pivot, also known as partitioning.

3) Partitioning happen around pivot, which is usually middle element of array.

4) Average case time complexity of Quicksort is O(n log n) and worst case time complexity is O(n ^2), which makes it one of the fasted sorting algorithm. Interesting thing is it's worst case performance is equal to Bubble Sort :)

5) Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during the recursion.

6) Quicksort is also a good example of algorithm which makes best use of CPU caches, because of it's divide and conquer nature.

7) In Java, Arrays.sort() method uses quick sort algorithm to sort array of primitives. It's different than our algorithm, and uses two pivots. Good thing is that it perform much better than most of the quicksort algorithm available on internet for different data sets, where traditional quick sort perform poorly. One more reason, not to reinvent the wheel but to use the library method, when it comes to write production code.

That's all about

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

*why quicksort is so popular?*because on average it is one of the fastest sorting algorithm we have. On average quicksort is a O(n log n) algorithm, while it's worst case is O(n^2), which is much better comparing with Bubble Sort or Insertion Sort. It's also one of the popular algorithm interview question, so as a programmer you must know*how QuickSort works as well*as*how to implement Quicksort in Java*or any other programming language. One of the most important thing interviewer look in your quicksort implementation is choice of pivot and whether you are sorting in place or not. In "*in-place"*sorting, actual sorting takes place in same array and no additional space is needed. Due to this reason, quicksort is very efficient in sorting large list of numbers, as no additional memory is required, a very space efficient sorting algorithm. Quicksort is also one of the naturally recursive algorithm and serves a good exercise for Java programmers to master art of recursion.###
__How QuickSort Algorithm works__

Quicksort is a divide and conquer algorithm, which means original list is divided into multiple list, each of them is sorted individually and then sorted output is merged to produce the sorted list. Here is step by step explanation of how quicksort algorithm works.Steps to implement Quick sort algorithm in place:

1) Choose an element, called pivot, from the list or array. Generally pivot is the middle element of array.

2) Reorder the list so that all elements with values less than the pivot come before the pivot, and all elements with values greater than the pivot come after it (equal values can go either way). This is also known as

*partitioning*. After partitioning the pivot is in its final position.3) Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values. If the array contains only one element or zero elements then the array is sorted.

Following GIF image will help you to understand working of Quick sort algorithm little better. In this image we have an array of integers which is not sorted and we need to sort them in ascending order. Our array is {6, 5, 3, 1, 8, 7, 2, 4} and we first choose 3 as pivot. Now partitioning starts and we pick 6 on left side of side, because its greater than 3. Now on right side, we leave 4 because its greater than 3, and pick 2 for swapping with 6. After swapping our list look like {2, 5, 3, 1, 8, 7, 6, 4}. Now we pick 5 on left side, and 1 on right side because it's greater than 3 and swap them again. Now, our array looks like {2, 1, 3, 5, 8, 7, 6, 4}. Since we are done with all elements with respect to 3 as pivot, we can now take the sub-array at left side of 3 and apply same procedure. This will sort the left array. Now on right side, we choose 4 as pivot, and repeat same procedure, which result in 4 swapped against 5. Now we take right side again with 6 as pivot and apply same procedure.

__Sorting an array of integer using QuickSort sorting algorithm__###
__Java Program to implement QuickSort Algorithm__

Here is a Java program to sort an array of integers using QuickSort algorithm. It is an in-place, recursive implementation of QuickSort. Logic is encapsulated in QuickSort class, and method quickSort(int low, int high). This method is called recursively to sort the array. This algorithm work exactly as explained in above GIF image, so if you understand the logic there, its very easy to write by your own.import java.util.Arrays; /** * Test class to sort array of integers using Quicksort algorithm in Java. * @author Javin Paul */ public class QuickSortDemo{ public static void main(String args[]) { // unsorted integer array int[] unsorted = {6, 5, 3, 1, 8, 7, 2, 4}; System.out.println("Unsorted array :" + Arrays.toString(unsorted)); QuickSort algorithm = new QuickSort(); // sorting integer array using quicksort algorithm algorithm.sort(unsorted); // printing sorted array System.out.println("Sorted array :" + Arrays.toString(unsorted)); } } /** * Java Program sort numbers using QuickSort Algorithm. QuickSort is a divide * and conquer algorithm, which divides the original list, sort it and then * merge it to create sorted output. * * @author Javin Paul */ class QuickSort { private int input[]; private int length; public void sort(int[] numbers) { if (numbers == null || numbers.length == 0) { return; } this.input = numbers; length = numbers.length; quickSort(0, length - 1); } /* * This method implements in-place quicksort algorithm recursively. */ private void quickSort(int low, int high) { int i = low; int j = high; // pivot is middle index int pivot = input[low + (high - low) / 2]; // Divide into two arrays while (i <= j) { /** * As shown in above image, In each iteration, we will identify a * number from left side which is greater then the pivot value, and * a number from right side which is less then the pivot value. Once * search is complete, we can swap both numbers. */ while (input[i] < pivot) { i++; } while (input[j] > pivot) { j--; } if (i <= j) { swap(i, j); // move index to next position on both sides i++; j--; } } // calls quickSort() method recursively if (low < j) { quickSort(low, j); } if (i < high) { quickSort(i, high); } } private void swap(int i, int j) { int temp = input[i]; input[i] = input[j]; input[j] = temp; } } Output : Unsorted array :[6, 5, 3, 1, 8, 7, 2, 4] Sorted array :[1, 2, 3, 4, 5, 6, 7, 8]

###
__Import points about Quicksort algorithm__

Now we know how quick sort works and how to implement quicksort in Java, its time to revise some of the important points about this popular sorting algorithm.1) QuickSort is a divide and conquer algorithm. Large list is divided into two and sorted separately (conquered), sorted list is merge later.

2) On "in-place" implementation of quick sort, list is sorted using same array, no additional array is required. Numbers are re-arranged pivot, also known as partitioning.

3) Partitioning happen around pivot, which is usually middle element of array.

4) Average case time complexity of Quicksort is O(n log n) and worst case time complexity is O(n ^2), which makes it one of the fasted sorting algorithm. Interesting thing is it's worst case performance is equal to Bubble Sort :)

5) Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during the recursion.

6) Quicksort is also a good example of algorithm which makes best use of CPU caches, because of it's divide and conquer nature.

7) In Java, Arrays.sort() method uses quick sort algorithm to sort array of primitives. It's different than our algorithm, and uses two pivots. Good thing is that it perform much better than most of the quicksort algorithm available on internet for different data sets, where traditional quick sort perform poorly. One more reason, not to reinvent the wheel but to use the library method, when it comes to write production code.

That's all about

**Quicksort sorting algorithm in Java**. It is one of the must know algorithm for all level of Java programmers, not that you need it often to implement it but to do well on interviews and use the lesson learned while implementing quick sort in Java. In our example, we have implemented quicksort "in-place", which is what you should do if asked to write quicksort in Java. Remember as Java programmer, you don't need to write your own implementation as library implementation are much better implemented and tested. You should use Arrays.sort() method to sort your array instead of writing your own sort method. One more reason of using library method is that they are usually improved over different version, and can take advantage of new machine instructions or native improvement.**Further Learning**Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

## 11 comments :

Hello Javin, nice article, I have been waiting for this ever since someone asked me following question :

Explain why recursive implementation of QuickSort will require O(log n) of additional space?

I have gone through the article, but not clear about how much additional space recursive implementation of quicksort is taking, could you please explain that in detail?

What is meaning of "double pivot" quick sort algorithm? Can you please elaborate how it perform better with classical Quicksort algo with just one pivot? an example would be great.

please refer this link

https://www.youtube.com/watch?v=3DV8GO9g7B4&list=PLEbnTDJUr_IeHYw_sfBOJ6gk5pie0yP-0&index=9&nohtml5=False

Hi Javin,

It's nice:

if ( i <= j ) {

i++;

j--;

}

This makes slower the running time. Am I right?

public void quickSort(int[] arr, int p, int r){

if(p < r) {

int q = partition(arr, p, r);

quickSort(arr, p, q-1);

quickSort(arr, q+1, r);

}

}

public int partition(int arr[], int p, int r)

{

int i = p-1;

int pivot = arr[r];

for (int j = p; j <= r; j++) {

if(arr[j] <= pivot){

i++;

//do the swap

if(i!=j){

arr[i] = arr[i] ^ arr[j];

arr[j] = arr[i] ^ arr[j];

arr[i] = arr[i] ^ arr[j];

}

}

}

return i;

}

Does anyone tried to run the program.

Its not working.

@Unknown, what is the error your are getting?

@Javin paul swapping condition to be (i < j) not the (i<=j) . getting wrong result if we sort 1 3 4 8 7 6 5 2

tried with input 10, 30, 80, 90, 40, 50, 70 but it dint worked. even after sravan's change

@sravan chitari the program is working

Hello guys, one of my reader Tomasz has some interesting insight about in-place quicksort algorithms which he mailed to me. I am reposting here for everyones benefit:

- if you would like to achieve O(log n) extra memory bound, you need to be more careful with the recursion: the simple trick is to use recursion only to the smaller

subinterval out of [low, j] and [i, high] and sort bigger interval on the same recursion level (use sth like tail recursion https://en.wikipedia.org/wiki/Tail_call).

Without that trick the algorithm could take O(n) extra memory.

- technically speaking any algorithm that use Omega(1) extra memory is not in-place. This kind of implementation of quick-sort use O(log n) extra memory (recursion stack clearly counts as extra memory). In practice there is no difference between O(1) and O(log n), but if you would like to be strict it is worth to mention the difference.

Once again thanks to Tomasz for his input.

## Post a Comment