Mógłby ktoś wytłumaczyć co znaczy taki zapis?
const int k = 77;
const int n = 1000;
int T[n];
int Tp[n];
int TPom[k];
int i;
for(i = 0 ; i < k ; ++i)
TPom[i] = 0;
for(i = 0 ; i < n ; ++i)
++TPom[T[i]]; // CHODZI MI O TEN MOMENT
Równoważny zapis:
int tmp;
for(i = 0 ; i < n ; ++i)
{
tmp = T[i];
TPom[tmp] = TPom[tmp] + 1;//czyli ++TPom[tmp]
}
Jak masz tylko ten kod, to w tablicy T są zapewne jakieś losowe wartości, więc program powinien się wyburaczyć.
Ale tak czy siak, bierzesz wartość z tablicy T o indeksie i, potem bierzesz wartość z tablicy TPom o indeksie o wcześniej pobranej wartości, a następnie inkrementujesz ową wartość, czyli zwiększać jej wartość o jeden.
Ale co niby biore z Tpom skoro wczesniej ta tablica została wyzerowana?
Inkrementujesz :P
Została wyzerowana, ale jeżeli dany element się powtarza (np. 3), to Tpom[3] będzie wynosiło dwa, jako że dwa razy nastąpiła inkrementacja (zwiększenie wartości).
Już czaje, dzięki
Nie rozumiem kolejnego miejsca, chodzi o sortowanie przez zliczanie
for(i = 1 ; i < k ; ++i)
TPom[i] += TPom[i-1];
for(i = n-1 ; i >= 0 ; --i)
Tp[--TPom[T[i]]] = T[i];
Mógłby mi ktoś to wytłumaczyć?
Czemu to przeskakuje co dwie pozycje?
for(i = 1 ; i < k ; ++i)
TPom[i] += TPom[i-1];
Sortowanie przez zliczanie uzywasz gdy znasz zakres liczb ktore chcesz posortowac. Przykladowo jesli wiesz ze masz miliard liczb z zakresu 0-10000 do posortowania to zamiast standardowego sortowania duzo szybsze bedzie sprawdzenie ile razy dana liczba wystapila i potem wypisanie kazdej z tych liczb z zakresu tyle razy ile wystapila.
Czyli tak:
X[T[i]]++ oznacza ze zwiekszasz liczbe wystapien elementu T[i] w tablicy wystapien
Co do tego:
for(i = 1 ; i < k ; ++i)
TPom[i] += TPom[i-1];
zalozmy ze wTPom[0] masz wartosc 5, a w kolejnych elementach tablicy masz kolejne liczby tak, ze TPom[i] = i.
TPom[1] = 1 + 5 = 6;
TPom[2] = 2 + (1 + 5) = 8;
TPom[3] = 3 + (2 + (1 + 5));
TPom[n] = n + (n-1) + ... + 1 + TPom[0]
a w zapisie ogolniejszym:
TPom[n] = TPom_poprzednie[n] + TPom_poprzednie[n - 1] + ... + TPom_poprzednie[0];
Czyli suma wszystkich elementow od pierwszego do aktulnego z poprzedniego stanu tablicy.
No to wiem czytałem o tym milion razy ale nie rozumiem tego kodu który wrzuciłem powyżej, robi kompletnie co innego niż według mnie powinien czyli:
Najpierw ten element powinien zliczać ilość wystąpień jakiejś liczby i tak jest
for(i = 0 ; i < n ; ++i)
++TPom[T[i]];
Potem ten kawałek według mnie powinien dodawać sobie jakieś wartośći i przypisywać do Tpom, nie wiem jakim cudem ten kawałek ustawia tą ilość wystąpień od najmniejszej do największej a co najważniejsze nie wiem po co
for(i = 1 ; i < k ; ++i)
TPom[i] += TPom[i-1];
Zobacz moj poprzedni post po modyfikacji. Druga czesc oznacza ze liczysz sume czastkowa od poczatku tablicy do aktualnego momentu wlacznie. Po co to robisz to nie wiem, sam sobie odpowiedz. Samo zliczanie to jest ta czesc co myslisz.
Wynk sortowania wypisac mozesz np. tak:
// k - liczba elementow w tablicy
for (int i = 0; i < k; i++)
{
// i - element
// n - liczba wystapien elementu i w tablicy T
int n = TPom[i];
for (int i = 0; i < n; i++) // lub rownoznacznie: while (n--)
{
cout << i << endl;
}
}
Mysle ze te Twoje liczenie sumy mozna wykorzystac do latwego obliczenia (np. binarnie) jaka wartosc ma i-ty element w posortowanej tablicy, gdzie TPom[i] mowi Ci o tym na jakim wirtualnym indeksie (po nie ma rzeczywistej tablicy wynikowej) koncza sie elementy o wartosci i
Dzięki juz rozumiem tamten kawałek
Po dodaniu tego kodu
for(i = n-1 ; i >= 0 ; --i)
Tp[--TPom[T[i]]] = T[i];
Wyswietla posartowane elementy tylko nie rozumiem tego kodu ani jak on ma sie do poprzedniego. Rozumiem tylko ten fragment
--TPom[T[i]]
W TPom masz teraz koncowe indeksy kazdej z liczb ktore mowia mniej wiecej cos takiego (na przykladzie):
TPom[0] = 2
TPom[1] = 3;
TPom[2] = 6;
Oznacza to ze Twoja wynikowa tablica to (z zaznaczonymi indeksami z tablicy TPom):
0 0 1 2 2 2 X
| | |
2 3 6
Teraz po kolei od ostatniego elementu oryginalnej tablicy:
T[i] - wartosc w oryginalnej tablicy
TPom[T[i]] - indeks jednego za ostatnim elementu w tablicy posortowanej
--TPom[T[i]] - pokazuje gdzie jest ostatni element T[i] w tablicy posortowanej
Tp - tablica posortowana
Tp[--TPom[T[i]]] - element w tablicy posortowanej do ktorego przypisujesz aktualny element, czyli wypelniasz tablice posortowaną.
--TPom[T[i]] po operacji pokazuje na "nowy" koniec elementu T[i] w tablicy posortowanej, tak ze odniesienie sie do tego samego elementu wskaze na element poprzedni.
Generalnie jesli nie potrzebujesz znac dokladnie wartosci gdzie ktory element poszedl (tzn. np. nie sortujesz obiektow lub nie potrzebujesz tzw. stable sort ani nie potrzebujesz informacji o indeksach - w przypadku sortowania intow poza sytuacja gdzie potrzebujesz oryginalne indeksy jest to zawsze prawda), to mozna to zrobic prosciej (wstaw zaraz po zliczeniu elementow):
int idx = 0;
for (int i = 0; i < k; i++)
{
int n = TPom[i];
while (n--)
{
Tp[idx] = i;
idx++;
}
}
Wielkie dzięki, już rozumiem. Juz myślałem że dziś się nie przespie.