Rozważ następujące liczby:
50 60 30 10 80 70 20 40
Jeśli ta lista jest posortowana w porządku rosnącym, wyglądałoby to tak:
10 20 30 40 50 60 70 80
Jeśli jest posortowany w kolejności malejącej, będzie to:
80 70 60 50 40 30 20 10
Sortowanie przez wstawianie to algorytm sortowania używany do sortowania listy w kolejności rosnącej lub malejącej. Ten artykuł dotyczy tylko sortowania w porządku rosnącym. Sortowanie w kolejności malejącej odbywa się zgodnie z tą samą logiką podaną w tym dokumencie. Celem tego artykułu jest wyjaśnienie sortowania przez wstawianie. Programowanie odbywa się w następującym przykładzie w języku C. W tym miejscu wyjaśniono sortowanie przez wstawianie przy użyciu jednej tablicy.
Algorytm sortowania przez wstawianie
Podana jest lista nieposortowana. Celem jest posortowanie listy w porządku rosnącym przy użyciu tej samej listy. Mówi się, że sortowanie nieposortowanej tablicy przy użyciu tej samej tablicy jest sortowaniem w miejscu. Stosowane jest tutaj indeksowanie od zera. Kroki są następujące:
-
- Lista jest skanowana od początku.
- Podczas skanowania dowolna liczba mniejsza niż jej poprzedniczka jest zamieniana na jej poprzednika.
- Ta zamiana jest kontynuowana na liście, dopóki nie będzie już możliwe dokonanie zamiany.
- Gdy skanowanie dobiega końca, sortowanie jest zakończone.
Ilustracja sortowania wstawiania
Kiedy mamy do czynienia ze złożonością czasową, zwykle bierze się pod uwagę najgorszy przypadek. Najgorszy układ dla poprzedniej listy to:
80 70 60 50 40 30 20 10
Istnieje osiem elementów z indeksami od zera do 7.
Przy indeksie zero skanowanie osiąga 80. To jest jeden ruch. Ten jeden ruch to operacja. 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
Przy indeksie jeden następuje ruch do 70, 70 w porównaniu z 80. 70 i 80 są zamienione. Jeden ruch to jedna operacja. Jedno porównanie to też jedna operacja. Jedna zamiana to także jedna operacja. Ta sekcja zawiera trzy operacje. Do tej pory przeprowadzono w sumie cztery operacje (1 + 3 = 4). Wynik jest następujący:
70 | 80 60 50 40 30 20 10
Przy indeksie drugim następuje ruch do 60. 60 jest porównywane z 80, a 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 przeprowadzono łącznie dziewięć operacji (4 + 5 = 9). Wynik jest następujący:
60 70 | 80 50 40 30 20 10
Przy indeksie trzecim następuje ruch do 50. 50 jest porównywane z 80, a następnie 50 i 80 są zamieniane. 50 jest porównywane z 70, następnie 50 i 70 są zamieniane. 50 jest porównywane z 60, a następnie 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 przeprowadzono łącznie szesnaście operacji (9 + 7 = 16). Wynik jest następujący:
50 60 70 | 80 40 30 20 10
Przy indeksie czwartym następuje ruch do 40. 40 jest porównywane z 80, następnie 40 i 80 są zamieniane. 40 jest porównywane z 70, następnie 40 i 70 są zamieniane. 40 jest porównywane z 60, następnie 40 i 60 są zamieniane. 40 jest porównywane z 50, następnie 40 i 50 są zamieniane. Jeden ruch to jedna operacja. Cztery porównania to cztery operacje. Cztery swapy to cztery operacje. W tej sekcji przedstawiono dziewięć operacji. Do tej pory przeprowadzono łącznie dwadzieścia pięć operacji (16 + 9 = 25). Wynik jest następujący:
40 50 60 70 80 | 30 20 10
Przy indeksie piątym następuje ruch do 30. 30 jest porównywane z 80, a 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, następnie 30 i 40 są zamieniane. 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 przeprowadzono łącznie trzydzieści sześć operacji (25 + 11 = 36). Wynik jest następujący:
30 40 50 60 70 80 | 20 10
Przy indeksie szóstym następuje 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, następnie 20 i 40 są zamieniane. 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 przeprowadzono łącznie czterdzieści dziewięć operacji (36 + 13 = 49). Wynik jest następujący:
20 30 40 50 60 70 80 | 10
Przy indeksie siódmym następuje ruch do 10. 10 jest porównywane z 80, a 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, następnie 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 są zamieniane. 10 jest porównywane z 30, następnie 10 i 30 są zamieniane. 10 jest porównywane z 20, następnie 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 przeprowadzono 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 skończona! Dokonano 64 operacji.
64 = 8 x 8 = 8 dwa
Złożoność czasowa dla sortowania wstawiania
Jeśli istnieje n elementów do sortowania za pomocą sortowania przez wstawianie, maksymalna liczba możliwych operacji będzie wynosić n2, jak pokazano wcześniej. Złożoność czasu sortowania wstawiania to:
Na dwa )
Używa notacji Big-O. Notacja Big-O zaczyna się wielkimi literami O, po których następuje nawias. Wewnątrz nawiasów znajduje się wyrażenie określające maksymalną możliwą liczbę operacji.
Kodowanie w C
Na samym początku skanowania pierwszy element nie może zmienić swojej pozycji. Program jest zasadniczo następujący:
#włączpuste wstawienieSortuj ( int A [ ] , int N ) {
dla ( int i = 0 ; i < N; i++ ) {
int j = i;
podczas gdy ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
temp. wewn = A [ j ] ; A [ j ] = A [ j- 1 ] ; A [ j- 1 ] = temp; // zamieniać
j--;
}
}
}
Definicja funkcji insertSort() korzysta z opisanego algorytmu. Zwróć uwagę na warunki dla pętli while. Odpowiednią główną funkcją C dla tego programu jest:
{
int n = 8 ;
int A [ ] = { pięćdziesiąt , 60 , 30 , 10 , 80 , 70 , 20 , 40 } ;
sortowanie przez wstawianie ( Jakiś ) ;
dla ( int i = 0 ; i < n; i++ ) {
printf ( '%i ' , A [ i ] ) ;
}
printf ( ' \n ' ) ;
zwrócić 0 ;
}
Wniosek
Złożoność czasowa dla sortowania przez wstawianie jest podana jako:
Na dwa )
Czytelnik mógł słyszeć o złożoności czasowej najgorszego przypadku, złożoności czasowej dla przeciętnego przypadku i złożoności czasowej w najlepszym przypadku. Te odmiany złożoności czasu sortowania wstawiania zostały omówione w następnym artykule na naszej stronie internetowej.