Sortarea prin inserție este un algoritm simplu de sortare pentru un număr mic de elemente.

Exemplu:

În sortare prin inserție, comparați key element cu elementele anterioare. Dacă elementele anterioare sunt mai mari decât key element, apoi mutați elementul anterior în poziția următoare.

Începeți de la indexul 1 până la dimensiunea matricei de intrare.

[ 8 3 5 1 4 2 ]

Pasul 1 :

[ 8 3 5 1 4 2 ]
      key = 3 //starting from 1st index.

      Here `key` will be compared with the previous elements.

      In this case, `key` is compared with 8. since 8 > 3, move the element 8
      to the next position and insert `key` to the previous position.

      Result: [ 3 8 5 1 4 2 ]

Pasul 2 :

[ 3 8 5 1 4 2 ]
      key = 5 //2nd index

      8 > 5 //move 8 to 2nd index and insert 5 to the 1st index.

      Result: [ 3 5 8 1 4 2 ]

Pasul 3 :

[ 3 5 8 1 4 2 ]
      key = 1 //3rd index

      8 > 1     => [ 3 5 1 8 4 2 ]  

      5 > 1     => [ 3 1 5 8 4 2 ]

      3 > 1     => [ 1 3 5 8 4 2 ]

      Result: [ 1 3 5 8 4 2 ]

Pasul 4:

[ 1 3 5 8 4 2 ]
      key = 4 //4th index

      8 > 4   => [ 1 3 5 4 8 2 ]

      5 > 4   => [ 1 3 4 5 8 2 ]

      3 > 4   ≠>  stop

      Result: [ 1 3 4 5 8 2 ]

Pasul 5:

[ 1 3 4 5 8 2 ]
      key = 2 //5th index

      8 > 2   => [ 1 3 4 5 2 8 ]

      5 > 2   => [ 1 3 4 2 5 8 ]

      4 > 2   => [ 1 3 2 4 5 8 ]

      3 > 2   => [ 1 2 3 4 5 8 ]

      1 > 2   ≠> stop

      Result: [1 2 3 4 5 8]
[ 1 2 3 4 5 8 ]

Algoritmul prezentat mai jos este o versiune ușor optimizată pentru a evita schimbarea key element în fiecare iterație. Aici key elementul va fi schimbat la sfârșitul iterației (pas).

    InsertionSort(arr[])
      for j = 1 to arr.length
         key = arr[j]
         i = j - 1
         while i > 0 and arr[i] > key
            arr[i+1] = arr[i]
            i = i - 1
         arr[i+1] = key

Iată o implementare detaliată în JavaScript:

function insertion_sort(A) {
    var len = array_length(A);
    var i = 1;
    while (i < len) {
        var x = A[i];
        var j = i - 1;
        while (j >= 0 && A[j] > x) {
            A[j + 1] = A[j];
            j = j - 1;
        }
        A[j+1] = x;
        i = i + 1;
    }
}

O implementare rapidă în Swift este prezentată mai jos:

  var array = [8, 3, 5, 1, 4, 2]

  func insertionSort(array:inout Array<Int>) -> Array<Int>{
      for j in 0..<array.count {
          let key = array[j]
          var i = j-1

          while (i > 0 && array[i] > key){
              array[i+1] = array[i]
              i = i-1
          }
          array[i+1] = key
      }
      return array
  }

Exemplul Java este prezentat mai jos:

public int[] insertionSort(int[] arr)
      for (j = 1; j < arr.length; j++) {
         int key = arr[j]
         int i = j - 1
         while (i > 0 and arr[i] > key) {
            arr[i+1] = arr[i]
            i -= 1
         }
         arr[i+1] = key
      }
      return arr;

inserție sortare în c ….

void insertionSort(int arr[], int n) 
{ 
   int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = arr[i]; 
       j = i-1;
       while (j >= 0 && arr[j] > key) 
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       } 
       arr[j+1] = key; 
   } 
} 

Proprietăți:

  • Complexitate spațială: O (1)

Complexitatea timpului: O (n), O (n * n), O (n * n) pentru cele mai bune, medii, respectiv cele mai grave cazuri.

  • Cel mai bun caz: matricea este deja sortată
  • Caz mediu: matricea este sortată aleatoriu
  • Cel mai rău caz: matricea este sortată invers.
  • Sortare în loc: Da
  • Stabil: Da

Alte resurse: