Liczenie złożoności sortowania

Co liczy sort?

Liczenie jest najlepiej zilustrowane sortowaniem liczb całkowitych. W C/C ++ i Java postacie są liczbami całkowitymi i mogą być sortowane w sposobie sortowania liczb całkowitych. Rozważ następującą nieporadowaną listę liczb całkowitych:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

Ta lista jest sortowana w kolejności rosnącej. Można go podać (otrzymane przez program sortowania) jako tablicę. Składa się z liczb dodatnich większych lub równych 0.

Zauważ tutaj, że najwyższa liczba całkowita to 20. Tak więc, 20 + 1 = 21, należy zapewnić nowe lokalizacje tablicy. Dodatkowe 1 dotyczy możliwości, że jeden z liczb całkowitych do sortowania wynosi 0. Pamiętaj, że program sortowania nie zna liczb, które należy sortować z wyprzedzeniem. Tak więc należy wykonać 0.

Dla każdego indeksu nowej tablicy, która odpowiada wartości na danej liście, liczba wystąpienia wartości na danej liście jest przypisana jako wartość tej nowej komórki tablicy. To znaczy, nowa tablica składa się z liczników. Poprzednia lista nieprojektowana jest przedstawiona w następujący sposób:

0	0	0	0	0	0	0	0	1	0	1	0	3	0	1	0	1	0	2	0	1
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

Ta tabela reprezentuje jedną tablicę, która jest nową gamą liczników. Na tym etapie istnieją dwie tablice: podana tablica listy nieporozowanej i tablica liczników zwanych tablicą hrabia.

W tabeli drugi wiersz ma indeksy. Pierwszy rząd ma liczbę. Każda liczba jest liczbą występowania odpowiedniego wskaźnika znalezionego jako wartość na listy nieporządkowanej.

W przypadku indeksów od 0 do 7 (włącznie) liczba wynosi 0. Wynika to z faktu, że żaden z tych indeksów nie jest wartością na podanej listy nieporządkowanej. Indeks 8 występuje raz na liście, więc jego liczba wynosi 1. Indeks 9 występuje zero razy na liście, więc jego liczba wynosi 0. Indeks 10 występuje raz na liście, więc jego liczba wynosi 1. Indeks 12 występuje trzy razy na liście, więc jego liczba wynosi 3. Indeks 13 występuje zero razy na liście, więc jego liczba wynosi 0. Trwa to do indeksu 20 z liczbą 1, podczas gdy indeks 18 ma liczbę 2.

Sortowana lista jest następująca:

8, 10, 12, 12, 12, 14, 16, 18, 18, 20

Można to uzyskać z tablicy hrabiego (nowej) w następujący sposób:

Przechodząc od lewej do prawej, jeśli wartość indeksu wynosi 0, wartość ta nie znajduje się na podanej listy niepohamowanej (tablica). Jeśli wartość to 1, wpisz indeks raz. Jeśli wartość to 2, wpisz indeks dwa razy. Jeśli wartość to 3, wpisz indeks trzy razy. Jeśli wartość to 4, wpisz indeks 4 razy i tak dalej. Wszystko to można wykonać w danej rozprawie (lista).

Liczenie algorytmu sortowania

• Podaj tablicę, której długość jest maksymalną liczbą na liście Unsorted, plus 1 (aby uwzględnić możliwe 0 na liście). Indeks tej tablicy jest możliwą wartością na liście nieporozumień.
• Przeczytaj tablicę liczby od lewej do prawej, a następnie wpisz indeks, którego wartość nie wynosi 0, i liczba razy dla wartości komórki indeksu.

Operacje

Algorytm ma dwa kroki. W przypadku poprzedniej podanej listy pierwszy krok ma 10 głównych operacji, ponieważ liczba elementów na liście Unsorted wynosi 10. Drugi krok ma 21 głównych operacji, ponieważ maksymalna wartość na liście nieprojektowanej wynosi 20 (dodatkowe 1 to dla możliwej wartości 0). Tak więc liczba głównych operacji jest uważana za następujące:

O (10 + 20)

Gdzie 10 jest liczbą elementów na liście nieprojektowanej, a 20 to maksymalna wartość na liście nieporozumień. Dodane 1 do 20 jest w tym momencie ignorowane, ale pamiętaj, że należy go zakodować.

Złożoność czasu do liczenia sortowania

Złożoność czasu to przybliżona liczba głównych operacji dla niektórych kodów. Złożoność czasu wskazuje szybkość kodu. Złożoność czasu do liczenia jest podana następująco:

O (n + m)

Gdzie n jest liczbą elementów (długość lub rozmiar) podanej nieprojektowanej tablicy, a m to maksymalna wartość w danej nieporządkowanej tablicy. Dodane 1 do M jest w tym momencie ignorowane. Big-O z nawiasami i treścią jest określany jako notacja Big-O.

Zauważ, że aby uzyskać maksymalną wartość w tablicy, niektóre operacje muszą wystąpić w kodzie. Jednak operacje te są ignorowane podczas cytowania złożoności czasu.

Tablica hrabia musi mieć początkowo wszystkie swoje elementy jako zero. Wszystkie te operacje są również ignorowane przy cytowaniu złożoności czasu dla sortowania liczenia.

Przestrzeń pamięci

Zauważ, że w poprzedniej tablicy liczby wszystkie liczby 0 są zbędne. Chociaż ich przestrzenie są zbędne w pamięci, muszą tam być. Sekt zliczania wymaga niepotrzebnej przestrzeni pamięci. Nic zwykle nie jest robione, aby uniknąć zbędnych lokalizacji. Jeśli może być znana minimalna wartość w danej nieporządkowanej tablicy, początkowa część tablicy liczby można pominąć w celu zmniejszenia miejsca. Jednak nie można pominąć przeplatanych zer w tablicy liczby.

Uwaga: Istnieje również złożoność przestrzeni, ale nie jest to rozwiązane w tym artykule.

Kodowanie w c

Funkcja sortowania liczenia w języku komputerowym C jest następująca:

void Countingsort (int arr [], int n)
int max = 0;
for (int i = 0; i max)
max = arr [i];


int liczba [max+1];
dla (int i = 0; i< max+1; i++)
Count [i] = 0;

//N
dla (int i = 0; i< n; i++)
count [arr [i]] = count [arr [i]] + 1; // Dodaj 1 dla każdego zdarzenia

//M
int k = 0; // indeks dla danej tablicy
dla (int i = 0; iif (liczba [i] != 0)
for (int j = 0; jarr [k] = i; // Odkładanie sortowanej wartości w danej tablicy
K ++;

Zagnieżdżone w pętli i wkład są następujące:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

W rzeczywistości są 24 główne operacje, a nie 20. Dodatkowa operacja 3 + 1 = 4 jest ignorowana podczas cytowania złożoności czasu dla sortowania zliczania.

Odpowiednia główna funkcja C jest następująca:

int main (int argc, char ** argv)

int n = 10;
int arr [] = 16, 20, 12, 10, 18, 8, 12, 18, 12, 14;
hrabitsort (arr, n);
dla (int i = 0; iprintf („%d”, arr [i]);
printf („\ n”);
powrót 0;

Wyjście to:

8 10 12 12 12 14 16 18 18 20

Wniosek

Złożoność czasu dla liczenia jest:

O (n + m)

Gdzie m jest zwykle większy niż n, n to liczba elementów (długość) podanej listy nieporządkowanej, a M jest maksymalnym elementem na podanej listy nieporządkowanej.