My Quicksort does not sort the input array

Question

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.

David Schwartz · Accepted Answer · 2021-11-26 11:34:40Z

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?

463035818_is_not_an_ai · Accepted Answer · 2021-11-26 11:35:03Z

1

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.

answered Nov 26, 2021 at 11:35

463035818_is_not_an_ai

129k11 gold badges116 silver badges240 bronze badges

Comments

Pranto · Accepted Answer · 2021-11-26 11:45:33Z

0

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.

answered Nov 26, 2021 at 11:45

Pranto

414 bronze badges

1 Comment

justANewb stands with Ukraine Over a year ago

Your swapping function is a C-like way for passing by reference.

Collectives™ on Stack Overflow

My Quicksort does not sort the input array

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related