Sortowanie przez zliczanie jest jednym z nielicznych, prostych w implementacji algorytmów klasy O(n). Dzieje się tak gdyż nie wykorzystuje się tutaj wogóle porównywania. Jedyne operacje to dodawanie, odejmowanie i wypełanie tablicy.
Algorytm:
1. Tablica wejściowa o n długości i największym elementem k. Jest to tablica A[n].
2. Tworzymy tablicę o długości k (długość równa jest największemu elementowi tablicy wejściowej). Będzie to tablica B[k].
3. Indeksami tablicy B będą wartości tablicy A.
4. Tablica B będzie zawierała ilość wystąpień każdej z liczb z tablicy A.
Dygresja – jeśli tablica A to A={2,3,4,100} to tablica B będzie miała indeksy B[1], B[2], B[3]…B[100].
5. Sumujemy wartości z tablicy B sukcesywnie, tj:
B={0,0,1,2,0,4}
to po sumowaniu będzie to:
B={0,0,1,3,3,7}
Kawałek pseudokodu:
[c]
for i=2 to k do{
B[i]=B[i]+B[i-1]
}
[/c]
Ok, mam nadzieje że to jest w miarę jasne, potem pokażę jakis case study :)
6. Tworzymy tablicę C[n] – tablicę wynikową o rozmiarze n.
7. Tablicę wypełniamy w ten sposób:
7a. Przeglądamy od tyłu tablicę A i…
A[n] = 0;
B[0]=x;
C[x]=A[n];
B[0]=B[0]-1;
aż do momentu skonczenia tablicy A.
Posortuj tablicę A= {2,3,5,5,2,5,3,1,1};
Mamy taką tablicę, gdzie n = 9 i k = 5
Tworzymy tablicę B[k];
B[1]=2; //mamy dwa razy 1
B[2]=2; // mamy dwa razy 2
B[3] =2; // dwa razy 3
B[4]=0; //nie mam 4
B[5]=3; // i mamy 3 piątki.
przechodzimy ją, sumując sukcesywnie elementy i tablica
B={2,2,2,0,3} zmienia się w
B={2,4,6,6,9} – gdzie ostatnia liczba w tablicy B po dodawaniu będzie liczbą cyfr w tablicy A.
Tworzymy tablicę C[n];
i lecimy – przedstawie każdy krok…
1. A[9]=1;
B[1]=2;
C[2]=1;
B[2]=B[2]-1;
Teraz B={1,4,6,6,9}
2.A[8]=1;
B[1]=1; // w poprzednim kroku zmniejszylismy wartosc tej komórki.
C[1]=1;
B[1]=B[1]-1;
Teraz B={0,4,6,6,9}
3. A[7]=3;
B[3]=6;
C[6]=3;
B[3]=B[3]-1;
Teraz B={0,4,5,6,9}
4. A[6]=5;
B[5]=9;
C[9]=5;
B[5]=B[5]-1;
Teraz B={0,4,5,6,8}
5. A[5]=2;
B[2]=4;
C[4]=2;
B[2]=B[2]-1;
Teraz B={0,3,5,6,8}
6. A[4]=5;
B[5]=8;
C[8]=5;
B[5]=B[5]-1;
Teraz B={0,3,5,6,7}
7. A[3]=5;
B[5]=7;
C[7]=5;
B[5]=B[5]-1;
Teraz B={0,3,5,6,6}
8. A[2]=3;
B[3]=5;
C[5]=3;
B[3]=B[3]-1;
Teraz B={0,3,4,6,6}
9. A[1]=2;
B[2]=3;
C[3]=2;
B[2]=B[2]-1;
Teraz B={0,1,4,6,6}
Teraz bierzmy wartości w kolorze pomarańczowym czyli nasze posortowanie wartości:
| I | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| wartości | 1 | 1 | 2 | 2 | 3 | 3 | 5 | 5 | 5 |
Chyba jaśniej napisac o tym nie umiem… :)
Cześć. Dziś luźny artykuł, bo dziś pobawimy się jedną z pierwszy wersji Pythona. Skompilujemy go i zobaczymy co tam w… Read More
Nowy rok czas zacząć! Więc lećmy z podsumowaniem. Nowy artykuł Nie uwierzycie, ale pojawił się na blogu nowy artykuł! Piszę… Read More
Cześć! W Pythonie 3.13 dodano JITa! JIT, czyli just-in-time compiler to optymalizacja na która Python naprawdę długo czekał. Na nasze… Read More
Cześć! Zapraszam na podsumowanie roku 2024. Książki W sumie rok 2024 był pod względem ilości książek nieco podobny do roku… Read More
Podtrzymując tradycję, prawie regularnych podsumowań, zapraszam na wpis! Nie mogło obyć się bez Karkonoszy We wrześniu odwiedziłem z kolegą Karkonosze,… Read More
Oj daaawnoo mnie tu nie było. Ale wakacje to był czas dużej liczby intensywnych wyjazdów i tak naprawdę, dopiero jakoś… Read More
Pokaż komentarze
Jak tworzymy tablice C i przyjmujemy A[9]=1, B[1]=2, C[2]=1 i B[2]=B[2]-1 i do tego momentu wszystko jest dla mnie chyba jasne. Teraz zaczyna się mój problem, tablica B wygląda tak B={2,4,6,6,9} przed zmniejszeniem drugiego elementu o jeden, a po zmianie wygląda tak B={1,4,6,6,9}, czy nie powinna wyglądać tak że B={2,3,6,6,9}? Przecież zmniejszam drugi element, nie pierwszy? Mógłby Pan mi to wyjaśnić ?