tirou Temat założony przez niniejszego użytkownika |
Sortowanie przez Kopcowanie » 2012-08-02 13:29:07 Witam mam problem zsortowaniem przez kopcowanie, gdyz nie sortuje prawidlowo tablicy. Mogłby ktoś wejrzeć w problem? Dodam niestety, iż algorytm rozumiem w 90%.
#include <iostream> #include <cstdlib> using namespace std; void budujkop( int[], int ); void rozlozkop( int[], int ); void sort( int[], int n ); void swap( int &, int & ); int main() { const int n = 20; int d[ n ]; for( int i = 0; i < n; i++ ) { d[ i ] = rand() % 10; cout << d[ i ] << " "; } sort( d, n ); cout << "\nPosortowana: \n\n"; for( int i = 0; i < n; i++ ) { cout << d[ i ] << " "; } }
void budujkop( int d[], int n ) { for( int i = 2; i <= n; i++ ) { int j = i; int k = j / 2; int x = d[ i ]; while(( k > 0 ) &&( x > d[ k ] ) ) { d[ j ] = d[ k ]; j = k; k = j / 2; } d[ j ] = x; } }
void rozlozkop( int d[], int n ) { int m; for( int i = n; i > 1; i-- ) { swap( d[ 1 ], d[ i ] ); int j = 1; int k = 2; while( k < i ) { if(( k + 1 < i ) &&( d[ k + 1 ] > d[ k ] ) ) int m = k + 1; else m = k; if( d[ m ] <= d[ j ] ) break; swap( d[ j ], d[ m ] ); j = m; k = j + j; } } }
void sort( int d[], int n ) { budujkop( d, n ); rozlozkop( d, n ); }
void swap( int & a, int & b ) { int tmp = a; a = b; b = tmp; } |
|
m4tx |
» 2012-08-02 13:30:41 1. Kolorowanie składni języka C++2. Możesz podać dane wejściowe programu, jak program powinien dane posortować, a jak sortuje? :) Uwierz, nie każdemu chce się tutaj kompilować ten program :P |
|
SeaMonster131 |
» 2012-08-02 13:33:04 A tak apropo.. Tylko ja mam buga ze scrollowanie treści w tym znaczniku [code]? o.O // w tym [cpp] też -.- Ale wtedy gdy podczas ładowania strony przesunę stronę gdzieś dalej na dół. |
|
tirou Temat założony przez niniejszego użytkownika |
» 2012-08-02 13:34:42 tzn dane wejsciowe sa losowe, powinien sortowac rosnaco, a sortuje nieznanym mi algorytmem.
Problem prawdopodobnie jest w kodzie dotyczacym rozkladaniu kopca, gdyż budowanie jest dla mnie zrozumiale, a rozkladanie kopca troszkemi sie myli i popelnilem jakis fatalny blad, ktorego niestety nie widze..
Tablica randomowa: 1 7 4 0 9 4 8 8
Tablica posortowana: 1 7 8 4 0 4 8 8
cos jest nie tak z odliczaniem gdyz np znikla 9 a pojawila sie trzecia 8.
Potrafi ktoś poprawic mój algorytm ? |
|
CodeMeister |
» 2012-08-03 12:27:35 Masz taki kod: for( int i = 2; i <= n; i++ ) { int j = i; int k = j / 2; d[ j ] = d[ k ];
popatrz na 4 linijkę (int k = j/2). Zmienna 'J' jest typu int, inkrementujesz ją o jeden... (pośrednio) A zmiennej 'K' przypisujesz wartość 'J' dzielonej na dwa... Co będzie jeśli 'J' będzie nie parzysta? np. 5 wtedy 'J' / 2 = 2.5 a kompilator nie może przechowywać w int liczby "z przecinkiem"... więc zaokrągli do 3. Musisz to zmienić. ps. w pętlach staraj się umieszczać inkrementację przedrostkową (++i) :) //EDIT: @WodnyPotworze131 - też sobie znalazłeś miejsce na wygłoszenie problemu :P |
|
m4tx |
» 2012-08-03 12:59:49 ps. w pętlach staraj się umieszczać inkrementację przedrostkową (++i) :) |
Co za różnica? Toż to pętla przecież :P A nie MorskiPotworze131? :) |
|
SeaMonster131 |
» 2012-08-03 13:06:04 Raczej "morski" :P I sorry za offtop, więcej już nie spamuję :) |
|
tirou Temat założony przez niniejszego użytkownika |
» 2012-08-03 15:52:04 tak, lecz w sortowaniu przez kopcowanie elementy w kopcu mniejsze od korzenia majaindeksy 2*i oraz 2*i+1, wiec jak dojade od 3 do 4 to bede mial caly czas 2, jak i=5, to k=j/2=2.5=3 i wtedy dojade do elementu 2*i+1 itd. Wydaje mi się, że akurat w tym nie ma błędu, aczkolwiek moge sie mylic i po prostu nie zrozumiałem ciebie kolego (tam nieco wyzej ;p) |
|
« 1 » 2 |