Beszúrás rendezése: Mi ez, és hogyan működik

A beszúrás rendezése egy egyszerű rendezési algoritmus kis számú elemhez.

Példa:

A Beszúrás rendezés mezőben összehasonlítja az keyelemet az előző elemekkel. Ha az előző elemek nagyobbak, mint az keyelem, akkor az előző elemet a következő pozícióba helyezi.

Kezdje az 1. indextől a bemeneti tömb méretéig.

[8 3 5 1 4 2]

1. lépés :

[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 ]

2. lépés :

[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 ]

3. lépés:

[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 ]

4. lépés:

[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 ]

5. lépés:

[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]

Az alább látható algoritmus egy kissé optimalizált verzió, hogy elkerülje az keyelem cseréjét minden iterációban. Itt az keyelem az iteráció (lépés) végén felcserélődik.

 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

Itt van egy részletes megvalósítás a JavaScript-ben:

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

A Swift gyors megvalósítása az alábbiakban látható:

 var array = [8, 3, 5, 1, 4, 2] func insertionSort(array:inout Array) -> Array{ for j in 0..
    
      0 && array[i] > key){ array[i+1] = array[i] i = i-1 } array[i+1] = key } return array }
    

A Java példa az alábbiakban látható:

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

beszúrás rendezés c-ben ....

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

Tulajdonságok:

  • Tér összetettsége: O (1)

Időkomplexitás: O (n), O (n * n), O (n * n) a legjobb, az átlagos, a legrosszabb esetben.

  • Legjobb eset: a tömb már rendezve van
  • Átlagos eset: a tömb véletlenszerűen van rendezve
  • Legrosszabb eset: a tömb fordított rendezésű.
  • Rendezés helyben: Igen
  • Istálló: Igen

Egyéb források:

  • Wikipédia
  • CS50 - YouTube
  • SortInsertion - GeeksforGeeks, YouTube
  • Beszúrás Rendezés vizualizáció
  • Beszúrási rendezés - MyCodeSchool
  • Beszúrási rendezés - VisuAlgo