Ordenación por inserción: qué es y cómo funciona

La ordenación por inserción es un algoritmo de ordenación simple para una pequeña cantidad de elementos.

Ejemplo:

En la ordenación por inserción, compara el keyelemento con los elementos anteriores. Si los elementos anteriores son mayores que el keyelemento, mueva el elemento anterior a la siguiente posición.

Comience desde el índice 1 hasta el tamaño de la matriz de entrada.

[8 3 5 1 4 2]

Paso 1 :

 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 ]

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

Paso 3 :

 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 ]

Etapa 4 :

 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 ]

Paso 5:

 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]

El algoritmo que se muestra a continuación es una versión ligeramente optimizada para evitar intercambiar el keyelemento en cada iteración. Aquí, el keyelemento se intercambiará al final de la iteración (paso).

 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

Aquí hay una implementación detallada en JavaScript:

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 continuación, se muestra una implementación rápida en Swift:

 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 }
    

El ejemplo de Java se muestra a continuación:

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;
    

ordenación por inserción en c ....

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; } } 

Propiedades:

• Complejidad espacial: O (1)

Complejidad de tiempo: O (n), O (n * n), O (n * n) para los mejores, promedio y peores casos, respectivamente.

• Mejor caso: la matriz ya está ordenada
• Caso promedio: la matriz se ordena aleatoriamente
• Peor de caso: la matriz está ordenada de forma inversa.
• Clasificación en el lugar: sí
• Estable: si

Otros recursos:

• Wikipedia
• CS50 - YouTube
• SortInsertion - GeeksforGeeks, YouTube
• Visualización de ordenación por inserción
• Orden de inserción - MyCodeSchool
• Orden de inserción - VisuAlgo