zliczanie ciągów w quicksort

0

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.

0

chyba jest problem ze zrozumieniem rekurencji ;)

tworzysz zmienną lokalną licze. po pierwszym wywołaniu ma ona wartość: {zliczam2=0; zliczam3=1}. potem rekurencyjnie wywołujesz kolejne quicksorty, ale nic nie robisz z ich wynikiem! to znaczy, że jak już wszystkie wywołania rekurencyjne funkcji się zakończą, to na końcu i tak zostanie zwrócona pierwsza wartość czyli {0,1}. nie chce mi się tego dogłębnie analizować, nie mam czasu na sprawdzenie tego programu, ale na moje oko musisz zrobić coś takiego:

struct ciagi licze1 = quickSort(T, p, poz, licze.zliczam2, licze.zliczam3);                                
struct ciagi licze2 = quickSort(T, poz+1, k, licze.zliczam2, licze.zliczam3);   
licze.zliczam2 += licze1.zliczam2+licze2.zliczam2 ;
licze.zliczam3 += licze1.zliczam3+licze2.zliczam3 ;
0

Dziwię się, że cos takiego w ogóle Ci się skompilowało:

<code = cpp> int n;
cin >> n;
int tab[n];


Jeśli z góry nie znasz wielkości tablicy, musisz ją deklarować dynamiczne:

<code = cpp>int n;
int *tab;
cin >> n;
tab = new int[n];
0
rafal__ napisał(a)

chyba jest problem ze zrozumieniem rekurencji ;)
...

struct ciagi licze1 = quickSort(T, p, poz, licze.zliczam2, licze.zliczam3);                                
struct ciagi licze2 = quickSort(T, poz+1, k, licze.zliczam2, licze.zliczam3);   
licze.zliczam2 += licze1.zliczam2+licze2.zliczam2 ;
licze.zliczam3 += licze1.zliczam3+licze2.zliczam3 ;

Dopiero się uczę, więc pewnie i z tym problem ;) Zrobiłem jak zaproponowałeś, ale teraz zwraca mi zupełnie dziwaczne wartości. Fragment kodu:

struct ciagi quickSort(int *T, int p, int k, int dwa, int trzy){
	struct ciagi licze, licze1, licze2;
	if (p + 1 < k) {  
				int poz = partition(T, p, k);
				if (poz-p-1==2 || k-poz==2) licze.zliczam2=dwa+1;
				if (poz-p-1==3 || k-poz==3) licze.zliczam3=trzy+1;
				licze1 = quickSort(T, p, poz, licze.zliczam2, licze.zliczam3);                                
				licze2 = quickSort(T, poz+1, k, licze.zliczam2, licze.zliczam3);
				licze.zliczam2 += licze1.zliczam2+licze2.zliczam2 ;
				licze.zliczam3 += licze1.zliczam3+licze2.zliczam3 ;
			}  
	return licze;
}
0
mrower napisał(a)
rafal__ napisał(a)

chyba jest problem ze zrozumieniem rekurencji ;)
...

struct ciagi licze1 = quickSort(T, p, poz, licze.zliczam2, licze.zliczam3);                                
struct ciagi licze2 = quickSort(T, poz+1, k, licze.zliczam2, licze.zliczam3);   
licze.zliczam2 += licze1.zliczam2+licze2.zliczam2 ;
licze.zliczam3 += licze1.zliczam3+licze2.zliczam3 ;

Dopiero się uczę, więc pewnie i z tym problem ;) Zrobiłem jak zaproponowałeś, ale teraz zwraca mi zupełnie dziwaczne wartości. Fragment kodu:

struct ciagi quickSort(int *T, int p, int k, int dwa, int trzy){
	struct ciagi licze, licze1, licze2;
	if (p + 1 < k) {  
				int poz = partition(T, p, k);
				if (poz-p-1==2 || k-poz==2) licze.zliczam2=dwa+1;
				if (poz-p-1==3 || k-poz==3) licze.zliczam3=trzy+1;
				licze1 = quickSort(T, p, poz, licze.zliczam2, licze.zliczam3);                                
				licze2 = quickSort(T, poz+1, k, licze.zliczam2, licze.zliczam3);
				licze.zliczam2 += licze1.zliczam2+licze2.zliczam2 ;
				licze.zliczam3 += licze1.zliczam3+licze2.zliczam3 ;
			}  
	return licze;
}

no to DEBUG ;)

0
rafal__ napisał(a)

no to DEBUG ;)

Klikam Debugger ale nic nie widzę. Tzn. w konsoli normalnie jest to co zwykle, a w Debuggerze nic nie mam. Używam Xcode :)

0
mrower napisał(a)
rafal__ napisał(a)

no to DEBUG ;)

Klikam Debugger ale nic nie widzę. Tzn. w konsoli normalnie jest to co zwykle, a w Debuggerze nic nie mam. Używam Xcode :)
to postaw breakpointa ;) ja też na początku nie lubiłem debugować, ale trzeba się tego nauczyć, nie ma innej rady

0

Dziwię się, że cos takiego ort! Ci się skompilowało:

int n;
        cin >> n;
        int tab[n]

ych, któryś raz chyba już powtórzę, że to dozwolona konstrukcja w C, którą kompilator GCC dopuszcza również w C++ jako rozszerzenie.

0

To ciekawe bo u mnie się nie kompiluje ( MSVC++ 2008 EE )

0

Ehh nie mogę znaleźć błędu i pewnie dlatego, że czegoś nie rozumiem, ale nie wiem też czego nie rozumiem. Nie wychodzi mi to zliczanie ciągów ani trochę. Pomoże mi ktoś?

1 użytkowników online, w tym zalogowanych: 0, gości: 1