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++;
}
}