Hej, mam takie zadanie:
Zaimplementuj algorytm QuickSort w wersji opisanej w Lekcji 7, tzn. jako element dzielący wybieramy zawsze pierwszy element sortowanego podciągu.
Algorytm kończy działanie sortując ciągi składające się z 2 i 3 elementów. Policz i wypisz ilość takich ciągów dla podanych danych wejściowych.
Dane wejściowe składają się z 2 linii:
w pierwszej wpisana jest liczba n elementów do sortowania. W drugiej linii znajduje się n liczb całkowitych nieujemnych.
Wyjście składa się z jednej linii w której wypisane są liczby podciągów długości 2 i 3 oddzielone spacją.
Przykład:
Dane:
8
31 47 18 19 37 8 65 7
Wynik:
2 2
I zrobiłem je tak:
#include <iostream>
using namespace std;
struct ciagi {
int zliczam2;
int zliczam3;
};
int partition(int *T, int p, int k) {
int x = T[p];
int i = p;
for (int j = p + 1; j < k; j++){
if (T[j] <= x) {
i++;
int tmp = T[j];
T[j] = T[i];
T[i] = tmp;
}
}
int tmp = T[i];
T[i] = T[p];
T[p] = tmp;
return i;
}
struct ciagi quickSort(int *T, int p, int k, int dwa, int trzy){
struct ciagi licze;
if (p + 1 < k) {
int poz = partition(T, p, k);
if (poz-p-1==2) licze.zliczam2=dwa+1;
if (k-poz-1==3) licze.zliczam3=trzy+1;
quickSort(T, p, poz, licze.zliczam2, licze.zliczam3);
quickSort(T, poz+1, k, licze.zliczam2, licze.zliczam3);
}
return licze;
}
int main () {
int n;
cin >> n;
int tab[n];
for (int i=0; i<n; i++) {
cin >> tab[i];
}
struct ciagi m;
m=quickSort(tab, 0, n, 0, 0);
cout << m.zliczam2 << " " << m.zliczam3 << endl;
return 0;
}
No i jak zwykle mam problem, bo mi źle liczy. I nie wiem co jest nie tak, choć wydaje mi się, że dobrze zliczam ciągi. Już na podanych przykładowych danych mi nie gra, daje mi 0 1 a nie 2 2.