Sortowanie przez zliczanie
Ostatnio zmodyfikowano 2016-02-03 22:19
LeajD Temat założony przez niniejszego użytkownika |
Sortowanie przez zliczanie » 2016-02-03 18:29:50 Witam! Mam problem z ogarnięciem kodu w c++ z mojej książki odnośnie sortowania przez zliczanie. Mógłby mi ktoś pomóc i go objaśnić? Na przykładzie na którym było to wyjaśnione zrozumiałem a w kodzie kompletnie dziwnie to jest napisane :). Nie wiem o co chodzi z P[MAX] ( rozumiem że w tej linijce jest tablica zerowana ale nie wiem na jakiej zasadzie to przebiega), kiedy jest sortowana tablica, kiedy jest zliczana ilość występowania odpowienich cyfr i czym jest to "m" i "k". void sortuj( int T[], int n, int m )
{
int P[ MAX ] = { 0 };
for( i = 0; i < n; i++ ) P[ T[ i ] ] ++;
int k = 0;
for( int i = 0; i < m; i++ )
for( int j = P[ i ]; i >= 1; j-- )
{
T[ k ] = i;
k++;
}
}
Z góry dzięki i pozdrawiam! |
|
pekfos |
» 2016-02-03 18:31:19 Ten kod nie jest poprawny i nic nie robi. |
|
mateczek |
» 2016-02-03 18:59:57 int P[ MAX ] = { 0 };
for( i = 0; i < n; i++ ) P[ T[ i ] ] ++;
for example !!! reszty się domyśleć nie potrafię :P (Jest dla mnie tajemnicą co autor miał na myśli!!!) #include <iostream>
using namespace std;
int main() {
const int rozmiar = 10;
int T[ rozmiar ] { 1, 3, 1, 3, 3, 3, 2, 4, 2, 4 };
int P[ 4 + 1 ] { 0 };
for( int i = 0; i < rozmiar; i++ ) P[ T[ i ] ] ++;
cout << "jedynka wysapila " << P[ 1 ] << "razy" << endl;
cout << "dwojka wysapila " << P[ 2 ] << "razy" << endl;
cout << "trojka wysapila " << P[ 3 ] << "razy" << endl;
cout << "czworka wysapila " << P[ 4 ] << "razy" << endl;
} |
|
LeajD Temat założony przez niniejszego użytkownika |
» 2016-02-03 19:05:32 Tak dokładnie miało być
for( i = 0; i < n; i++ ) P[ T[ i ]]++
A mógłbyś wyjaśnić jeszcze czemu tam jest MAX? bo dla mnie to jakby maksymalna wartość w tablicy? |
|
mateczek |
» 2016-02-03 19:10:20 Moim zdaniem powinno być MAX+1
To jest druga tablica MAX-elementowa. Tablica, która składa się w moim przypadku z 5 elementów
P[0] =0
P[1] =0
P[2] =0
P[3] =0
P[4] =0 //max=5
teraz jak pętla for znajdzie w tablicy "T" liczbę 3 to zwiększa o jeden element P[3] o jeden. I po modyfikacji tablica wygląda tak!!!
P[0] =0
P[1] =0
P[2] =0
P[3] =1
P[4] =0 // max=5
trochę głupawe totto ale tak jakoś działa !!! |
|
hit |
» 2016-02-03 19:11:23 MAX oznacza maksymalną liczbę ze zbioru, który sortujesz, powiększoną o jeden - no bo po co tworzyć większą tablicę, skoro pozostała część nigdy nie zostanie wykorzystana? Chyba jednak nie do końca zrozumiałeś opis z książki. |
|
LeajD Temat założony przez niniejszego użytkownika |
» 2016-02-03 20:02:46 Ok, a co z tym "k" i o co chodzi w ostatniej pętli w której sie to k zwiększa? |
|
hit |
» 2016-02-03 20:55:45 Pokaż, w którym miejscu zmienna k się zwiększa? |
|
| « 1 » 2 |