Menu

Sortuj przez wstawianie w C ++ z przykładami

  • Główny
  • Inny
  • Sortuj przez wstawianie w C ++ z przykładami

insertion sort c with examples

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Dogłębne spojrzenie na sortowanie przez wstawianie z klasycznymi przykładami.

Sortowanie przez wstawianie to technika sortowania, którą można zobaczyć w sposób, w jaki gramy w karty. Sposób, w jaki wkładamy dowolną kartę do talii lub wyjmujemy ją, sortowanie przez wkładanie działa w podobny sposób.

Technika algorytmu sortowania przez wstawianie jest bardziej wydajna niż techniki sortowania bąbelkowego i sortowania przez wybór, ale jest mniej wydajna niż inne techniki, takie jak sortowanie szybkie i scalanie.

=> Sprawdź najlepsze samouczki szkoleniowe C ++ tutaj.

SORTOWANIE PRZEZ WSTAWIANIE

Czego się nauczysz:

Przegląd

W technice sortowania przez wstawianie zaczynamy od drugiego elementu i porównujemy go z pierwszym elementem i umieszczamy w odpowiednim miejscu. Następnie wykonujemy ten proces dla kolejnych elementów.

Porównujemy każdy element ze wszystkimi jego poprzednimi elementami i ustawiamy lub wstawiamy element we właściwej pozycji. Technika sortowania przez wstawianie jest bardziej wykonalna w przypadku tablic z mniejszą liczbą elementów. Przydaje się również do sortowania połączonych list.

najlepszy bezpieczny konwerter youtube na mp3

Listy połączone mają wskaźnik do następnego elementu (w przypadku listy pojedynczo połączonej) oraz wskaźnik do poprzedniego elementu (w przypadku listy podwójnie połączonej). W związku z tym łatwiejsze staje się zaimplementowanie sortowania przez wstawianie dla połączonej listy.

W tym samouczku zbadajmy wszystko o sortowaniu przez wstawianie.

Algorytm ogólny

Krok 1 : Powtórz kroki od 2 do 5 dla K = 1 do N-1
Krok 2 : temperatura zadana = A (K)
Krok 3 : zestaw J = K - 1
Krok 4 : Powtarzaj, gdy temp<=A(J)
zestaw A (J + 1) = A (J)
ustaw J = J - 1
(koniec wewnętrznej pętli)
Krok 5 : zestaw A (J + 1) = temp
(koniec pętli)
Krok 6 : Wyjście

Dlatego w technice sortowania przez wstawianie zaczynamy od drugiego elementu, ponieważ zakładamy, że pierwszy element jest zawsze sortowany. Następnie od drugiego do ostatniego elementu porównujemy każdy element ze wszystkimi jego poprzednimi elementami i ustawiamy ten element we właściwej pozycji.

Pseudo kod

Pseudokod sortowania przez wstawianie jest podany poniżej.

procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element whilefreePosition> 0 and array(freePosition -1) >insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedure

Powyżej podano pseudokod sortowania przez wstawianie, a następnie zilustrujemy tę technikę w poniższym przykładzie.

Ilustracja

Tablica do posortowania jest następująca:

tablica do posortowania

Teraz dla każdego przebiegu porównujemy bieżący element ze wszystkimi jego poprzednimi elementami. Tak więc w pierwszym przebiegu zaczynamy od drugiego elementu.

Sortowanie przez wstawianie - ilustracja

Dlatego potrzebujemy N liczby przebiegów, aby całkowicie posortować tablicę zawierającą N liczby elementów.

przykłady skryptów powłoki unix dla początkujących

Powyższą ilustrację można podsumować w formie tabelarycznej:

PrzechodzićNiesortowana listaporównaniePosortowana lista
1{12,3,5,10,8,1}{12.3}{3,12,5,10,8,1}
dwa{3,12,5,10,8,1}{3,12,5}{3,5,12,10,8,1}
3{3,5,12,10,8,1}{3,5,12,10}{3,5,10,12,8,1}
4{3,5,10,12,8,1}{3,5,10,12,8}{3,5,8,10,12,1}
5{3,5,8,10,12,1}{3,5,8,10,12,1}{1,3,5,8,10,12}
6{}{}{1,3,5,8,10,12}

Jak pokazano na powyższej ilustracji, zaczynamy od 2ndelement, ponieważ zakładamy, że pierwszy element jest zawsze sortowany. Zaczynamy więc od porównania drugiego elementu z pierwszym i zamieniamy pozycję, jeśli drugi element jest mniejszy niż pierwszy.

Ten proces porównywania i zamiany ustawia dwa elementy na właściwych miejscach. Następnie porównujemy trzeci element z jego poprzednimi (pierwszym i drugim) elementami i wykonujemy tę samą procedurę, aby umieścić trzeci element we właściwym miejscu.

