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.*

- Element smaller than the element pointed to by
- 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.*

- Element greater than the element pointed to by

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.