Counting Sort

Loendamismeetod



Elements are integers from 1 to 6.
Lähtejada kõik elemendid on täisarvud vahemikust 1 kuni 6:

1
 2
 3
 4
 5
 6
 7
 8
3
 6
 4
 1
 3
 4
 1
 4


Count frequency of each element:
Loendame esinemiste arvu abimassiivi:
1
 2
 3
 4
 5
 6
2
 0
 2
 3
 0
 1



Count, how many elements are less or equal than cell number:
Summeerime kõrvutiolevad elemendid abimassiivis:
1
 2
 3
 4
 5
 6
2
 2
 4
 7
 7
 8


Re-write elements from right to left (to keep the method stable).
Kirjutame lähtejada elemendid ümber tagantpoolt ettepoole:
1
 2
 3
 4
 5
 6
 7
 8
3
 6
 4
 1
 3
 4
 1
 4

1
 2
 3
 4
 5
 6
 7
 8






4

1
 2
 3
 4
 5
 6
2
 2
 4
 6
 7
 8


Result:
Tulemus:
1
 2
 3
 4
 5
 6
 7
 8
1
 1
 3
 3
 4
 4
 4
 6

Jaanus Pöial