Algoritm de sortare a inserției

În acest tutorial, veți afla cum funcționează sortarea prin inserare. De asemenea, veți găsi exemple de lucru de sortare a inserției în C, C ++, Java și Python.

Sortarea prin inserție funcționează similar, așa cum sortăm cărțile în mână într-un joc de cărți.

Presupunem că prima carte este deja sortată, apoi selectăm o carte nesortată. Dacă cardul nesortat este mai mare decât cardul în mână, acesta este plasat în dreapta altfel, în stânga. În același mod, alte cărți nesortate sunt luate și puse la locul lor potrivit.

O abordare similară este utilizată de sortarea prin inserție.

Sortarea prin inserție este un algoritm de sortare care plasează un element nesortat la locul potrivit în fiecare iterație.

Cum funcționează sortarea prin inserare?

Să presupunem că trebuie să sortăm următoarea matrice.

Matricea inițială
  1. Se presupune că primul element din matrice este sortat. Luați al doilea element și păstrați-l separat în key.
    Comparați keycu primul element. Dacă primul element este mai mare decât key, atunci cheia este plasată în fața primului element. Dacă primul element este mai mare decât cheia, atunci cheia este plasată în fața primului element.
  2. Acum, primele două elemente sunt sortate.
    Luați al treilea element și comparați-l cu elementele din stânga acestuia. Așezat-o chiar în spatele elementului mai mic decât acesta. Dacă nu există nici un element mai mic decât acesta, atunci așezați-l la începutul matricei. Plasați 1 la început
  3. În mod similar, așezați fiecare element nesortat în poziția corectă. Plasați 4 în spatele 1 Plasați 3 în spatele 1 și matricea este sortată

Algoritm de sortare a inserției

 insertionSort (matrice) marchează primul element ca sortat pentru fiecare element nesortat X „extrage” elementul X pentru j X deplasează elementul sortat la dreapta cu o buclă de pauză și introduceți X aici la sfârșitul insertionSort

Exemple Python, Java și C / C ++

Python Java C C ++ 
 # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)
  // Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )
 // Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )

Complexitate

Complexități de timp

  • Cel mai prost caz de complexitate: Să presupunem că o matrice este în ordine crescătoare și doriți să o sortați în ordine descrescătoare. În acest caz, apare cel mai rău caz de complexitate. Fiecare element trebuie comparat cu fiecare dintre celelalte elemente, astfel încât, pentru fiecare al n-lea element, se fac numărul de comparații. Astfel, numărul total de comparații =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Complexitatea celui mai bun caz: O(n)
    Când matricea este deja sortată, bucla exterioară rulează de mai nmulte ori, în timp ce bucla interioară nu rulează deloc. Deci, există doar un nnumăr de comparații. Astfel, complexitatea este liniară.
  • Complexitatea medie a cazurilor: apare atunci când elementele unui tablou sunt în ordine amestecată (nici crescătoare, nici descendentă).O(n2)

Complexitatea spațială

Complexitatea spațiului se O(1)datorează faptului că keyse utilizează o variabilă suplimentară .

Aplicații de sortare prin inserție

Sortarea prin inserție este utilizată atunci când:

  • matricea are un număr mic de elemente
  • rămân doar câteva elemente de sortat

Articole interesante...