## Quick Sort Method Download Algorithm & Program

Quick Sort method is an efficient sorting method for larger List. It works fine for the list having large number of elements. It uses Divide and conquers strategy in which a list is divided into two smaller lists.
First initialize LOW with index of the first element and HIGH with index of last element.
Now find the pivot element from the list of elements using the equation:
PIVOT = (LOW + HIGH) / 2
Now we scan elements from left to right and compare each element with PIVOT element. If the scanned element is less then the PIVOT element we scan next element and increment the value of LOW. Repeat same procedure until we found the element which is greater then the PIVOT element.
Now we scan elements from right to left and compare each element with PIVOT element. If the scanned element is greater then the PIVOT element we scan next element and decrement the value of HIGH. Repeat same procedure until we found the element which is less then the PIVOT element.
Now we compare the value of LOW and HIGH. If LOW is less then HIGH then we interchange the element which are at the index LOW and HIGH.
Increment the value of LOW and decrement the value of HIGH. Repeat above procedure while value of LOW less then or equal to value of HIGH.
After the completion of first PASS the entire list of elements is divided in to two lists. First list contains elements which are less then the PIVOT element and second list contains elements which are greater then the PIVOT element.
The above procedure is recursively repeated for the sub lists until all the elements in the lists are sorted.
The order of comparison for this method is o (nlogn)

Example of Quick Sort:

 Element 5 2 35 9 3 -2 52 0 Index 0 1 2 3 4 5 6 7
Pass 1:
 Low High Pivot 0 7 (0+7)/2=3.5=3
 Index 0 1 2 3 4 5 6 7 5 2 35 9p 3 -2 52 0 5 2 0 9p 3 -2 52 35 5 2 0 -2 3 9p 52 35 List1 List2

Now List is Partitioned in two Sub Lists. List1 Consist of elements having value less than PIVOT element and List2 consist of elements having value greater than PIVOT element. Now Repeat Same Process first for List1 and then for List2.
Pass 2:

 Low High Pivot 0 4 (0+4)/2=2
 List 1 List 2 Index 0 1 2 3 4 5 6 7 5 2 0p -2 3 9 52 35 -2 2 0p 5 3 9 52 35 -2 0p 2 5 3 9 52 35 List1.1 List1.2 List 2

Now List 1 is partitioned in two Sub Lists. List 1.1 Consist of elements having value less than PIVOT element 0 and List 1.2 consist of elements having value greater than PIVOT element 0. Now Repeat same Process for List 1.2.
Pass 3:

 Low High Pivot 2 4 (2+4)/2=6/2=3
 List1.1 List 1.2 List 2 Index 0 1 2 3 4 5 6 7 -2 0 2 5p 3 9 52 35 -2 0 2 3 5p 9 52 35

Now Repeat Same Process for List 2.
Pass 4:

 Low High Pivot 6 7 (6+7)/2=13/2=6.5=6
 List1.1 List 1.2 List 2 Index 0 1 2 3 4 5 6 7 -2 0 2 3 5 9 52p 35 -2 0 2 3 5 9 35 52p Download Algorithm & Program