|
65
|
70
|
75
|
80
|
85
|
60
|
55
|
50
|
45
|
Sorting takes place from the pivot
value, which is the first value of the given elements, this is marked bold. The
values at the left pointer and right pointer are indicated using L
and R respectively.
|
65
|
70L
|
75
|
80
|
85
|
60
|
55
|
50
|
45R
|
Since pivot is
not yet changed the same process is continued after interchanging the values at
L and R positions
|
65
|
45
|
75
L
|
80
|
85
|
60
|
55
|
50
R
|
70
|
|
65
|
45
|
50
|
80
L
|
85
|
60
|
55
R
|
75
|
70
|
|
65
|
45
|
50
|
55
|
85
L
|
60
R
|
80
|
75
|
70
|
|
65
|
45
|
50
|
55
|
60
R
|
85
L
|
80
|
75
|
70
|
When the L and
R pointers cross each other the pivot value is interchanged with the value at
right pointer. If the pivot is changed it means that the pivot has occupied its
original position in the sorted order (shown in bold italics) and hence two
different arrays are formed, one from start of the original array to the pivot
position-1 and the other from pivot position+1 to end.
|
60 L
|
45
|
50
|
55
R
|
65
|
85 L
|
80
|
75
|
70
R
|
|
55 L
|
45
|
50
R
|
60
|
65
|
70 R
|
80
L
|
75
|
85
|
|
50 L
|
45
R
|
55
|
60
|
65
|
70
|
80
L
|
75
R
|
85
|
In the next
pass we get the sorted form of the array.
|
45
|
50
|
55
|
60
|
65
|
70
|
75
|
80
|
85
|
