{"id":11620,"date":"2023-01-10T07:01:54","date_gmt":"2023-01-10T07:01:54","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=11620"},"modified":"2023-04-17T12:39:32","modified_gmt":"2023-04-17T12:39:32","slug":"quick-sort-program-in-java","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/quick-sort-program-in-java\/","title":{"rendered":"Quick Sort Program in Java"},"content":{"rendered":"

\"\"<\/p>\n

Quick Sort program in Java has been introduced because it is an efficient sorting algorithm that can quickly sort large datasets. It has a time complexity of O(n log n) and is widely used in many programming applications.<\/p>\n

Introduction to Quick Sort Program in Java<\/h2>\n

Quick Sort program in Java is a fast and efficient sorting algorithm in Java, which works by recursively dividing and sorting sub-arrays. It selects a pivot element and then partitions the array based on whether elements are greater or lesser than the pivot.<\/p>\n

Quick Sort Algorithm in Java<\/h2>\n

Here,is the quick sort algorithm in Java. Consider the array shown below.<\/p>\n

\"\"<\/p>\n

Here, We have to partition the given array. Partitioning an array around a value pivot means that we arrange the array in such a way that the pivot is in its sorted position. And we don\u2019t consider the rest of the array. The pivot element will be at a position in which it will be if we sort an array. This means that the elements before the pivot element i.e. the elements to the left of the pivot will be smaller than the pivot and the elements after the pivot element i.e. the elements to the right of the pivot element will be larger than the pivot.<\/p>\n

For instance, consider the array shown below.<\/p>\n

\"\"<\/p>\n

Here 10 is at its sorted position. The elements to the left of the value 10 are smaller than 10 and the elements to the right of element 10 are larger than 10. Their respective order does not matter i.e. we can see that the left part is not sorted and the right part is also not sorted itself. <\/p>\n

So, let\u2019s come back to our example, we have the initial condition as shown below.<\/p>\n

\"\"<\/p>\n

The pivot value here is 5. We have assumed that the pivot will always be the last element of the array. The partitioning technique in which the last element of the array is always chosen as the pivot is called the Lomuto partition.<\/strong><\/p>\n

There are 2 pointers l and r at the top of the first element. The ticks below every element represent that all the elements are unexplored at the current moment. See, to partition the array, we have to divide the array into 2 regions, one where the elements will be smaller than the pivot and the other where the elements will be larger than the pivot. However, currently, all the elements are divided into 3 regions. <\/p>\n

The 3 regions are; greater than the pivot, less than the pivot, and unexplored elements.<\/strong> Currently, there are no elements in the first 2 regions and all the elements are in the unexplored region. As we go on and move the pointers l and r, we will keep on adding the elements to one of the first 2 regions.<\/p>\n

If the number of elements in the array is N, the following image shows the ranges of all the 3 regions.<\/p>\n

\"\"<\/p>\n

So, we have to work according to this. Let\u2019s see the first step shown below.<\/p>\n

\"\"<\/p>\n

We were at element 7 and pivot = last element = 5. So, 7 is greater than 5. We know that the region for the elements greater than the pivot is from l to r-1. So, l=0 which is correct as 7 is at index 0. However, r-1=0-1=-1. This is incorrect. So, to validate the range l to r-1, we need to move r one step forward. So, we do r++. <\/p>\n

Now r is at index 1. So, we can see that the range for the elements greater than the pivot has been satisfied. Also, the other 2 ranges have automatically been validated as the unexplored region is now from index 1 onwards and less than equal to pivot is currently a non-existing region after exploring just 1 element.<\/p>\n

With this, we have also come to the conclusion that if arr[r] > pivot, we do r++.<\/p>\n

Next, we have element 9. So, perform the same operation and r will be at index 1. (Do it yourself to get the concept clearly).<\/p>\n

Now, we are at index 2 i.e. element 4. <\/p>\n

\"\"<\/p>\n

As shown above, the previous 2 elements have now come under the >pivot region. Element 4 is, however, less than the pivot i.e. 5. So, to validate the ranges mentioned above, we will swap the elements at the l and r indices and increment both l and r as shown below.<\/p>\n

\"\"<\/p>\n

Now, we can see that the ranges are validated automatically. So, we have come to the conclusion that if arr[r] < pivot, we swap arr[l] and arr[r] and do l++ and r++.
\nSo, you can follow the same steps yourself for the remaining array. The array after r goes out of bound is shown below.<\/p>\n

\"\"<\/p>\n

So, we can see that the array has been partitioned. Throughout the partition procedure, the left pointer or l denotes the first element of the >pivot region and the right pointer or r denotes the first element of the unexplored region.<\/p>\n

Now that we have understood the complete partition procedure, let us write the code for the same.<\/p>\n

Partition Procedure Program in Java<\/h3>\n\t\t\t\t\t\t