maciek1o3s Temat założony przez niniejszego użytkownika |
Pomoc w zrozumieniu rekurencji w quick_sort » 2015-11-16 21:01:50 Hej, podano nam algorytm do quick_sorta, jako tako go rozumiem a paroma wyjątkami. void quick_sort( int t[], int n ) { int i, j, x = t[ 0 ], n1 = 0, n2 = 0, t1[ n - 1 ], t2[ n - 1 ]; if( n <= 1 ) return; for( i = 1; i < n; i++ ) { if( t[ i ] < x ) { t1[ n1 ] = t[ i ]; n1++; } else { t2[ n2 ] = t[ i ]; n2++; } } quick_sort( t1, n1 ) quick_sort( t2, n2 ) for( i = 0; j = 0; j < n1; j++; i++ ) { t[ i ] = t1[ j ]; } t[ i ] = x; i++; for( j = 0; j < n2; j++; i++ ) { t[ i ] = t2[ j ]; } }
I teraz tak, jako że dopiero uczę się rekurencji chciałbym rozpisać sobie co się dzieje przy wywoływania funkcji - quick_sort(t1,n1). Tak więc: tutaj mamy caly poczatek, az do pierwszego wywolania funkcji w funkcji quick_sort( t1, n1 ) { int i, j, x = t[ 0 ], n1 = 0, n2 = 0, t1[ n - 1 ], t2[ n - 1 ]; if( n <= 1 ) return; for( i = 1; i < n; i++ ) { if( t[ i ] < x ) { t1[ n1 ] = t[ i ]; n1++; } else { t2[ n2 ] = t[ i ]; n2++; } } quick_sort( t1, n1 ) { ... }
Chciałbym przeanalizować dokładnie co tu się stało. Wywołujemy funkcję, która ma nowo utworzoną tabele t1 podzielić na 2 nowe tabele. Tylko teraz tak, mamy pare sprzeczności moim zdaniem. 1. if( t[ i ] < x ) - czemu odnoszę się znów do pierwszej tablicy? Nie powinienem odnieść się już do tablicy t1? 2. if( t[ i ] < x ) { t1[ n1 ] = t[ i ]; n1++; } else { t2[ n2 ] = t[ i ]; n2++; } - no chwila, przecież ja już mam t1 i t2 to mam je nadpisać czy co? |
|
carlosmay |
» 2015-11-16 21:57:19 t1[ n - 1 ], t2[ n - 1 ];
rozmiar statycznej tablicy musi być znany w momencie kompilacji. quick_sort( t1, n1 ) quick_sort( t2, n2 )
wywołania funkcji nie mają średników. for( i = 0; j = 0; j < n1; j++; i++ ) { }
Jeśli chcesz mieć więcej niż jedną zmienną w poszczególnych elementów oddzielasz je przecinkami. np. for( i = 0, j = 1; i < a; i++, j++ ) { }
Sporo błędów na podany algorytm. chciałbym rozpisać sobie co się dzieje przy wywoływania funkcji - quick_sort(t1,n1). |
Funkcja rekurencyjnie wywołuje samą siebie, czyli funkcja rozpoczyna się od początku z nowymi wartościami argumentów, ale same argumenty to te same nazwy co w pierwszym wywołaniu. Więc kolejne wywołanie samej siebie nie będzie tak wyglądać: czemu odnoszę się znów do pierwszej tablicy? Nie powinienem odnieść się już do tablicy t1? |
przekazujesz tablicę t1, ale funkcja w nagłówku ma zadeklarowaną nazwę 't[]' więc odbiera ją jako 't'. |
|
maciek1o3s Temat założony przez niniejszego użytkownika |
» 2015-11-16 22:43:13 odbiera ją jako t[]? Czyli znów sie odnosi do pierwszej (początkowej) tablicy? To nie ma sensu, przecież powinna odnosić się do tablicy, którą dzieli (wcześniejszą), a nie do początkowej. t1[ n - 1 ], t2[ n - 1 ];
rozmiar statycznej tablicy musi być znany w momencie kompilacji. Pytałem o to na wykładzie i podobno jest to dobrze, bo deklarujemy maksymalną liczbę elementów nowej tablicy (w tym przypadku n-1). |
|
carlosmay |
» 2015-11-16 22:56:11
quick_sort( tablica, ilosc_elementow );
void quick_sort( int t[], int n ) { quick_sort( t1, n1 ); quick_sort( t2, n2 ) }
na pierwszy ogień idzie pierwsze wywołanie, póki jest wywoływana, a później funkcja wraca po własnych wywołaniach i uruchamia się dalsza część funkcji z drugim wywołaniem. (rekurencja) |
|
Gibas11 |
» 2015-11-16 22:56:32 Tyle że tutaj nie jest znany, może używasz jakiegoś cudownego kompilatora który to kompiluje, ale coś takiego nie powinno działać. |
|
maciek1o3s Temat założony przez niniejszego użytkownika |
» 2015-11-16 23:19:17 #include <cstdlib> #include <iostream> using namespace std;
void quick_sort( int t[], int n ) { int i, j, x = t[ 0 ], n1 = 0, n2 = 0, t1[ n - 1 ], t2[ n - 1 ]; if( n <= 1 ) return; for( i = 1; i < n; i++ ) if( t[ i ] < x ) { t1[ n1 ] = t[ i ]; n1++; } else { t2[ n2 ] = t[ i ]; n2++; } quick_sort( t1, n1 ); quick_sort( t2, n2 ); for( i = 0, j = 0; j < n1; j++, i++ ) t[ i ] = t1[ j ]; t[ i ] = x; i++; for( j = 0; j < n2; j++, i++ ) t[ i ] = t2[ j ]; }
void print_table( int t[], int n ) { int i; for( i = 0; i < n; i++ ) { cout << t[ i ]; if( i < n - 1 ) cout << ","; cout << " "; } }
int main( int argc, char * argv[] ) { int table1[ 10 ] = { 5, 2, 1, 3, 8, 7, 9, 4, 0, 6 }; int table2[ 8 ] = { - 5, - 2, 1, 33, 28, 17, - 9, 42 }; quick_sort( table1, 10 ); quick_sort( table2, 8 ); cout << "table1 = "; print_table( table1, 10 ); cout << endl; cout << "table2 = "; print_table( table2, 8 ); cout << endl; system( "PAUSE" ); return 0; } Normalnie chodzi to w Dev Cpp. Nie wiem o co się czepiacie :P Mnie nie chodzi zebyście wytknęli mi błędy w kodzie tylko proszę o wytłumaczenie jak działa rekurencja. Jeśli w czasie funkcji void quick_sort jest wywoływana ona jeszcze raz - quick_sort (t1, n1); - to tak w miejsce tego znów zaczął pisać zawartość void quick_sort - czyli mielę od początku tablicę t (bo void quick_sort ma np. if(t <x) - to jest odniesienie to tablicy t (czyli pierwszej), a nie do tablicy t1), a przecież mi zależy żeby teraz operować na nowej tablicy t1, która została utworzona z tablicy t. |
|
Gibas11 |
» 2015-11-16 23:22:57 Operujesz na tablicy t1, po prostu dostaje ona inną nazwę, ponieważ w parametrach jest samo 't'. |
|
maciek1o3s Temat założony przez niniejszego użytkownika |
» 2015-11-16 23:32:57 Ja jestem lewy w C++ więc nie zrozumiałem za bardzo co mi chcesz przekazać. Spróbuję sformułować pytanie najprościej jak się da.
Na początku funkcja void quick_sort dzieli nam tablice t na t1 i t2. Potem wywołujemy funkcje quick_sort(t1, n1) dla tablicy t1. I teraz nie rozumiem tego, funkcja dzieli nam tablice t1 na tablice t1 i t2? No coś tu nie halo chyba. Dlaczego uważam że t1 dzieli na t1 i t2? A no dlatego że t zostało podzielone na t1 i t2, a dla t1 stosujemy dokładnie tą samą funkcję.
Czego ja nie rozumiem tutaj? |
|
« 1 » 2 |