Jkoder.com Tutorials, Tips and interview questions for Java, J2EE, Android, Spring, Hibernate, Javascript and other languages for software developers
What is Quick sort and usage of Quick sort in JAVA Arrays.sort method
As per JDK-8 Arrays.sort method uses Quick sort algorithm for sorting of data in ascending/descending order. So this post is for persons who wants to know, how does Quick sort works.
In JAVA world quick sorting is used to sort an array. In our example we will sort an array of integers in ascending order. Before we start lets understand the basic principle of Quick sort algorithm. “Pivot” is an item that is used to compare to every other item in the array. Move all the items that are smaller than pivot to the left of the pivot, and the items that are greater than the pivot are moved to the right of the pivot. So, the pivot actually partitions the array into 2 parts left partition and right partition. Now the same funda is applied recursively in the left and right partition till only one item is in left partition and in right partition.
Let’s apply this principle in the below example.
| 17 | 41 | 5 | 22 | 54 | 6 | 29 | 3 | 13 |
You are free to choose your pivot randomly. In our case I choose the rightmost item i.e. 13
We are gonna sort the items from index 0 to 7 by comparing to the pivot. So, assume that our pointers are at index 0 and at index 7.
Is 17>pivot? yes it is. Is 3<pivot? yes it is. Since 17 is larger than the pivot and 3 is smaller than the pivot, so we swap them.
| 3 | 41 | 5 | 22 | 54 | 6 | 29 | 17 | 13 |
Now move the pointers one step. So now our pointers are at index 1 and 6.
Is 41>pivot? yes it is. Is 29< pivot? no. So move the right most pointer from index 6 to index 5. note that our left most point is still at index 1. Is 6<pivot? yes its is. So swap values at index 5 and 1.
| 3 | 6 | 5 | 22 | 54 | 41 | 29 | 17 | 13 |
Now move the pointers one step. So now our pointers are at index 2 and 4. Note that our both pointers are moving to the center. Is 5>pivot? no its not. Move the left most pointer to next index. So, our pointers are at index 3 and 4. Is 54<pivot? no its not. Move the right most pointer to next index. Here, left most pointer and right most pointer are both at index 3. At this point we are done with 1 level of sorting with 13 as pivot. So, we swap the pivot with the value index where left most and right most pointers meet.
| 3 | 6 | 5 | 13 | 54 | 41 | 29 | 17 | 22 |
So, we know that the values to the left of 13 are smaller than 13, and the values to the right of 13 are greater than 13. So 13 is at the correct place. Now 13 has divided the array into left partition and right partition. Now, apply quick sort on these 2 partitions recursively. We will start with the left partition.
So, we know that the values to the left of 13 are smaller than 13, and the values to the right of 13 are greater than 13. So 13 is at the correct place. Now 13 has divided the array into left partition and right partition. Now, apply quick sort on these 2 partitions recursively. We will start with the left partition.
Consider right most item as the pivot which is 5. And our left most pointer is at index 0 and right most pointer is at index 1. Is 3>pivot? no its not. move the left most pointer to one step. So, our pointers meet at index 1. So swap the value at index 1 with the pivot.
| 3 | 5 | 6 | 13 | 54 | 41 | 29 | 17 | 22 |
Now, items to the left of 5 is smaller then 5 and items to the right of 5 is greater than 5. And, since there only one-one items to the left and right of 5 , so this sub group is already sorted.
But, still we have 5 items on the right of 13 to sort. So, lets apply quick sort on it as well. Choose right most item as pivot which is 22. And, the left most pointer is at index 4 and right most pointer is at index 7. Is 54>pivot? yes it is. Is 17<pivot? yes it is. So, swap 54 and 17.
| 3 | 5 | 6 | 13 | 17 | 41 | 29 | 54 | 22 |
Is 41>pivot? yes it is. Is 29<pivot? no its not. Move the right most pointer to next step, and it meets with the left most pointer at index 5. So swap the pivot with the value at this index.
| 3 | 5 | 6 | 13 | 17 | 22 | 29 | 54 | 41 |
Now all the items to the left of 22 is smaller than 22 and all the items to the right of 22 are greater than 22. Since 17 is the only item to the left of 22 in this sub group, so consider it sorted. Now we need to sort the right most items of 22. Choose the pivot of this sub group which is 41. Left most pointer will be at index 6 and right most pointer will at index 7. Is 29>pivot? no its not. Move the left most pointer to next index. Now, both the pointers are at the same index. So, swap the value at this index with pivot(41).
Now in this sub group we have one item to the left of 41 and one item to the right of 41. So no further sorting is required.
That’s it, array is fully sorted now. That in a nutshell is how quick sort works.
Quick sort is based on divide and conquer algorithm, its efficient for large data sets. In JAVA Arrays.sort uses Quick sort algorithm to sort the items in array. Quick sort has the advantage of being completely in place, so it does not require any additional storage. As against merge sort it is not stable.If you are required to sort an array of primitives use Quick sort(Arrays.sort method). If you need to sort list of objects use Merge sort(Collections.sort method).
| 3 | 5 | 6 | 13 | 17 | 22 | 29 | 41 | 54 |
