Quick Sort Method


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 Projects


Download Programs