insertion sort c with examples
O privire aprofundată asupra sortării inserției cu exemple clasice.
Sortarea prin inserție este o tehnică de sortare care poate fi vizualizată într-un mod în care jucăm cărți la îndemână. Modul în care introducem orice carte într-un pachet sau îl eliminăm, sortează prin inserare funcționează în mod similar.
Tehnica algoritmului de sortare a inserției este mai eficientă decât tehnicile de sortare Bubble și Selection, dar este mai puțin eficientă decât celelalte tehnici precum sortarea Quicksort și Merge.
=> Consultați aici cele mai bune tutoriale de formare C ++.
Ce veți învăța:
- Prezentare generală
- Algoritm general
- Pseudo cod
- Ilustrare
- Exemplu C ++
- Exemplu Java
- Analiza complexității algoritmului de sortare a inserției
- Concluzie
- Lectură recomandată
Prezentare generală
În tehnica de sortare prin inserție, pornim de la al doilea element și îl comparăm cu primul element și îl punem într-un loc adecvat. Apoi efectuăm acest proces pentru elementele ulterioare.
Comparăm fiecare element cu toate elementele sale anterioare și punem sau inserăm elementul în poziția corectă. Tehnica de sortare prin inserție este mai fezabilă pentru tablourile cu un număr mai mic de elemente. De asemenea, este util pentru sortarea listelor legate.
cum se deschid fișiere bin pe Windows 7
Listele conectate au un pointer către elementul următor (în cazul unei liste conectate individual) și un pointer către elementul anterior (în cazul unei liste dublu conectate). Prin urmare, devine mai ușor să implementați sortarea inserției pentru o listă legată.
Haideți să explorăm totul despre sortarea inserției în acest tutorial.
Algoritm general
Pasul 1 : Repetați pașii de la 2 la 5 pentru K = 1 la N-1
Pasul 2 : set temp = A (K)
Pasul 3 : set J = K - 1
Pasul 4 : Repetați în timp ce temp<=A(J)
set A (J + 1) = A (J)
setul J = J - 1
(sfârșitul buclei interioare)
Pasul 5 : set A (J + 1) = temp
(sfârșitul buclei)
Pasul 6 : Ieșire
Astfel, în tehnica de sortare prin inserție, pornim de la al doilea element, deoarece presupunem că primul element este întotdeauna sortat. Apoi, de la al doilea element la ultimul element, comparăm fiecare element cu toate elementele sale anterioare și punem acel element în poziția corectă.
Pseudo cod
Pseudo codul pentru sortarea inserției este dat mai jos.
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 procedureDat mai sus este pseudo-codul pentru sortare Insertion, în continuare, vom ilustra această tehnică în exemplul următor.
Ilustrare
Matricea care trebuie sortată este după cum urmează:
Acum, pentru fiecare trecere, comparăm elementul curent cu toate elementele sale anterioare. Deci, în prima trecere, începem cu al doilea element.
Astfel, avem nevoie de N număr de treceri pentru a sorta complet o matrice care conține N număr de elemente.
Ilustrația de mai sus poate fi rezumată într-o formă tabelară:
| Trece | Listă nesortată | comparaţie | Listă sortată |
|---|---|---|---|
| 1 | {12,3,5,10,8,1} | {12.3} | {3,12,5,10,8,1} |
| Două | {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} |
După cum se arată în ilustrația de mai sus, începem cu 2ndelement, deoarece presupunem că primul element este întotdeauna sortat. Deci, începem cu compararea celui de-al doilea element cu primul și schimbăm poziția dacă al doilea element este mai mic decât primul.
primele 10 companii de cercetare de piață din lume
Acest proces de comparație și schimbare poziționează două elemente în locurile lor adecvate. Apoi, comparăm al treilea element cu elementele sale anterioare (primul și al doilea) și efectuăm aceeași procedură pentru a plasa al treilea element în locul potrivit.
În acest mod, pentru fiecare trecere, plasăm un element în locul său. Pentru prima trecere, plasăm al doilea element în locul său. Astfel, în general, pentru a plasa N elemente în locul lor adecvat, avem nevoie de treceri N-1.
Apoi, vom demonstra implementarea tehnicii de sortare Insertion în limbaj C ++.
Exemplu 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 < Ieșire:
Lista de intrare este
12 4 3 1 15 45 33 21 10 2
Lista sortată este
1 2 3 4 10 12 15 21 33 45
Apoi, vom vedea implementarea Java a tehnicii de sortare Insertion.
Exemplu 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) + ' '); } } } Ieșire:
cel mai bun firewall gratuit pentru Windows 10
Lista de intrare a elementelor ...
12 4 3 1 15 45 33 21 10 2
listă sortată de elemente ...
1 2 3 4 10 12 15 21 33 45
În ambele implementări, putem vedea că începem să sortăm din 2ndelement al matricei (variabila buclă j = 1) și comparați în mod repetat elementul curent cu toate elementele sale anterioare și apoi sortați elementul pentru a-l plasa în poziția corectă dacă elementul curent nu este în ordine cu toate elementele sale anterioare.
Sortarea prin inserție funcționează cel mai bine și poate fi finalizată în mai puține treceri dacă matricea este parțial sortată. Dar pe măsură ce lista crește, performanța sa scade. Un alt avantaj al sortării prin inserție este că este un sortare stabilă, ceea ce înseamnă că menține ordinea elementelor egale din listă.
Analiza complexității algoritmului de sortare a inserției
Din pseudo-cod și din ilustrația de mai sus, sortarea prin inserție este algoritmul eficient în comparație cu sortarea cu bule sau sortarea prin selecție. În loc să utilizeze pentru buclă și condiții actuale, folosește o buclă while care nu mai efectuează pași suplimentari atunci când matricea este sortată.
Cu toate acestea, chiar dacă trecem matricea sortată la tehnica de sortare Insertion, aceasta va executa totuși bucla exterioară pentru a necesita astfel un număr de pași pentru a sorta o matrice deja sortată. Acest lucru face ca cea mai bună complexitate de timp a inserării să sorteze o funcție liniară a lui N unde N este numărul de elemente din matrice.
Astfel, diversele complexități pentru tehnica de sortare prin inserție sunt date mai jos:
Complexitatea timpului cel mai prost O (n 2) Complexitatea în cel mai bun caz Pe) Complexitatea timpului mediu O (n 2) Complexitatea spațiului O (1)
În ciuda acestor complexități, putem trage totuși concluzia că Sortarea prin inserție este cel mai eficient algoritm în comparație cu alte tehnici de sortare, cum ar fi sortarea cu bule și sortarea prin selecție.
Concluzie
Sortarea prin inserție este cea mai eficientă dintre toate cele trei tehnici discutate până acum. Aici, presupunem că primul element este sortat și apoi comparăm în mod repetat fiecare element cu toate elementele sale anterioare și apoi plasăm elementul curent în poziția sa corectă în matrice.
În acest tutorial, în timp ce discutăm despre sortarea inserției, am observat că comparăm elementele folosind un increment de 1 și, de asemenea, acestea sunt contigue. Această caracteristică are ca rezultat necesitatea mai multor permise pentru a obține lista sortată.
În viitorul nostru tutorial, vom discuta despre „Sortarea Shell”, care este o îmbunătățire față de sortarea Selecției.
În sortarea shell-ului, introducem o variabilă cunoscută sub numele de „increment” sau „gap” folosind care împărțim lista în subliste care conțin elemente necontigue care se „separă”. Sortarea Shell necesită mai puține treceri în comparație cu sortarea Insertion și este, de asemenea, mai rapidă.
În viitorele noastre tutoriale, vom învăța despre două tehnici de sortare, „Quicksort” și „Mergesort”, care utilizează strategia „Divide and conquer” pentru sortarea listelor de date.
=> Fii atent la Ghidul de instruire pentru începători C ++ aici.
Lectură recomandată