Napisałem algorytm na QS w C++ dla tablicy przechowującej wartości typu int.
Problem w tym, że sortuje tylko "prawie" dobrze (nie zamienia doslownie 2 liczb). Gdzie tutaj jest błąd?
Wrzucam link do kompilatora online.
Napisałem algorytm na QS w C++ dla tablicy przechowującej wartości typu int.
Problem w tym, że sortuje tylko "prawie" dobrze (nie zamienia doslownie 2 liczb). Gdzie tutaj jest błąd?
Wrzucam link do kompilatora online.
#include <iostream>
using namespace std;
void swap(int& left, int& right)
{
int temp = left;
left = right;
right = temp;
}
void qSort(int tab[], int left, int right)
{
int i = left;
int j = right;
int x = tab[(left + right) / 2];
do
{
while (tab[i] < x)
i++;
while (tab[j] > x)
j--;
if (i <= j)
{
swap(tab[i], tab[j]); // można użyć std::swap() z (C++98: <algorithm>, C++11: <utility>)
i++;
j--;
}
} while (i <= j);
if (left < j) qSort(tab, left, j);
if (right > i) qSort(tab, i, right);
}
int main()
{
int tab[] = { 4,3,5,2,5,6,5,2,3,5,3,2,234,21,1,35,13,2,3,45 };
qSort(tab, 0, sizeof(tab)/sizeof(int) - 1);
for (int i = 0; i < 20; i++)
cout << tab[i] << endl;
return 0;
}
Wystarczy zmienić linię 23 z
qSort(tab, left, m - 1);
na
qSort(tab, left, m);
i działa. Wygląda na to że błąd był tylko przez to że wychodziłeś poza zakres tablicy dla m = 0.