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

Sortowanie przez Kopcowanie

Ostatnio zmodyfikowano 2012-08-06 16:57
Autor Wiadomość
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%.

C/C++
#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 ] << " ";
    }
   
   
}
// budujemy kopiec
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;
    }
}
//rozkladamy kopiec
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;
           
        }
    }
}

// sortowanie przez kopcowanie
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;
}
P-61601
m4tx
» 2012-08-02 13:30:41
1. » Kurs STC » Kolorowanie składniKolorowanie składni języka C++ lekcja
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
P-61602
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ół.
P-61603
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 ?
P-61604
CodeMeister
» 2012-08-03 12:27:35
Masz taki kod:
C/C++
//budujkop()
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
P-61632
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

WodnyPotworze131
A nie MorskiPotworze131? :)
P-61635
SeaMonster131
» 2012-08-03 13:06:04
Raczej "morski" :P I sorry za offtop, więcej już nie spamuję :)
P-61637
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)
P-61653
« 1 » 2
  Strona 1 z 2 Następna strona