Quick explanation of the sort code

Question

This is the code I came across with implementing a quick sort algorithm. Could you explain how recursion works here?

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--; } } /* recursion */ if (left < j) quickSort(arr, left, j); if (i < right) quickSort(arr, i, right); } 

And note that this is not homework.

Answer 1

Not sure what you mean, "explain how recursion works." But here you go:

The function you posted takes an array of ints and two indexes. It will not sort the entire array, but only its part between the two indices, ignoring everything that is outside of them. This means that the same function can sort the entire array if you pass the first and last indices or just an auxiliary array if you pass the left value, which is not the index of the first element of the array and / or the right value, which is not the index of the last item.

A sorting algorithm is a well-known high-speed sorting. It uses a central element as a rod (it could use any other element). It splits the array into a subframe less than (or equal to) pivot and a submatrix greater than (or equal to) pivot , leaving the element equal to the axis of rotation between the two sections.

Then it recursively calls itself to sort the two sections, but only does it if necessary (hence, ifs before the recursive calls).

The implementation works, but is not optimal in many ways and can be improved. Here are some possible improvements:

• switch to another sorting algorithm if the array is short enough
• chose the rotation value as the average of three values ​​(usually the first, last and average)
• initially move one rotation value from the array (put it in the first or last position and reduce focus to the rest of the array), and then change the tests to transfer values ​​equal to the axis to reduce the number of swaps with their participation. You will return the rotation value with the final exchange at the end. This is especially useful if you do not follow Proposition 2 and choose the first or last element instead of the middle, as in this implementation.

Answer 2

Late answer, but I just added some fingerprints, and this can help anyone who comes across this to understand the code.

 #include<iostream> using namespace std; void quickSort(int arr[], int left, int right) { int i = left, j = right; int tmp; int pivot = arr[abs((left + right) / 2)]; cout<<"pivot is"<<pivot<<endl; /* partition */ while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i <= j) { cout<<"i and j are"<<i<<" "<<j<<"and corresponding array value is"<<arr[i]<<" " <<arr[j]<<endl; tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; cout<<"entering first big while loop"<<endl; for(int i=0;i<7;i++) cout<<arr[i]<<" "<<endl ; } } cout<<"recursion"<<endl; /* recursion */ if (left < j) quickSort(arr, left, j); if (i< right) quickSort(arr, i, right); } int main(){ int arr[7]= {2,3,8,7,4,9,1}; for(int i=0;i<7;i++) cout<<arr[i]<<" " ; quickSort(arr,0,6); cout<<endl; for(int i=0;i<7;i++) cout<<arr[i]<<" " ; int wait; cin>>wait; return 0; } 

Answer 3

Here is your answer - in general, both recursive calls will be executed, because the conditions above them will be true. However, in a corner case, you can have the rotation element as the largest (or smallest) element. In this case, you need to make only one recursive call, which basically will try to execute the process again, selecting another reference element after removing the control from the array.