Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Pomoc w zrozumieniu rekurencji w quick_sort

Ostatnio zmodyfikowano 2015-11-17 16:24
Autor Wiadomość
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.

C/C++
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:
C/C++
tutaj mamy caly poczatek, az do pierwszego wywolania funkcji w funkcji
quick_sort( t1, n1 ) // rozpisujemy hipotetycznie co sie dzieje po wywołaniu funkcji
{
    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. 
C/C++
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?
P-140235
carlosmay
» 2015-11-16 21:57:19
C/C++
t1[ n - 1 ], t2[ n - 1 ]; // tak nie deklarujemy tablic w C++
rozmiar statycznej tablicy musi być znany w momencie kompilacji.

C/C++
quick_sort( t1, n1 )
quick_sort( t2, n2 )
 wywołania funkcji nie mają średników.

C/C++
for( i = 0; j = 0; j < n1; j++; i++ ) { } // nagłówek for sklada sie z trzech elementow
// for(wartosc poczatkowa; warunek; licznik) {}
 Jeśli chcesz mieć więcej niż jedną zmienną w poszczególnych elementów oddzielasz je przecinkami.
np.
C/C++
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ć:
C/C++
quick_sort( t1, n1 ) // rozpisujemy hipotetycznie co sie dzieje po wywołaniu funkcji

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'.
P-140242
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.

C/C++
t1[ n - 1 ], t2[ n - 1 ]; // tak nie deklarujemy tablic w C++
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).
P-140248
carlosmay
» 2015-11-16 22:56:11
C/C++
// wywolanie main()
//...
quick_sort( tablica, ilosc_elementow ); // ok ale w funkcji quick_sort(int t[], int n){}

// ... funkcja quick_sort()
void quick_sort( int t[], int n )
{
    // ... kod z masa bledow do poprawienia
    quick_sort( t1, n1 ); // brak srednika, wywolanie samej siebie z nowymi argumentami, czyli quick_sort(int t[], int n){}
    quick_sort( t2, n2 ) // to samo tutaj
    // ... tutaj reszta kodu z masa bledow
}
 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)
P-140251
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ć.
P-140252
maciek1o3s
Temat założony przez niniejszego użytkownika
» 2015-11-16 23:19:17
C/C++
#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.
P-140255
Gibas11
» 2015-11-16 23:22:57
Operujesz na tablicy t1, po prostu dostaje ona inną nazwę, ponieważ w parametrach jest samo 't'.
P-140256
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?
P-140258
« 1 » 2
  Strona 1 z 2 Następna strona