Quick sort is the most efficient method of sorting .It uses the divide and conquer strategy to sort the elements. Quick sort divides the array of objects to be sorted into two parts, which are then sorted using the quicksort algorithm recursively. For this we choose a pivot element and arrange all elements such that all the elements in the left part are less than the pivot and all those in the right part are greater than it.
Algorithm to implement Quick Sort is as follows:
Consider array A of size n to be sorted. p is the pivot element. Index positions of the first and last element of array A are denoted by ‘first’ and ‘last’.
Initially first=0 and last=n–1.
Increment first till A[first]=p
If first < last> last then swap p with A[last] and thus the position of p is found. Pivot p is placed such that all elements to its left are less than it and all elements right to it are greater than it. Let us assume that j is the final position of p. Then A[0] to A[j–1] are less than p and A [j + 1] to A [n–1]are greater than p.
Now we consider the left part of array A i.e A[0] to A[j–1].Repeat step 1,2,3 and 4. Apply the same procedure for the right part of the array.
We continue with the above steps till no more partitions can be made for every subarray.
Algorithm
PARTITION (ARR, BEG, END, LOC)
Step1: [INITIALIZE] SET LEFT = BEG, RIGHT = END, LOC = BEG, FLAG =
Step2: Repeat Steps 3 to 6 while FLAG =
Step3: Repeat while ARR[LOC] ARR[RIGHT]SWAP ARR[LOC] with ARR[RIGHT]SET LOC = RIGHT[END OF IF]
Step4: IF FLAG = 0Repeat while ARR[LOC] >= ARR[LEFT] AND LOC != LEFTSET LEFT = LEFT + 1[END OF LOOP]
Step5:IF LOC = LEFTSET FLAG = 1ELSE IF ARR[LOC] < ARR[LEFT]SWAP ARR[LOC] with ARR[LEFT]SET LOC = LEFT[END OF IF][END OF IF]
Step6: [END OF LOOP]
Step7: END
QUICK_SORT (ARR, BEG, END)
Step 1: IF (BEG < END) CALL PARTITION (ARR, BEG, END, LOC) CALL QUICKSORT(ARR, BEG, LOC – 1) CALL QUICKSORT(ARR, LOC + 1, END) [END OF IF]
Step2: END
Interested in learning about similar topics? Here are a few hand-picked blogs for you!