W ten sposób dla każdego przejścia umieszczamy jeden element na jego miejscu. W pierwszym przejściu umieszczamy drugi element na jego miejscu. Tak więc ogólnie, aby umieścić N elementów we właściwym miejscu, potrzebujemy przejść N-1.

Następnie zademonstrujemy implementację techniki sortowania przez wstawianie w języku C ++.

Przykład w C ++

#include using namespace std; int main () { int myarray(10) = { 12,4,3,1,15,45,33,21,10,2}; cout<<' Input list is '; for(int i=0;i<10;i++) { cout <

Wynik:

Lista wejściowa to

12 4 3 1 15 45 33 21 10 2

Posortowana lista to

1 2 3 4 10 12 15 21 33 45

Następnie zobaczymy implementację techniki sortowania przez wstawianie w języku Java.

Przykład Java

public class Main { public static void main(String() args) { int() myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println('Input list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } for(int k=1; k=0 && temp <= myarray(j)) { myarray(j+1) = myarray(j); j = j-1; } myarray(j+1) = temp; } System.out.println(' sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } } }

Wynik:

Lista wejściowa elementów…

12 4 3 1 15 45 33 21 10 2

posortowana lista elementów…

1 2 3 4 10 12 15 21 33 45

W obu implementacjach widzimy, że zaczynamy sortowanie od 2ndelement tablicy (zmienna pętli j = 1) i wielokrotnie porównuj bieżący element ze wszystkimi jego poprzednimi elementami, a następnie posortuj element, aby umieścić go we właściwej pozycji, jeśli bieżący element nie jest w porządku ze wszystkimi poprzednimi elementami.

Sortowanie przez wstawianie działa najlepiej i można je wykonać w mniejszej liczbie przebiegów, jeśli tablica jest częściowo posortowana. Ale gdy lista rośnie, jej wydajność spada. Kolejną zaletą sortowania przez wstawianie jest to, że jest to sortowanie stabilne, co oznacza, że ​​zachowuje kolejność równych elementów na liście.

Analiza złożoności algorytmu sortowania przez wstawianie

Z pseudokodu i powyższej ilustracji wynika, że ​​sortowanie przez wstawianie jest wydajnym algorytmem w porównaniu z sortowaniem bąbelkowym lub sortowaniem przez wybór. Zamiast używać pętli for i obecnych warunków, używa pętli while, która nie wykonuje żadnych dodatkowych kroków, gdy tablica jest sortowana.

Jednak nawet jeśli przekażemy posortowaną tablicę do techniki sortowania przez wstawianie, nadal wykona ona zewnętrzną pętlę for, wymagając tym samym n liczby kroków do posortowania już posortowanej tablicy. To sprawia, że ​​najlepsza złożoność czasowa sortowania przez wstawianie jest funkcją liniową N, gdzie N jest liczbą elementów w tablicy.

Zatem różne zawiłości techniki sortowania przez wstawianie są podane poniżej:

W najgorszym przypadku złożoność czasowaO (nr 2)
Złożoność czasu w najlepszym przypadkuNa)
Średnia złożoność czasowaO (nr 2)
Złożoność przestrzeniO (1)

Pomimo tych zawiłości, nadal możemy stwierdzić, że sortowanie przez wstawianie jest najbardziej wydajnym algorytmem w porównaniu z innymi technikami sortowania, takimi jak sortowanie bąbelkowe i sortowanie przez wybór.

Wniosek

Sortowanie przez wstawianie jest najbardziej wydajną ze wszystkich trzech omówionych dotychczas technik. Tutaj zakładamy, że pierwszy element jest posortowany, a następnie wielokrotnie porównujemy każdy element ze wszystkimi jego poprzednimi elementami, a następnie umieszczamy bieżący element w odpowiedniej pozycji w tablicy.

W tym samouczku, omawiając sortowanie przez wstawianie, zauważyliśmy, że porównujemy elementy z przyrostem o 1, a ponadto są one ciągłe. Ta funkcja wymaga większej liczby przejść, aby uzyskać posortowaną listę.

analityk biznesowy pytania i odpowiedzi podczas rozmowy kwalifikacyjnej

W naszym nadchodzącym samouczku omówimy „Sortowanie powłoki”, które jest ulepszeniem w stosunku do sortowania przez wybór.

W sortowaniu powłokowym wprowadzamy zmienną zwaną „przyrostem” lub „przerwą”, za pomocą której dzielimy listę na podlisty zawierające nieciągłe elementy, które „oddzielają się” od siebie. Sortowanie powłoki wymaga mniejszej liczby przebiegów w porównaniu do sortowania przez wstawianie i jest również szybsze.

W naszych przyszłych samouczkach poznamy dwie techniki sortowania, „Szybkie sortowanie” i „Mergesortowanie”, które wykorzystują strategię „Dziel i rządź” do sortowania list danych.

=> Obejrzyj przewodnik szkoleniowy dla początkujących C ++ tutaj.

rekomendowane lektury

^