rancid star
Hello, I'm having some trouble understanding the partition sort algorithmn, (see pic from my Universities slides),
The array we saw in class is as such;
A= [42, 89, 63, 12, 94, 27, 78, 3, 50, 36]
I understand the Idea of a partition sorting is to separate every thing less than X to one side and greater to the other, but I can't seem to understand the process. (By partition sorting I am referring to the quicksort substep)
here is the code for a closer glance (there are no errors within)
QuickSort(int left, int right){
if(right <= left) return;
else {
pivot = A[right];
pivotIndex = partition(left, right, pivot);
QuickSort(left, pivotIndex-1);
QuickSort(pivotIndex+1, right); }
}
int partition(int left, int right, int pivot){
int i = left-1;
int j = right;
while(true) {
while(A[++i] < pivot);
while(A[--j] > pivot);
if(i >= j) break;
else swapReferences(A,i,j)
}
swapReferences(A,i,right); // put pivot in correct spot
return i; // return new pivot location
}
thorny fox