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.
>Solution :
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?