Złożoność czasu sortowania wstawienia

Rozważ następujące liczby:

50 60 30 10 80 70 20 40

Gdyby ta lista jest sortowana w kolejności rosnącej, byłoby to:

10 20 30 40 50 60 70 80

Jeśli jest posortowany w kolejności malejącej, byłoby to:

80 70 60 50 40 30 20 10

SORTESERTION to algorytm sortowania, który służy do sortowania listy w kolejności rosnącej lub w kolejności malejącej. Ten artykuł dotyczy tylko sortowania w kolejności rosnącej. Sortowanie w kolejności malejącej jest zgodne z tą samą logiką podaną w tym dokumencie. Celem tego artykułu jest wyjaśnienie rodzaju wstawienia. Programowanie odbywa się w poniższym przykładzie w C. Sekt wstawienia jest tutaj wyjaśniany za pomocą jednej tablicy.

Algorytm do sortowania wstawienia

Podana jest nieprojektowana lista. Celem jest uporządkowanie listy w kolejności rosnącej za pomocą tej samej listy. Mówi się, że sortowanie nieprojektowanej tablicy za pomocą tej samej tablicy jest sortowanie. Tutaj używane jest indeksowanie oparte na zero. Kroki są następujące:

• • Lista jest skanowana od początku.
  • Podczas gdy skanowanie trwa, dowolna liczba mniejsza niż jego poprzednik jest zamieniony na jego poprzednik.
  • Ta zamiana trwa wzdłuż listy, dopóki nie będzie już możliwe zamiana.
  • Gdy skanowanie osiągnie koniec, sortowanie jest zakończone.

Ilustracja sortowania insercji

W radzeniu sobie ze złożonością czasu jest to najgorszy przypadek, który zwykle jest brany pod uwagę. Najgorszym porozumieniem dla poprzedniej listy jest:

80 70 60 50 40 30 20 10

Istnieje osiem elementów z indeksami od zera do 7.

W INDEX ZERO skanowanie przechodzi do 80. To jest jeden ruch. Ten jeden ruch jest operacją. Do tej pory jest w sumie jedna operacja (jeden ruch, bez porównania i bez zamiany). Wynik to:

|. 80 70 60 50 40 30 20 10

W indeksie pierwszym jest ruch do 70. 70 jest porównywane z 80. 70 i 80 są zamieniane. Jeden ruch to jedna operacja. Jedno porównanie to także jedna operacja. Jedna zamiana to także jedna operacja. Ta sekcja zawiera trzy operacje. Do tej pory jest w sumie cztery operacje (1 + 3 = 4). Wynik jest następujący:

70 | 80 60 50 40 30 20 10

W indeksie drugim jest ruch do 60. 60 jest porównywane z 80, następnie 60 i 80 są zamieniane. 60 jest porównywane z 70, następnie 60 i 70 są zamieniane. Jeden ruch to jedna operacja. Dwa porównania to dwie operacje. Dwie swapy to dwie operacje. Ta sekcja zawiera pięć operacji. Do tej pory jest w sumie dziewięć operacji (4 + 5 = 9). Wynik jest następujący:

60 70 | 80 50 40 30 20 10

W indeksie trzecim jest ruch do 50. 50 jest porównywane z 80, następnie 50 i 80 są zamieniane. 50 jest porównywane z 70, a następnie 50 i 70 są zamieniane. 50 jest porównywane z 60, wówczas 50 i 60 są zamieniane. Jeden ruch to jedna operacja. Trzy porównania to trzy operacje. Trzy swapy to trzy operacje. Ta sekcja zawiera siedem operacji. Do tej pory istnieje w sumie szesnaście operacji (9 + 7 = 16). Wynik jest następujący:

50 60 70 | 80 40 30 20 10

W indeksie czwartym jest ruch do 40. 40 jest porównywane z 80, następnie 40 i 80 są zamieniane. 40 jest porównywane z 70, a następnie 40 i 70 są zamieniane. 40 jest porównywane z 60, a następnie 40 i 60 są zamieniane. 40 jest porównywane z 50, a następnie 40 i 50 są zamieniane. Jeden ruch to jedna operacja. Cztery porównania to cztery operacje. Cztery swapy to cztery operacje. Ta sekcja zawiera dziewięć operacji. Do tej pory jest w sumie dwadzieścia pięć operacji (16 + 9 = 25). Wynik jest następujący:

