Why doesn't this implementation of the quicksort algorithm work properly?

Question

C++ / C#

I'm trying to figure out one of the many implementations of qsort, but it sorts in a strange way:

#include <iostream>
#include <ctime>
#include <iomanip>
using namespace std;
void swap(int* a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void part(int *arr_ptr, int size_arr, int m){
    if (m != 0){
        swap (arr_ptr[0],arr_ptr[m]);
    }
    int x = arr_ptr[0];
    int i=0;
    int j=size_arr;
    while(j-i>1){
        bool change = false;
        if(arr_ptr[i+1] <=x){
            ++i;
            change = true;
        }
        if(j-1>i && arr_ptr[j-1] >= x){
            --j;
            change = true;
        }
        if(!change){
            ++i;
            --j;
            swap(arr_ptr[i], arr_ptr[j]);
        }
    }
    if(i > 0){
            swap(arr_ptr[0], arr_ptr[i]);    
    }
    m = i;
}
void quicksort(int *arr_ptr, int size_arr){
    if(size_arr <= 1){
        return;
    } else if (size_arr == 2){
        if (arr_ptr[0] > arr_ptr[1]){
            swap(arr_ptr[0],arr_ptr[1]);
        }
    return;    
    }
    int beg=0;
    int k = size_arr;
    while(k>1){
        int m = k/2; //mediana
        part(arr_ptr + beg, k, m);
            int left = m;
            int right = k-1-left;
            if(left <= right){
                quicksort(arr_ptr+beg, left);
                beg +=  left+1; 
                k   -=  left+1; 
            } else {
                quicksort(arr_ptr+beg+m+1, right);
                k -= right+1;
            }
        
    } 
} 
int main()
{
    int size_arr = 10;
    srand(static_cast<unsigned int>(time(NULL)));
    int *sort_arr = new int [size_arr];
    
    int line=0;
    for (int i = 0; i < size_arr; ++i)
    {
        line++;
        sort_arr[i] = rand()%100;
        cout << setw(3) << sort_arr[i] << " ";
        if(line%5 == 0){
            cout << "\n";
        }
    }
    cout << "\n";
    quicksort(sort_arr, size_arr);
    for (int i = 0; i < size_arr; ++i)
    {
        line++;
        cout << setw(3) << sort_arr[i] << " ";
        if(line%5 == 0){
            cout << "\n";
        }
    }
    cout << "\n";
    delete [] sort_arr;
}

Conclusion:

33 23 61 14 11
14 65 23 69 60

14 23 11 14 61
33 23 60 65 69

How to fix?

Answer 1

there are a lot of problems here.
1) it is not necessary to swap the 0-th and i-th elements at the end of part. It is pointless. You support the option that the elements from 0 to the i-th <=x, from the j-th and further >=x
2) You have the parameter m in part () is passed by value. Changing it at the end of the function is not visible from the call site. You each time, no matter how the partitioning happened, recursively run the halves of the array split exactly in the middle.
3) What's going on with recursive calls? Have you slammed the tail recursion with your hands or what? And why choose which side to call recursively, and which side to process further in the cycle? There you have something messed up with the calculations, all sorts of + -1 are incorrectly shoved. you do therek -= left+1 и k -= right+1. Logically, in one half of the left elements, in the other - right. Then why are you still doing -1 here and there?