The idea of quicksort is simple enough where you chose a pivot and arrange the elements so that each element bigger than the pivot is on its right and smaller is on its left. At this point the pivot in theory is in its final sorted position. We then take all the elements on the left and create a new array and perform the same operation. Similarly we do the same to all the elements on the right of the pivot. Eventually we reach the last element and the array is sorted and we copy them back in their ordered form.
So how does the algorithm work in detail? The first step is to decide how the pivot is chosen. In this example I will simply use the last element in the current partition as the pivot however there are other techniques such as median of three and random. The importance of choosing the pivot will be clear later however because it does make a difference to the worst case running time. Once the pivot is selected we will swap it with the element at the beginning of the array and then we can start testing. We have a left index indexing the beginning of the array but to the element after the pivot. We also have a right index that indexes the last element of the array. After this we first increment the left index and compare each element until it is at an element that is bigger than the pivot. We then start decrementing the right index and comparing each element it is indexing until it reaches an element smaller than the pivot. At this point we swap the elements pointed to by the left and right indices with each other. This step is repeated until the left index is bigger than the right index at which point we know the pivot is in the right place. We then swap the pivot with the element pointed to by the right index. Here is a small scale example with 5 elements.
Array "q"
initial. Pivot = 5 at index 4.
6 3 1 2 5:
5 3 1 2 6: Swapped pivot with first element. Pivot 5 is now at index 0.
left index l = 1, right index r = 4. (Zero index based).
Start:
q[l] > q[pivot]? no. l = 1 + 1 = 2.
q[l] > q[pivot]? no. l = 2 + 1 = 3.
q[l] > q[pivot]? no. l = 3 + 1 = 4
q[l] > q[pivot]? yes, stop.
q[r] > q[pivot]? yes. r = 4 -1 = 3.
left index is bigger than right index, swap q[r] with q[pivot]:
2 3 1 5 6.
Pivot 5 is now in its final position, so now we partition.
Left side 5 Right side
2 3 1 6
Pivot = 1 at index 2. One element so
already sorted.
"q" = new array.
1 3 2: Swapped pivot with first element. Pivot 1 is now at index 0.
l = 1, r = 2.
Start:
q[l] > q[pivot]? yes, stop.
q[r] > q[pivot]? yes. r = 2 -1 = 1.
q[r] > q[pivot]? yes. r = 1 -1 = 0.
left index is bigger than right index, swap q[r] with q[pivot]:
1 3 2: no change because r = pivot index.
Pivot 1 is now in its final position, so now we partition:
1 Left Right 5 6
none 3 2
"q" = new array 3 2.
Pivot = 2 at index 1.
3 2 Swap Pivot with first element. Pivot 2 is now at index 0.
2 3
l = 1, r = 1.
Start.
q[l] > q[pivot]? yes, stop.
q[r] > q[pivot]? yes. r = 1 -1 = 0.
left index is bigger than right index, swap q[r] with q[pivot]:
2 3: no change because r = pivot index.
Pivot 2 is now in its final position so now we partition:
1 2 Left side Right side 5 6
None 3
One element so
already sorted.
Final:
1 2 3 5 6
As you can see from the above step-through of a short array it is a lot of work on paper however thankfully the running time is more forgiving. Quicksort average case is O(n log n) and worst case of O(n^2). Worst case running time occurs when the array is either sorted or reverse sorted however we can improve this as mentioned earlier by changing the way we choose the pivot and the way we use the pivot. To develop this into code, a careful analysis indicates we need 5 methods.
QuickSort: Passes an array and initial condition to QuckSortAlgorithm
QuickSortAlgorithm: Performs the QuickSort Division and Partitioning
Partition: Performs the Quicksort operation on the partition.
GetPivot: Returns the pivot position of the chosen pivot and after moving it to front of array.
Swap: Swaps two elements in an array.
Swap method has already been explained on the main page.
The code for the QuickSort method:
public void QuickSort(ref int[] array)The code for the QuickSortAlgorithm method:
{
QuickSortAlgorithm(ref array, 0, array.Length - 1);
}
public void QuickSortAlgorithm(ref int[] array, int left, int right)
{
if (left < right)
{
//Partition by finding and returning final pivot position.
int pivotIndex = Partition(ref array, left, right);
QuickSortAlgorithm(ref array, left, pivotIndex - 1);
QuickSortAlgorithm(ref array, pivotIndex + 1, right);
}
}
The code for the Partition method:
public int Partition(ref int[] array, int left, int right)The code for the GetPivot method:
{
//Pick pivot.
int pivotIndex = GetPivot(ref array, left++, right);
int newPivotIndex = pivotIndex;
while (left <= right)
{
while (left <= right && array[left] <= array[pivotIndex]) left++; //move left pointer.
while (left <= right && array[right] >= array[pivotIndex]) right--; //move right pointer.
if(left < right) Swap(ref array, left, right); //Swap elements at left and right indices.
}
//Swap pivot from current position to final position.
if (left > right) newPivotIndex = right;
Swap(ref array, pivotIndex, newPivotIndex);
return newPivotIndex;
}
private int GetPivot(ref int[] array, int left, int right)
{
Swap(ref array, left, right);
return left;
}
From the above code it is quite clear that a lot of work is done in the Partition method.
The explanation of how the above code works is trivial and is explained in the third paragraph above. In the QuickSortAlgorithm method the statement if (left < right) ensures that recursion only runs if there are more than one element. You will also notice why this method is in-place; because the same array is used so no additional memory to store the array is used. In C# this is achieved through passing by reference. This is a good all around algorithm to use and many programming languages built in sorting uses some form of quicksort algorithm.
Next: MergeSort.
Previous: Insertion Sort.
Landing page: Part One.
No comments :
Post a Comment