Insertion Sort

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

A continuación se muestra el código para este tipo de ordenamiento en Python:

#INSERTION SORT

def insertionSort(prueba):
   for j in range(1,len(prueba)):

     currentvalue = prueba[j]
     posicion = j

     while posicion>0 and prueba[posicion-1]>currentvalue:
         prueba[posicion]=prueba[posicion-1]
         posicion = posicion-1

     prueba[posicion]=currentvalue

prueba = [54,26,93,17,77,31,44,55,20]
insertionSort(prueba)

print(prueba)