COUNTSORT

Atutami tego algorytmu są jego szybkość ( złożoność teoretycznie stała ) i stabilność. Szybkość ponieważ działa on liniowo w każdym przypadku. Poza tym jest on stabilny, ponieważ kilka takich samych wartości sortuje w tej samej kolejności jak występowały one w oryginalnej tablicy. Dzieje się tak, ponieważ aby wstawić jakąś wartość do TEMP-a, program pobiera ją z TAB-a czytając od prawej. Czyli dwie `4' , zostaną wstawione do TEMP-a posortowane , ale w kolejności występowania w TAB-ie.

TAB [10]

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

TEMP [10]

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

COUNT [max+1]

0	1	2	3	4	5	6
1	0	0	3	3	2	1
1	1	1	4	7	9	10
				6
			3
0
						9
			2
...

ETAPY SORTOWANIA:

1/ KOPIOWANIE DO TEMP-a

2/ SZUKANIE MAKSYMUM aby móc utworzyć COUNT

3/ WYLICZENIE WYTĄPIEŃ KONKRETNEJ WAROŚCI

4/ OBLICENIE POZYCJI WARTOSCI (pierwsza z prawej) + 1

5/ Opis obok =>

-------------------------- -----------

Rozmiar Tablicy: 100,000

Funkcja CountSort : 0.080000

_Analyza + Alokacja count-a: 0.010000

_Czas sortowania : 0.070000

-------------------------- -----------

Rozmiar Tablicy: 10

Funkcja CountSort : 0.000000

_Analyza + Alokacja count-a: 0.000000

_Czas sortowania : 0.000000

-------------------------- -----------

Rozmiar Tablicy: 500,000

Funkcja CountSort : 0.391000

_Analyza + Alokacja count-a: 0.030000

_Czas sortowania : 0.361000

-------------------------- -----------

Rozmiar Tablicy: 1,000,000

Funkcja CountSort : 0.781000

_Analyza + Alokacja count-a: 0.050000

_Czas sortowania : 0.731000

-------------------------- -----------

Rozmiar Tablicy: 2,000,000

Funkcja CountSort : 1.572000

_Analyza + Alokacja count-a: 0.110000

_Czas sortowania : 1.462000

-------------------------- -----------

Rozmiar Tablicy: 4,000,000

Funkcja CountSort : 10.936000

_Analyza + Alokacja count-a: 6.620000

_Czas sortowania : 4.316000

1

2

3

5

• W pętli, program bierze kolejne wartości w TAB-ie ( od prawej do lewej ).

• W taki sposób dostaje indeks do COUNT-a pod którym wartość zmniejsza o jeden.

• Wynikiem tego działania, jest nowy indeks, tym razem do tablicy TEMP. Program może w tym momencie wrzucić do TEMP-a wartość wczytana na początku, pod tym właśnie nowym indeksem.

Strona Czytania (Punkt 5)

4

---