I wrote in place quick sort, but I'm not sure how to print passes, here is a code I found online @ QUICKSORT (Java, C++) | Algorithms and Data Structures, I would like to learn how to print passes during each partition as well as the return trip, when each partition is sorted, e.g.
given: 7,3,18,12,2,40,4 I'll choose first item as pivot so:
level 0: left of pivot: 4,3,2
level 0: pivot: 7
level 0: right of pivot: 12,40,18
level 1: left of pivot: 2,3
level 1: pivot: 4
level 1: left of pivot: empty
level 1: pivot: 12
level 1: right of pivot: 40,18
(after)level 1: left of pivot: empty
(after)level 1: pivot:12
(after)level 1: right of pivot: 18,40
(after)level 1: left of pivot:2,3
(after)level 1: pivot: 4
(after)level 1: left of pivot: empty
(after)level 0: left of pivot: 2,3,4
(after)level 0: pivot: 7
(after)level 0: right of pivot: 12,18,40
Code:
void print_from_to(list, int lo, int hi)
{
while ( lo <= hi )
{
cout << list[lo] << " ";
lo++;
}
}
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
//print current pass
cout << "Before: Level " << level << endl;
cout << "left of pivot: " << print_from_to(list, left, pivot) << endl;
cout << "pivot: " << pivot << endl;
cout << "right of pivot: " << print_from_to(list, pivot + 1, right) << endl;
/* recursion */
if (left < j)
quickSort(arr, left, j, level + 1);
if (i < right)
quickSort(arr, i, right, level + 1);
}
int main()
{
int list[] = {7,3,18,12,2,40,4};
size_t size = sizeof(list)/sizeof(list[0]);
quickSort(list, 0, size - 1);
return 0;
}
Any suggestions where to print each level. I added a level parameter, but I'm stuck here...I added a print_from_to function to print left and right of pivot (so from elems @ left to pivot for left of pivot list, and elems @ pivot + 1 to right for elems right of pivot). I added the printing passes but I don't know how to print the after part for each level's partition when it's sorted, please see my example.