40 50 60 70 80 | 30 20 10

W indeksie piątym jest ruch do 30. 30 jest porównywane z 80, następnie 30 i 80 są zamieniane. 30 jest porównywane z 70, następnie 30 i 70 są zamieniane. 30 jest porównywane z 60, następnie 30 i 60 są zamieniane. 30 jest porównywane z 50, następnie 30 i 50 są zamieniane. 30 jest porównywane z 40, a następnie 30 i 40. Jeden ruch to jedna operacja. Pięć porównań to pięć operacji. Pięć swapów to pięć operacji. Ta sekcja zawiera jedenaście operacji. Do tej pory istnieje w sumie trzydzieści sześć operacji (25 + 11 = 36). Wynik jest następujący:

30 40 50 60 70 80 | 20 10

W indeksie szóstym jest ruch do 20. 20 jest porównywane z 80, a następnie 20 i 80 są zamieniane. 20 jest porównywane z 70, następnie 20 i 70 są zamieniane. 20 jest porównywane z 60, następnie 20 i 60 są zamieniane. 20 jest porównywane z 50, następnie 20 i 50 są zamieniane. 20 jest porównywane z 40, a następnie 20 i 40. 20 jest porównywane z 30, następnie 20 i 30 są zamieniane. Jeden ruch to jedna operacja. Sześć porównań to sześć operacji. Sześć swapów to sześć operacji. Ta sekcja zawiera trzynaście operacji. Do tej pory istnieje w sumie czterdzieści dziewięć operacji (36 + 13 = 49). Wynik jest następujący:

20 30 40 50 60 70 80 | 10

W indeksie siódmym jest ruch do 10. 10 jest porównywane z 80, następnie 10 i 80 są zamieniane. 10 jest porównywane z 70, następnie 10 i 70 są zamieniane. 10 jest porównywane z 60, wówczas 10 i 60 są zamieniane. 10 jest porównywane z 50, następnie 10 i 50 są zamieniane. 10 jest porównywane z 30, następnie 10 i 40. 10 jest porównywane z 30, następnie 10 i 30 są zamieniane. 10 jest porównywane z 20, wówczas 10 i 20 są zamieniane. Jeden ruch to jedna operacja. Siedem porównań to siedem operacji. Siedem swapów to siedem operacji. Ta sekcja zawiera piętnaście operacji. Do tej pory istnieje w sumie sześćdziesiąt cztery operacje (49 + 15 = 64). Wynik jest następujący:

10 20 30 40 50 60 70 80 10 |

Praca jest wykonywana! W grę wchodziło 64 operacje.

64 = 8 x 8 = 8²

Złożoność czasu dla sortowania wstawienia

Jeśli istnieją n elementy do sortowania z sortowaniem wstawienia, maksymalna liczba możliwych operacji wynosiłaby N2, jak pokazano wcześniej. Złożoność czasu sortowania wstawienia wynosi:

NA²)

To wykorzystuje notację Big-O. Notacja Big-O zaczyna się od O UnperCase, a następnie nawiasów. Wewnątrz nawiasów znajduje się wyrażenie maksymalnej możliwej liczby operacji.

Kodowanie w c

Na samym początku skanowania pierwszy element nie może zmienić swojej pozycji. Program jest zasadniczo następujący:

#włączać
void insertionsort (int a [], int n)
dla (int i = 0; iint j = i;
While ([j] < A[j-1] && j-1 >= 0)
int temp = a [j]; A [j] = a [j-1]; A [j-1] = temp; //zamieniać
J--;

Definicja funkcji insertionsort () używa algorytmu zgodnie z opisem. Zwróć uwagę na warunki dla pętli pobytu. Odpowiednią główną funkcją C dla tego programu jest:

int main (int argc, char ** argv)

int n = 8;
int a [] = 50, 60, 30, 10, 80, 70, 20, 40;
insertionsort (a, n);
dla (int i = 0; iprintf („%i”, a [i]);

printf („\ n”);
powrót 0;

Wniosek

Złożoność czasu dla wstawienia jest podana jako:

NA²)

Czytelnik mógł słyszeć o gorszej złożoności czasowej, średniej złożoności czasu i najlepiej złożoności czasu. Te różnice złożoności czasu wstawienia są omówione w następnym artykule na naszej stronie internetowej.