Good day. I wrote the quick sorting function of the array in descending order in c ++, but for some reason it sorts the array not completely, the problem is probably in the algorithm, but I could not understand what was wrong. Here is the code:

void quick_sort(int* a, int n){ if(n <= 1) return; // если массив из одного элемента или меньше, то не сортируем int c = n/2; int l = 0; int r = n-1; int piv = a[c]; while(l < r){ while(a[l] > piv) l++; while(a[r] < piv) r--; if(l < r){ int tmp = a[l]; a[l++] = a[r]; a[r--] = tmp; } } quick_sort(a, c); quick_sort(a+c, nc); }

Here is an example of his work:

 massiv: 8 8 1 10 2 9 2 6 2 9 quick sort: 10 9 9 2 1 8 8 6 2 2

    2 answers 2

    You do not share so, you must recursively call not in the middle, but where l and r converge.

     void quick_sort(int* a, int n) { if (n <= 1) return; // если массив из одного элемента или меньше, то не сортируем int piv = a[n/2]; int l = 0; int r = n-1; do { while(a[l] > piv) l++; while(a[r] < piv) r--; if (l <= r){ int tmp = a[l]; a[l++] = a[r]; a[r--] = tmp; } } while(l <= r); if (r > 0) quick_sort(a,r+1); if (l < n-1) quick_sort(a+l,nl); }
    • And why in the internal if should be less or equal? After all, if left and right are equal, then this is the same element, and there is no sense to replace it? But if you make this condition strictly less, then the sorting of the left part of the array goes into infinite recursion for two elements, I don’t understand how this is related - Shadasviar
    • @Shadasviar when strictly non-recursion is infinite and external while , as in the case when l == r with strict less than l and r never change, an infinite loop comes out, and the fact that the same element changes itself is not scary (although it may be possible to do without this side effect), by the way, look also at my version of the implementation in the new answer. - ampawd

    I will offer my own implementation ...

     #include <iostream> #include <algorithm> void qsort(int* arr, int l, int r) { if (l >= r) return; int pivot = arr[l + ((r - l) >> 1)]; int i = l, j = r; for (; l <= r; ) { for (; arr[l] > pivot; ++l); for (; arr[r] < pivot; --r); if (l <= r) { std::swap(arr[l++], arr[r--]); } } qsort(arr, i, l - 1); qsort(arr, l, j); } void qsort(int* arr, int size) { qsort(arr, 0, size - 1); } int main(int argc, char *argv[]) { int arr[] = { 4, 10, -1, 2, 5, 13, 6, 0, 3 }; int size = sizeof(arr) / sizeof(arr[0]); qsort(arr, size); for (int a : arr) { std::cout << a << ' '; } return 0; }