| 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 |