W tym artykule omówimy algorytm sortowania przez wstawianie. Procedura sortowania przez wstawianie jest również prosta. Ten artykuł będzie bardzo pomocny i interesujący dla uczniów, ponieważ na egzaminach mogą spotkać się z pytaniem typu „wstawianie”. Dlatego ważne jest, aby omówić ten temat.
Sortowanie przez wstawianie działa podobnie do sortowania kart do gry w rękach. Zakłada się, że w grze karcianej pierwsza karta jest już posortowana, następnie wybieramy nieposortowaną kartę. Jeśli wybrana nieposortowana karta jest większa niż pierwsza karta, zostanie umieszczona po prawej stronie; w przeciwnym razie zostanie umieszczony po lewej stronie. Podobnie wszystkie nieposortowane karty są brane i umieszczane dokładnie na swoim miejscu.
To samo podejście stosuje się przy sortowaniu przez wstawianie. Ideą sortowania przez wstawianie jest to, że najpierw pobieramy jeden element, iterujemy go po posortowanej tablicy. Chociaż jest prosty w użyciu, nie nadaje się do dużych zbiorów danych, ponieważ złożoność czasowa sortowania przez wstawianie w średnim i najgorszym przypadku jest NA2) , gdzie n jest liczbą elementów. Sortowanie przez wstawianie jest mniej wydajne niż inne algorytmy sortowania, takie jak sortowanie przez stertę, sortowanie szybkie, sortowanie przez scalanie itp.
Sortowanie przez wstawianie ma różne zalety, takie jak -
- Prosta implementacja
- Wydajne w przypadku małych zestawów danych
- Adaptacyjny, tj. odpowiedni dla zbiorów danych, które są już zasadniczo posortowane.
Przyjrzyjmy się teraz algorytmowi sortowania przez wstawianie.
Algorytm
Proste kroki prowadzące do sortowania przez wstawianie są wymienione poniżej:
Krok 1 - Jeśli element jest pierwszym elementem, załóżmy, że jest już posortowany. Powrót 1.
gdzie są ustawienia przeglądarki
Krok 2 - Wybierz następny element i przechowuj go osobno w a klucz.
Krok 3 - Teraz porównaj klucz ze wszystkimi elementami posortowanej tablicy.
Krok 4 - Jeśli element w posortowanej tablicy jest mniejszy niż bieżący element, przejdź do następnego elementu. W przeciwnym razie przesuń większe elementy tablicy w prawo.
Krok 5 - Wstaw wartość.
Krok 6 - Powtarzaj, aż tablica zostanie posortowana.
Działanie algorytmu sortowania przez wstawianie
Przyjrzyjmy się teraz działaniu algorytmu sortowania przez wstawianie.
Aby zrozumieć działanie algorytmu sortowania przez wstawianie, weźmy nieposortowaną tablicę. Sortowanie przez wstawianie będzie łatwiejsze do zrozumienia na przykładzie.
Niech elementami tablicy są -
Początkowo porównywane są pierwsze dwa elementy podczas sortowania przez wstawianie.
Tutaj 31 jest większe niż 12. Oznacza to, że oba elementy są już w porządku rosnącym. Zatem na razie liczba 12 jest przechowywana w posortowanej tablicy podrzędnej.
Przejdźmy teraz do dwóch kolejnych elementów i porównajmy je.
Tutaj 25 jest mniejsze niż 31. Zatem 31 nie jest na właściwej pozycji. Teraz zamień 31 z 25. Wraz z zamianą sortowanie przez wstawianie sprawdzi także wszystkie elementy w posortowanej tablicy.
Na razie posortowana tablica ma tylko jeden element, tj. 12. Zatem 25 jest większe niż 12. Dlatego posortowana tablica pozostaje posortowana po zamianie.
Teraz dwa elementy w posortowanej tablicy to 12 i 25. Przejdź do kolejnych elementów, czyli 31 i 8.
Zarówno liczby 31, jak i 8 nie są posortowane. Więc zamień je.
Po zamianie elementy 25 i 8 pozostają nieposortowane.
Więc zamień je.
Teraz elementy 12 i 8 są nieposortowane.
Więc je też zamień.
Teraz posortowana tablica zawiera trzy elementy o wartościach 8, 12 i 25. Przejdź do kolejnych elementów o wartościach 31 i 32.
Dlatego są już posortowane. Teraz posortowana tablica zawiera 8, 12, 25 i 31.
Przejdź do kolejnych elementów czyli 32 i 17.
17 jest mniejsze niż 32. Zamień je.
Zamiana powoduje, że 31 i 17 są nieposortowane. Więc je też zamień.
Teraz zamiana powoduje, że 25 i 17 są nieposortowane. Wykonaj więc zamianę ponownie.
Teraz tablica jest całkowicie posortowana.
Złożoność sortowania przez wstawianie
Przyjrzyjmy się teraz złożoności czasowej sortowania przez wstawianie w najlepszym, średnim i najgorszym przypadku. Zobaczymy także złożoność przestrzenną sortowania przez wstawianie.
1. Złożoność czasowa
| Sprawa | Złożoność czasu |
|---|---|
| Najlepszy przypadek | NA) |
| Przeciętny przypadek | NA2) |
| Najgorszy przypadek | NA2) |
2. Złożoność przestrzeni
| Złożoność przestrzeni | O(1) |
| Stabilny | TAK |
- Złożoność przestrzenna sortowania przez wstawianie wynosi O (1). Dzieje się tak dlatego, że podczas sortowania przez wstawianie do zamiany wymagana jest dodatkowa zmienna.
Implementacja sortowania przez wstawianie
Przyjrzyjmy się teraz programom sortującym przez wstawianie w różnych językach programowania.
Program: Napisz program realizujący sortowanie przez wstawianie w języku C.
#include void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 17 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting are -
'); printarr(a, n); insert(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-18.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in python.</p> <pre> def insertionSort(a): # Function to implement insertion sort for i in range(1, len(a)): temp = a[i] # Move the elements greater than temp to one position #ahead from their current position j = i-1 while j >= 0 and temp <a[j] : a[j + 1]="a[j]" j="j-1" def printarr(a): # function to print the array for i in range(len(a)): (a[i], end=" " ) a="[70," 15, 2, 51, 60] print('before sorting elements are - ') printarr(a) insertionsort(a) print('
after < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-19.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C++ language.</p> <pre> #include using namespace std; void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 2 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) cout << a[i] <<' '; main() a[]="{" 89, 45, 35, 8, 12, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting are - '<<endl; printarr(a, n); insert(a, cout<<'
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-20.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C# language.</p> <pre> using System; class Insertion { static void insert(int[] a) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.Length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 12 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } static void printarr(int[] a) function print array int i; n="a.Length;" for (i="0;" i < n; i++) console.write(a[i] + ' '); main() int[] a="{" 98, 54, 53, 18, 21, }; console.write('before sorting are -
'); printarr(a); insert(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-21.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in Java.</p> <pre> public class Insert { void insert(int a[]) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 22 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[]) function print array int i; n="a.length;" for (i="0;" i < n; i++) system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 92, 50, 5, 20, 11, }; insert i1="new" insert(); system.out.println('
before sorting are - i1.printarr(a); i1.insert(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-22.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in PHP.</p> <pre> <?php $a = array( 92, 50, 5, 20, 11, 22 ); function printArray($a) { for($i = 0; $i < 6; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>'; printArray($a); for ($i = 1; $i = 0 && $temp <= $a[$j]) * move the elements greater than temp to one position ahead from their current position* { $a[$j+1]="$a[$j];" $j="$j-1;" } echo ' <br> After sorting array elements are - <br>'; printArray($a); ?> </=></pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-23.webp" alt="Insertion Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, and implementation in different programming languages.</p> <hr></=></n;></pre></=></n;></pre></=></n;></pre></a[j]></pre></=></n;> Wyjście:
To tyle na temat artykułu. Mam nadzieję, że artykuł będzie dla Ciebie pomocny i pouczający.
Artykuł ten nie ograniczał się tylko do algorytmu. Omówiliśmy także złożoność, działanie i implementację algorytmu w różnych językach programowania.