Quick sort is a sorting algorithm which use the idea of Divide and Conquer. This algorithm finds one element from array and name it pivot element,that divide the array in two parts in such a way that elements on left side are less than pivot element and elements on right side greater than pivot element and pivot point is at its exact location.
This is recursive algorithm. Suppose variable beg and end represent the first and last element of the array respectively, the quick sort can be defined recursively as following
if ( beg < end) then
Find element that partition the array into two halves
Quicksort the left half
Quicksort the right half
endif
The algorithm work as following , set the index of first element as loc and left variables and index of the last element of array to right variable.
Then processed as following:
- The array is scanned from right to left, comparing each element on the way with the element pointed to by loc , till either
- Element smaller than the element pointed to by loc is found. in this case , the element are interchanged and procedure continue with step 2
- If the value of the right variables becomes equal to the value of loc , the procedure terminates here. This condition indicates that the element is placed in its final position loc.
- The array is scanned from left to right, comparing each element on the way with the element pointed to by loc , till either
- Element greater than the element pointed to by loc is found. in this case , the element are interchanged and procedure continue with step 1.
- If the value of the left variables becomes equal to the value of loc , the procedure terminates here. This condition indicates that the element is placed in its final position loc.
As this procedure terminates, the first element,pivot,of original the array will be placed at loc ,its final location in the sorted array . the elements to left of it will be less than this element and elements to its right will be greater than this element.
Consider the following example to understand the concept of Quick Sort
We have array a having 6 element
Here the pivot element is 25. loc = 0, left = 0 , right = 5, as following
Start Scanning element from right . Since a[loc]<a[right], we decrease the value of variable right to get value where a[loc]>a[right] and that is a[4], interchange these element
Now start scanning from left,Since a[loc]>a[left] , we increase the value of variable to get value greater than a[loc] and that will be a[2], so interchange it
Start Scanning element from right . Since a[loc]<a[right], we decrease the value of variable right to get value where a[loc]>a[right] and that is a[3], interchange these elements
Now start scanning from left,Since a[loc]>a[left] , we increase the value of variable to get value greater than a[loc] and since left is equal to loc
This indicate the termination of procedure The element 25 is placed at right position and it divide the array into two sub array as
As we can see elements in left sub array are less than 25 and elements in right sub array are greater than 25.
Complexity
