Sortare inserare: algoritm cu C, C++, Java, Python Exemple
Sarah Chen
Ce este Insertion Sort?
Sortarea prin inserție este unul dintre algoritmii de sortare prin comparație utilizați pentru a sorta elemente prin iterarea pe un element la un moment dat și plasând elementul în poziția corectă.
Fiecare element este inserat secvenţial într-o listă deja sortată. Mărimea listei deja sortate inițial este una. Algoritmul de sortare prin inserție asigură că primele k elemente sunt sortate după a k-a iterație.
Caracteristicile algoritmului de sortare prin inserție
Algoritmul pentru sortarea prin inserare are următoarele caracteristici importante:
- Este o tehnică de sortare stabilă, deci nu modifică ordinea relativă a elementelor egale.
- Este eficient pentru seturi de date mai mici, dar nu este eficient pentru liste mai mari.
- Sortarea prin inserare este adaptativă, ceea ce reduce numărul total de pași dacă este sortată parțial. Mulțime este furnizat ca intrare pentru a-l face eficient.
Cum se inserează Operamunca de tion?
În algoritmul Insertion Sort, operația de inserare este utilizată pentru sortarea elementelor nesortate. Ajută la inserarea unui element nou într-o listă deja sortată.
Pseudocod al operației de inserare:
Să considerăm o listă A de N elemente.
A[N-1] is the element to be inserted in the sorted sublist A[0..N-2]. For i = N-1 to 1: if A[i] < A[i-1], then swap A[i] and A[i-1] else Stop
În exemplul de mai sus, un nou element 6 urmează să fie inserat într-o listă deja sortată.
Pas 1) În comparație cu elementul adiacent stâng al lui A[5], 9 > 6, schimbăm poziția lui 9 și 6. Acum elementul 6 este mutat în A[4].
Pas 2) Acum, comparăm A[4] și A[3] și aflăm că A[3] > A[4], schimbăm din nou poziția lui 6 și 8.
Pas 3) Acum comparați A[3] și A[2], deoarece A[2] > A[3] schimbă poziția lui 7 și 6.
Pas 4) Comparăm A[1] și A[2], iar ca A[1] < A[2], adică elementul adiacent din stânga nu mai este mai mare. Acum ajungem la concluzia că 6 este introdus corect și oprim algoritmul aici.
Cum funcționează sortarea inserției
Operația de inserare discutată mai sus este coloana vertebrală a sortării de inserare. Procedura de inserare este executată pe fiecare element și, în final, obținem lista sortată.
Figura de exemplu de mai sus demonstrează funcționarea sortării prin inserare în structura datelor. Inițial, în sublista sortată există un singur element, adică 4. După inserarea A[1] adică 3, dimensiunea sublistei sortate crește la 2.
C++ Program de sortare prin inserare
#include <iostream>
using namespace std;
int main(){
//unsorted list
int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
//size of list
int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);
//printing unsorted list
cout << "\nUnsorted: ";
for(int i = 0 ; i < size_unsorted ; i++){
cout << unsorted[i] << " ";
}
int current_element,temp;
for(int i = 1; i < size_unsorted; i++){
current_element = unsorted[i];
for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
//swapping if current element is lesser
temp = unsorted[j+1];
unsorted[j+1] = unsorted[j];
unsorted[j] = temp;
}
}
//printing sorted list
cout << "\nSorted: ";
for(int i = 0 ; i < size_unsorted ; i++){
cout << unsorted[i] << " ";
}
return 0;
}
ieșire:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Cod C pentru sortarea inserției
#include <stdio.h>
int main() {
//unsorted list
int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
//size of list
int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);
//printing unsorted list
printf("\nUnsorted: ");
for(int i = 0 ; i < size_unsorted ; i++){
printf("%d ", unsorted[i]);
}
int current_element, temp;
for(int i = 1; i < size_unsorted; i++){
current_element = unsorted[i];
for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
//swapping if current element is lesser
temp = unsorted[j+1];
unsorted[j+1] = unsorted[j];
unsorted[j] = temp;
}
}
//printing sorted list
printf("\nSorted: ");
for(int i = 0 ; i < size_unsorted ; i++){
printf("%d ", unsorted[i]);
}
return 0;
}
ieșire:
Output: Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Python Program de sortare prin inserare
#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]
#size of list
size_unsorted = len(unsorted)
#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
print(unsorted[i], end=" ")
for i in range(1, size_unsorted):
current_element = unsorted[i]
j = i - 1
while j >= 0 and unsorted[j] > current_element:
#swapping if current element is lesser
unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
j -= 1
#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
print(unsorted[i], end=" ")
ieșire:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Proprietăți ale sortării inserției
Iată proprietățile importante ale sortării prin inserție:
- online: Sortarea prin inserție poate sorta elementele pe măsură ce le primește. Adică, dacă am sortat deja o listă de elemente și am adăugat câteva elemente la liste, atunci nu este nevoie să rulăm din nou întreaga procedură de sortare. În schimb, trebuie să repetăm doar elementele nou adăugate.
- La loc: Complexitatea spațială a algoritmului de sortare prin inserare este constantă și nu necesită spațiu suplimentar. Acest algoritm sortează elementele la locul lor.
- Grajd: În sortarea prin inserție, nu schimbăm elementele dacă valorile lor sunt egale. De exemplu, două elemente, x și y, sunt egale, iar x apare înaintea y în listele nesortate, apoi în lista sortată, x va apărea înaintea y. Acest lucru face sortarea prin inserare stabilă.
- Adaptiv: A algoritm de sortare este adaptiv dacă durează mai puțin timp dacă elementele de intrare sau subsetul de elemente sunt deja sortate. După cum am discutat mai sus, cel mai bun timp de rulare pentru sortarea inserției este O(N), iar cel mai prost timp de rulare este O(N^2). Sortarea prin inserție este unul dintre algoritmii de sortare adaptivă.
Complexitatea sortării inserției
Complexitatea spațială
Sortarea prin inserare nu necesită spațiu suplimentar pentru sortarea elementelor, complexitatea spațiului este constantă, adică O(1).
Complexitatea timpului
Deoarece sortarea prin inserție iterează fiecare element simultan, necesită N-1 treceri pentru a sorta N elemente. Pentru fiecare trecere, poate face zero schimburi dacă elementele sunt deja sortate sau schimb dacă elementele sunt aranjate în ordine descrescătoare.
- Pentru trecerea 1, schimburile minime necesare sunt zero, iar swapurile maxime necesare sunt 1.
- Pentru trecerea 2, schimburile minime necesare sunt zero, iar swapurile maxime necesare sunt 2.
- Pentru trecerea N, schimbul minim necesar este zero, iar swapurile maxime necesare sunt N.
- Schimbarea minimă este zero, deci cea mai bună complexitate de timp este O(N) pentru repetarea N treceri.
- Schimburile maxime totale sunt (1+2+3+4+..+N) i. N(N+1)/2, cea mai proastă complexitate de timp este O(N^2).
Iată complexitatea de timp importantă a sortării inserției:
- Complexitatea celui mai rău caz: O(n2): Sortarea unui tablou în ordine descrescătoare atunci când este în ordine crescătoare este cel mai rău caz.
- Complexitatea celui mai bun caz: O(n): Complexitatea celui mai bun caz apare atunci când matricea este deja sortată, bucla exterioară rulează de n număr de ori, în timp ce bucla interioară nu rulează deloc. Există doar n număr de comparații. Deci, în acest caz, complexitatea este liniară.
- Complexitatea medie a cazului: O(n2): Se întâmplă atunci când elementele unui tablou apar în ordinea amestecată, care nu este nici ascendentă, nici descendentă.
Rezumat
- Sortarea prin inserție este o metodă de algoritm de sortare care se bazează pe comparație.
- Este o tehnică de sortare stabilă, deci nu modifică ordinea relativă a elementelor egale.
- Pe fiecare element, operația de inserare este utilizată pentru a insera elementul în sublista sortată.
- Sortarea prin inserare este un algoritm de sortare in loc.
- Cea mai slabă și medie complexitate de timp a sortării de inserție este pătratică, adică O(N^2).
- Sortarea prin inserție nu necesită spațiu auxiliar.
