QUICK SORT:
Sorting is done to arrange the elements in a particular order.
There are several types of sorting techniques like :
Bubble sort, Quick sort, Insertion sort, Count sort, etc.
Let’s understand what is “Quick Sort”.
Quick sort basically uses the “Divide and Conquer” technique, which divides the entire program into small parts and then perform the required operation on each small fragment and then merge all the fragments together to form the complete list.
Quick Sort follows the above explained approach.
It first partitions the entire array around the pivot such that all the elements smaller then the pivot lie on one side of it and vice versa.
Partitioning is done by swapping the elements to do the required operation and to place the pivot in it’s correct position.
After partitioning, the recursive function is called first from 0th index till the pivot and then from the pivot index till the end.
Thus we receive the sorted array.
Above was a descriptive method. Now let’s understand the whole algorithm stepwise:
STEP 1: First find out pivot element of the array by partitioning it
Partition algorithm:
Step 1: Initialise the variable pivot, i, j to first element of the array, 0 and (array size-1) respectively.
Step 2 : Run a while loop while the value of i is less than j .
Step 3 : Inside the loop, run another loop that increments the value of i till the element at ith index is less than or equal to pivot element.
Step 4 : Now run another loop till the element at jth index is greater than pivot element and in meantime it decrements the value of j.
Step 5: Now if the value of i is less than the value of j swap the elements present at i and j index.
Step 5 : After the outer loop started in Step : 2 gets over now swap the values at index j and the first element. In doing so, we’ll get the pivot at it’s position where all the elements greater than it are on one side and smaller elements are on another side. Thus we got the pivot element at it’s accurate position.
STEP 2 : After partition got over, we’ll recursively call the quick sort function first from 0th index till the pivot element.
STEP 3: Now run the function recursively starting from index ahead of pivot till the size of array.
STEP 4 : Now after STEP3, we got the sorted array.
Following is the snippet of the java code explained above:
Partitioning the array:
Quick Sort function:
