I tried to write quicksort by myself and faced with problem that my algorithm doesn't work. This is my code:

#include <iostream>
#include <vector>

using namespace std;

void swap(int a, int b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void qsort(vector <int> a, int first, int last)
{
    int f = first, l = last;
    int mid = a[(f   l) / 2];
     
    do {
        while (a[f] < mid) {
            f  ;
        }
        while (a[l] > mid) {
            l--;
        }

        if (f <= l) {
            swap(a[f], a[l]);
            f  ;
            l--;
        }
    } while (f < l);

    if (first < l) {
        qsort(a, first, l);
    }
    if (f < last) {
        qsort(a, f, last);
    }
}

int main()
{
    int n;
    cin >> n;
    vector <int> a;
    a.resize(n);
    for (int i = 0; i < n; i  ) {
        cin >> a[i];
    }

    qsort(a, 0, n - 1);

    for (int i = 0; i < n; i  ) {
        cout << a[i] << ' ';
    }

    return 0;
}

My sort is similar to other that described on the Internet and I can't find where I made a mistake. Even when I change sort function, the problem was not solved.

CodePudding user response：

You don't pass qsort the array you want to sort, you pass it the value of that array. It modifies the value that was passed to it, but that has no effect on the array.

Imagine if you had this code:

 void foo(int a)
 {
     a = a   1;
 }

Do you think if I call this like this foo(4); that foo is somehow going to turn that 4 into a 5? No. It's going to take the value 4 and turn it into the value 5 and then throw it away, since I didn't do anything with the modified value. Similarly:

int f = 4;
foo(f);

This will pass the value 4 to foo, which will increment it and then throw the incremented value away. The value f has after this will still be 4 since nothing ever changed f.

You meant this:

void qsort(vector <int>& a, int first, int last)

Your swap has the same problem. It swaps the values of a and b, but then never does anything with the value of a or b. So it has no effect. How could it? Would swap(3, 4); somehow change that 3 into a 4 and vice-versa? What would that even mean?

CodePudding user response：

Your swap does not swap anything. You should write tests not only for the whole program but for as small pieces as possible. At least you should test single functions. Try this:

 int main() {
     int a= 42;
     int b= 0;
     std::cout << "before " << a << " " << b << "\n";
     swap(a,b);
     std::cout << "after " << a << " " << b << "\n";
}

This is "poor mans testing". For automated tests you should use a testing framework.

Then read about pass by reference. (While doing so you hopefully also realize the issue with not passing the vector to qsort by reference.)

Then use std::swap instead of reinventing a wheel.

CodePudding user response：

I Found two error on your code void swap(int a, int b) This method is not working, cause is receive value only and swap , but the original one is not updated.

void swap(int *a, int *b)
{
   int t;

   t  = *b;
   *b = *a;
   *a = t;
}

swap(&a, &b);

And you pass vactor which also pass value. replace your void qsort(vector <int> &a, int first, int last) method.