Insertion sort

Después de dos horas y mas de 3 hojas bond compilando pude entender el método insertion xd

Algoritmo realizado con javascript y apoyado en angular para mostrar gráficamente el proceso que se llevó a cabo en el ordenamiento:

https://stackblitz.com/edit/ckupb1-insertion-sort

Mi solucion, muestra paso por paso como se van moviendo los datos

#include <stdio.h>
#include <stdlib.h>

void mostrar(int array[],int cantidadEspacios){
    for(int i = 0;i < cantidadEspacios;i++){
        printf("[ %d ]",array[i]);
    }
}

void sort(int array[], int cantidadEspacios){
    int temp, pos;
    for(int i = 1; i < cantidadEspacios;i++){
            pos = i;
            temp = array[i];
            printf("\nPaso n° %d, Voy a trabajar con el (%d) en su posicion %d\n",pos, temp ,i);
         for(int j = i;j > 0;j--){
            if(temp < array[j-1]){
                array[j] = array[j - 1];
                array[j - 1] = temp;
                pos--;
        printf("\nEl %d se movio a la posicion %d\n",array[pos] ,pos);
        for(int h = 0;h < cantidadEspacios;h++){
            if(h == pos){
                printf("[(%d)]",array[h]);
            }else{
                printf("[ %d ]",array[h]);
            }
        }
            }else if(j <= 1){
                 printf("\n¡El %d no se movio de posicion!\n",array[pos] );
            }

    }
}
      printf("\nArray ordenado\n");
      mostrar(array,cantidadEspacios);
}

int main() {
    int array[] = {3,5,1,2,4,8,7,9,12,61,34,-4,-6,100};
    int cantidadEspacios = sizeof(array)/sizeof(array[0]);
    printf("Array desordenado\n\n");
    mostrar(array,cantidadEspacios);
    printf("\n");
    sort(array,cantidadEspacios);
    return 0;
}

Y la clase y la explicación??? Así no me gusta! 👎👎👎💻

Está es mi implementación en Python

def insertion_sort(list, n):
    for i in range(0, len(list)):
        current_value = list[i]
        position = i
        while position > 0 and list[position-1] > current_value:
            list[position] = list[position-1]
            position-=1
        list[position] = current_value
        print(f"Round {i}: {list}")

def run():
    list = [50, 83, 64, 0, 12, 46, 45, 54, 14, 78, 23, -1]
    n = len(list)
    insertion_sort(list, n)
    print(list)

if __name__ == '__main__':
    run()

EL codigo en Python ascendente y descendente

import random


def insert_sort(array, n, asc=True):
    for i in range(1, n):
        current_value = array[i]
        j = i - 1

        if asc:
            while j >= 0 and current_value < array[j]:
                array[j+1] = array[j]
                j -= 1
        elif not asc:
            while j >= 0 and current_value > array[j]:
                array[j+1] = array[j]
                j -= 1

        array[j+1] = current_value
    return array


def main():
    array = [random.randint(-1000, 1000) for i in range(100)]
    n = len(array)
    insert_sort(array, n)
    print(array)

    insert_sort(array, n, asc=False)
    print(array)


if __name__ == "__main__":
    main()

En Python

# Insertion sort algorithm in Python
# From lowest to highest

def insertion_sort(list, n):
    for i in range(1, len(list)):
        current_value = list[i]
        j = i
        while j > 0 and list[j - 1] > current_value:
            list[j] = list[j -1]
            j = j - 1
        list[j] = current_value
        print(f"Round {i}: {list}")

def run():
    list = [60, 30, 20, 10, 50, 1, 90] 
    print(list)
    n = len(list)
    insertion_sort(list, n)
    print(list)

if __name__ == "__main__":
    run()```

Mi codigo en Python 3.7:

"""
Lista de Pasos de nuestro Algoritmo Insertion-Sort:
•	Crear un array de determinado tamaño indicado por el usuario.
•	Llenar el array con los respectivos elementos dados por el usuario.
•	Comparar los dos primeros elementos del array, luego los 3 primeros, y así sucesivamente hasta el final.
•	Comparar y preguntar cual es más grande entre el primero y segundo elemento, si el segundo es mayor se deja igual en las mismas posiciones, 
    pero si el primero es mayor se cambian las posiciones del menor y los mayores se corren hacia arriba, luego se compara los 3 primeros para 
    saber cuál es mayor, comparando el último con los dos primeros, después comparar los 4 primeros, se compara el último con los 3 primeros, 
    esto se repite hasta recorrer todos los elementos del array.
•	Detener el ciclo cuando se llegue al índice final y se compare el ultimo elementos con los demás, por lo tanto podemos romper el ciclo para terminar las iteraciones.
•	Mostrar al usuario el array ordenado.
"""
import copy

flag = True    #Bandera para indicar si ya quedo ordenada la lista

def insertionList(lista1,n):    #Funcion para ordenar el Array o Lista con el método insertion-sort   
    lista2 = copy.copy(lista1)
    conteo = 1
    for i,v in enumerate(lista1):   #La i representa el indice y la v respresenta el valor de ese indice
        conteo +=1
        if(conteo > n ):
            break
        lista3 = lista2[:conteo]    #Se forma pequeñas lista, emepezando por las primeras posiciones.
        ultimo = lista3[-1]         #Sacamos el último elemento de la lista nueva
        for i1,v1 in enumerate(lista3):
            if(v1 > ultimo):     #Valida si el último valor es menor que los demas elementos de la lista
                lista4 = []
                lista4.append(lista2[i1])
                lista2[i1] = ultimo
                lista2[(i1 + 1):] = lista4 + lista2[(i1+1):(conteo-1)] + lista2[conteo:]
                1+1
                break

    return lista2

def getList(n = 0):  #Función para crear el Array o Lista
    lista1 = []
    for i in range(n):
        elemento = int(input("Ingrese el entero en el indice {}:".format(i)))
        lista1.append(elemento)
    return lista1

    
size_list = int(input("Ingrese el tamaño del Array:"))
lista = getList(size_list)
lista_ordenada = insertionList(lista,size_list)
print("Array original: {}".format(lista))
print("Array ordenada: {}".format(lista_ordenada))```

Funcionó jajajaja que alegría y qué emoción me dio 😃

#include <stdio.h>
#include <math.h>

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

void printArray(int arr[], int n)
{
    int i;
    for (i=0; i < n; i++)
        printf("%d ", arr[i] );
            printf("\n");
}

int main(int argc, char const *argv[]) {
  int arr[] = {6, 4, 3, 11, 10};
  int n = sizeof(arr)/sizeof(arr[0]);
  insertionSort(arr, n);
  printArray(arr, n);
  return 0;
}

Aquí en JS:

Mi código en Java:

public void insertionSort(int[] arr) {

        final int n = arr.length;

        for (int i = 1; i < n; i++) {
            final int currentValue = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > currentValue) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = currentValue;
            
        }

    }

Python

def insertion_sort(lista):
    n = len(lista)
    for i in range(0, n):
        valorAct = lista[i]
        j = i
        while j > 0 and lista[j-1] > valorAct:
            lista[j] = lista[j-1]
            j -= 1
        lista[j] = valorAct


def main():
    lista = [45,65,87,9,42,1,6,0,5,-34,-266,5,21]
    print(f'\nLista original:\n\n{lista}')
    insertion_sort(lista)
    print(f'\nLista ordenada:\n\n{lista}')

if __name__ == '__main__':
    main()

Les comparto este video para reforzar los conocimientos de esta clase:

https://www.youtube.com/watch?v=lYNyL0HuWSg&ab_channel=ProgramaciónATS

En JS💛

var list = [5,2,4,3,1]

function insertion_sort(list) {
    var j,currentVal

    for (let index = 1; index < list.length; index++) {
        currentVal=list[index]
        j=index-1
        while (j>=0 && list[j]>currentVal) {
            list[j+1] = list[j]
            j=j-1
        }
        list[j+1]=currentVal
    }
    console.log(list)
}

insertion_sort(list)

Así como en el ejercicio anterior tengo una sola duda…
en:
for (i = 1; i < n; i++) { currentVal= arr[i]; j = i-1; }

No se indica en cuánto se inicia n, cómo se hace esta comparación?

la version con adecente o descendente

#include <stdio.h> 
#include <math.h> 
#include <stdbool.h>
  
/* Función de insertion Sort*/
void insertionSort(int arr[], int n, bool acc) 
{ 
   int i, currentVal, j; 
   for (i = 1; i < n; i++) 
   { 
       currentVal= arr[i]; //obtenemos el valor actual a comparar
       j = i-1;
  
       /* mueve los elementos del arreglo arr[0..i-1],que son mayores que el valor de la posición actual del recorrido, a una posición adelante de su posición actual */
        if(acc){
           while (j >= 0 && arr[j] > currentVal){ 
               arr[j+1] = arr[j]; 
               j = j-1; 
            }
        }else{
            while (j >= 0 && arr[j] < currentVal){ 
               arr[j+1] = arr[j]; 
               j = j-1; 
            }
        } 
        arr[j+1] = currentVal; 
   } 
} 
  
// función auxiliar para imprimir un arrary de tamaño n 
void printArray(int arr[], int n) 
{ 
   int i; 
   for (i=0; i < n; i++) 
       printf("%d ", arr[i]); 
   printf("\n"); 
} 
  
  
  
/* Driver program to test insertion sort */
int main() 
{ 
    int arr[] = {6, 4, 3, 11, 10}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    insertionSort(arr, n, true); 
    printArray(arr, n); 
    insertionSort(arr, n, false); 
    printArray(arr, n); 
  
    return 0; 
}

tengo una duda se puede en c el tener un valor por defecto en la función porque sino me recuerdo mal en c++ se hacia así

void insertionSort(int arr[], int n, bool acc = true)

pero no me compila si no pongo el argumento y me dice un esperaba un cierre de paracentesis. es posible hacerlo en c o no?

Me tomó un rato entenderlo, lo que hice para comprende fue ir sustituyendo y haciendo el algoritmo primero mentalmente, haciendo eso me quedó claro cómo funciona el código

def insertion_sort(numbers):
    n = len(numbers)

    for i in range(1, n):
        current_value = numbers[i]
        j = i - 1

        while j >= 0 and numbers[j] > current_value:
            numbers[j + 1] = numbers[j]
            j -= 1

        numbers[j + 1] = current_value

    return numbers


if __name__ == "__main__":
    numbers = [6 , 4, 3, 11, 10]
    print(numbers)
    ordered_numbers = insertion_sort(numbers)
    print(ordered_numbers)

Mi solucion en JavaScript

<code>
const list1 =[-796, 3229, -5164, -362, 4408, 8965, -6068, 9329, -3034, -443, -6693, 9497, 2615, -5966, -9065, -1160, 6148, 5517, 1123, -8887, 5649, 3302, -1176, -8542, -9166, 8, -2906, 8987, -2414, -7984, 4410, 8872, 5241, -4556, 59, -5562, -3877, 7452, -4467, 2076, 4076, 4297, -3847, -2055, 4483, -1484, -2371, 6199, -7261, -7032, 6010, 2325, -6625, -2601, 3870, 1822, -5665, 9622, 9883, -5794, -5218, 2926, 8599, -3099, 6399, -2570, 3943, -2409, 5114, 9791, -4420, 1065, 3077, -1062, -8004, 4397, 1635, 8578, -9226, 9222, -1793, -2691, -5060, -4727, -4098, 946, -6558, -4111, 4575, -2685, -4729, -5277, 1936, 5106, -2089, 824, 9421, -1683, -2083, 7891, -2099, 1305, -9076, -3535, 2565, -2871, 9448, 7177, -8614, -9954, -362, 1455, -8834, -9846, -8412, 1175, -1981, -5991, 7201, -1997, -5156, -1634, -9803, 1032, 9551, -6153, 8502, 3536, -2980, 8681, -9210, 4408, 8780, -916, -369, -8651, 1246, -702, -5555, 23, 8208, 2037, 6941, 9545, -5147, 5063, -8358, 2772, 8553, 9885, 4624, -3576, 9131, 1229, -429, -479, -673, -7060, -4031, 5650, 6679, 6796, 5622, -6256, -238, -6096, 3096, -1610, -2948, 6291, -1666, 5219, 5850, 7387, -3260, 3672, -1766, -9941, 8252, 2649, 7079, -8026, 6356, 676, -5065, -6338, 3287, 680, -3269, 2770, 6637, -8744, 9162, -2204, -3066, -7228, 8762, 1505, 4957, 766, -9136, 4632, -5022, -9999, 5361, 2732, 7831, -501, -4650, 7236, 3682, -2438, 5574, -8230, -9669, -7442, 7966, -2905, 7629, 7137, 200, -8670, -749, 2228, 458, 7889, -3668, -5350, -3261, 6741, -6953, 4800, 3372, 6662, -1018, 8523, 3164, 3577, 9720, -6826, -1574, -7875, -2796, -1078, -4755, 4926, 3368, 4302, 9254, 6410, -4689, 7878, 2461, 8233, -6688, 5904, 4735, -2940, 8830, 9976, -3674, 4222, -1446, 6187, -3181, -8882, 5487, -6939, -7885, 3786, -6234, -1062, -4553, -5709, 8459, 5008, 3352, 6586, 537, -7610, 3261, 8246, -2105, 5107, 7957, -7886, -2925, -2541, -7449, 9521, 5073, -239, -8054, -4379, -8323, -6485, -4828, -5294, -2720, 595]
console.log(list1)


function enlist(l, num) { //comparo una lista con un numero unico que sale de la lista madre y lo incerto en una lista nueva segun su orden con respecto a ella 
	for(let numOfList of l){
		if (num <= numOfList) {
			l.splice(l.indexOf(numOfList),0,num)
			return l
		}else if(num > numOfList){
			if(num < l[l.indexOf(numOfList)+1]){
				l.splice(l.indexOf(numOfList)+1,0,num)
				return l
			}else if (l.indexOf(numOfList)+1 === l.length){
				l.push(num)
				return l
			}else{
				continue
			}				
		}
	}
}

function insertionSort2(l) { //funcion madre que entrega los datos para ser ordenados a la funcion enlist()
	let limit = l.length
	let listReturn = []
	listReturn.push(l[0])
	l.shift()
	while(listReturn.length < limit){
		listReturn = enlist(listReturn,l[0])
		l.shift()
	}
	console.log(listReturn)
	return listReturn
}

insertionSort2(list1)
</code>

Mi solución para C#

    class Insercion
    {
        /// <summary>
        /// La funcion InsertionSort recorre un array posición por posición y en caso de ser menor,
        /// lo coloca en la posición indicada para ordenar de menor a mayor.
        /// </summary>
        /// <param name="p_array_entrada"> El array con los elementos para ordenar</param>
        public void InsertionSort(int[] p_array_entrada) {

            //Declaracion de variables auxiliares i e j
            int i, j;

            //Variable auxiliar para almacenar el valor actual
            int valor_actual;
                        
            for ( i = 1; i < p_array_entrada.Length; i++ )
            {
                
                valor_actual = p_array_entrada[i];
                j = i - 1;

                while ( j >= 0 && p_array_entrada[j] > valor_actual)
                {
                    p_array_entrada[j + 1] = p_array_entrada[j];
                    j -= 1;

                }// Final de: while ( j >= 0 && p_array_entrada[j] < valor_actual)

                p_array_entrada[j + 1] = valor_actual;

            }// Final de: for ( i = 0; i < p_array_entrada.Length; i++ )

        }// Final de: public void InsertionSort(int [] p_array_entrada) 

        /// <summary>
        /// Funcion para recorrer el array y mostrarlo por consola.
        /// </summary>
        /// <param name="p_array_entrada"> El Array a mostrar.</param>
        public void MostrarArray( int[] p_array_entrada ) {

            // Por cada uno de los valores dentro del array de entrada
            Console.Write("- ");
            foreach (int numero in p_array_entrada)
            {
                // Mostrar por consola
                Console.Write(" {0} ",numero);
            }

            Console.WriteLine(" - ");

        }// Final de: public void MostrarArray(int[] p_array_entrada)

        /// <summary>
        /// Llama a las funciones necesarias para mostrar el array original por consola, ordenarlo y mostrar la nueva salida.
        /// </summary>
        /// <param name="p_array_entrada"> El array a ordenar</param>
        public void OrdenarConInsertionSort( int[] p_array_entrada ) {

            // Mensaje de Bienvenida
            Console.WriteLine("------------------------------------------------------------");
            Console.WriteLine("Ejercicio Platzi - Mi solución de Insertion Sort para C#.");
            Console.WriteLine("------------------------------------------------------------");
            
            // Mostrar Array original
            Console.WriteLine("Array Original:");
            MostrarArray(p_array_entrada);
            Console.WriteLine("------------------------------------------------------------");
            
            // Mostrar Array Ordenado con Insertion Sort
            Console.WriteLine("Array ordenado con Insertion Sort:");
            InsertionSort(p_array_entrada);
            MostrarArray(p_array_entrada);
            
            Console.WriteLine("------------------------------------------------------------");
            Console.WriteLine("Finalizado - ¡Nunca pares de aprender! 8) ");
            Console.WriteLine("------------------------------------------------------------");

        }// Fin de: public void OrdenarConInsertionSort()


        // Codigo para ejecutar en el main
        //
        //Insercion insercion = new Insercion();
        //int[] p_array_entrada = new int[] { 5, 10, 20, 30, 4, 3 };
        //insercion.OrdenarConInsertionSort(p_array_entrada);               
        //Console.ReadKey();


    }// Final de: class Insercion```

Tuve que tomar lapiz y papel, para recorrer el código, y una hora treinta minutos para poder comprender como funciona el algoritmo pero es gratificante cuando lo logras

en java

public class InsertionSort {

    public void inserionSort(int []values){
        int positionActual =0;
        int j=0;
        for (int i = 1; i <values.length ; i++) {
            positionActual = values[i];
            j= i-1;
            while (j>=0 && (values[j] > positionActual) ){
                values[j+1]= values[j];
                j = j-1;
            }
            values[j+1]= positionActual;
        }
    }

    public void printValues(int [] values){
        for (int i = 0; i <values.length ; i++) {
            System.out.println(values[i] + " ");
        }
    }
}
*******************************************************
public class Main {

    public static void main(String[] args) {
        int [] values = {5,4,7,6,3};

        InsertionSort insertionSort1 = new InsertionSort();
        insertionSort1.inserionSort(values);
        System.out.println("valores ordenados ");
        insertionSort1.printValues(values);
    }
}

Comprato mi código en C#

using System;

namespace InsertionSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arreglo = new int[] { 15, -6, 35, 12, 25, -9, 9, 7 };
            Console.WriteLine("\nArreglo original:");
            ImprimirArreglo(arreglo);
            Console.WriteLine("\nArreglo ordenado:");
            ImprimirArreglo(InsertionSort(arreglo));
            Console.WriteLine("\n");
        }

        static int[] InsertionSort(int[] arregloEntrada)
        {
            for (int i = 0; i < arregloEntrada.Length - 1; i++)
            {
                for (int j = i + 1; j > 0; j--)
                {
                    if (arregloEntrada[j - 1] > arregloEntrada[j])
                    {
                        int temp = arregloEntrada[j - 1];
                        arregloEntrada[j - 1] = arregloEntrada[j];
                        arregloEntrada[j] = temp;
                    }
                }
            }
            return arregloEntrada;
        }
        public static void ImprimirArreglo(int[] arregloEntrada)
        {
            foreach (int i in arregloEntrada)
            {
                Console.Write(i.ToString() + "  ");
            }
        }
    }
}

Esta es mi implementación sin mirar el código de Ricardo

#include <stdio.h>

void swap (int *p1, int *p2)
{
  int buffer = *p1;
  *p1 = *p2;
  *p2 = buffer;
}

void insertionSort(int array[], int n)
{
  for (int i = 0; i < n-1; i++)
  {
    array[i];
    while(array[i] > array[i+1])
    {
      swap(&array[i],&array[i+1]);
      if (i != 0){
        i--;
      }
    }
  }
}

void printArray(int array[], int n)
{
  int i;
  printf("[");
    for (i = 0; i < 10; i++)
    {
      printf("%d, ", array[i]);
    }
    printf("]\n");
}

int main(int argc, char const *argv[]) {
  int array[10] = {5,4,8,6,7,9,1,3,2,0};
  int n = sizeof(array)/sizeof(array[0]);

  printArray(array, n);
  insertionSort(array, n);
  printArray(array, n);

  return 0;
}

He probado el script del ejemplo y me falla. He tenido que hacerle algunas modificaciones para que funcione:

creo que se necesita practicarlo para aprender a ejecutarlo bien

No llegue a entender la lógica de este algoritmo 😦

Lo revise varias veces y en ocasiones me confundia bastante, finalmente creo haber entendido este algoritmo.

Mucha practica para entender el funcionamiento de cada linea de codigo.

Hacerlo tiende a resultar mejor para entender el código.

Aquí mi solución en Python, funcionó con los vectores que usé, pero si lo quieren probar con otros, adelante. 😃

mi solución considerando un array de tamaño dinámico y valores aleatorios:

var boton1 = document.getElementById('boton1');
boton1.addEventListener("click", crearArray);
var boton2 = document.getElementById('boton2');
boton2.addEventListener("click", insertionSort);
t = document.getElementById('txt1')
var array = [];
var bandera = 0;

function crearArray(){
  var tamano = parseInt(t.value);
  if (bandera == 0) {
    for (var i = 0; i < tamano; i++){

      array.push(aleatorio(1,10));
    }
    bandera = 1;
  } else {
    for(var a in array){
      array[a] = aleatorio(1,10);
    }
  }
  console.log(array);
}
function aleatorio(min,max){
  var resultado;
  resultado = Math.floor(Math.random() * (max - min + 1)) + min;
  return resultado;
}
function insertionSort(){
  var currentVal,j;
  for(var i = 1; i < array.length; i++){
    currentVal = array[i];
     j = i - 1;

     while ( j >= 0 && array[j] > currentVal){
       array[j+1] = array[j];
       j = j - 1;
     }
     array[j+1] = currentVal;
     console.log(array);
    }

INSERTION SORT en Javascript.

<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>Document</title>
</head>
<body>
	<script type="text/javascript">
		var array= [6,4,3,11,10];
		var longitud= array.length;
		document.write("arreglo desordenado<br><br>");
		for(x in array){
			document.write(`posicion ${x} valor: ${array[x]}<br>`);
		}

		function insertSort(arreglo,tamaño){
			for(i=1;i<tamaño;i++){
				var valorComparar= arreglo[i];
				j= i-1;
				while(j>=0 && arreglo[j]>valorComparar){
					arreglo[j+1]= arreglo[j];
					j--;
				}
				arreglo[j+1]= valorComparar;//recordar que si por ejemplo tenemos los valores
				//6,4 al hacer el cambio en el while j valdra -1 al salir de el, arreglo[j+1] es igual a -1+1=0 asi la posicion cero guardada el valor de 4 y ya en el while colocamos el valor de 6 en la posicion 1
			}
		}
		insertSort(array,longitud);
		document.write("<br>arreglo ordenado<br><br>");
		for(x in array){
			document.write(`posicion ${x} valor: ${array[x]}<br>`);
		}
	</script>
</body>
</html>```

Corregi un poco los espacios

#include <stdio.h>
#include <math.h>

/* Función de insertion Sort*/
void insertionSort(int arr[], int n) {
   int currentVal, j;
   for ( int i = 1; i < n; i++ ) {
       currentVal = arr[i]; //obtenemos el valor actual a comparar
       j = i - 1;

       /* mueve los elementos del arreglo arr[0..i-1],que son mayores que el valor de la posición actual del recorrido, a una posición adelante de su posición actual */
       while ( ( j >= 0 ) &&  ( arr[j] > currentVal) ) {
           arr[j + 1] = arr[j];
           j = j - 1;
       }
       arr[j + 1] = currentVal;
   }
}

// función auxiliar para imprimir un arrary de tamaño n
void printArray(int arr[], int n) {
   for ( int i = 0; i < n; i++ )
       printf("%d ", arr[i]);
   printf("\n");
}



/* Driver program to test insertion sort */
int main() {
    int arr[] = {6, 4, 3, 11, 10};
    int n = sizeof( arr ) / sizeof( arr[0] );

    insertionSort(arr, n);
    printArray(arr, n);

    return 0;
}

All right, I just need a hour to process and understand the code.

#include<stdio.h>
#include<math.h>

// Insertion sort function
void insertionSort(int arr[],int n)
{
    int i, current_value, j;
    for ( i = 0; i < n; i++)
    {
        current_value = arr[i]; /* Get the value to compare */
        j = i-1;
        while (j >= 0 && arr[j] > current_value) /* Here, we ask if the current_value is lower that the before */ 
        {
            arr[j+1]= arr[j]; /* Here we send the value before to next */
            j = j-1;    /* Here we send the comparator to after the current position, 
                        because the current position is ocuped by the value j+1 */
        }
        arr[j+1] = current_value;  /* When the cicle breaks even before we get in -values,
                                    we save the value in the correct line, that is + 1 
                                    the j, wich is the comparator */
    }
   
    
}

void print_arr(int arr[], int n)
    {
        int i;
        for ( i = 0; i < n ; i++)
        {
            printf("%d,", arr[i]);
        }
        printf("\n");
    }
int main(int argc, char const *argv[])
{
    int arr[] = {684,627,11,5,8,2666,623,154,309,85,0,-9};
    int n = sizeof(arr)/sizeof(arr[0]);

    insertionSort(arr,n);
    print_arr(arr,n);

    return 0;
}```

De nuevo, una explicacion bien pobre 👎.

En JS, dejo algunos comentarios que pueden ayudar a entender la implementación.
Me costo mucho entender el array[j + 1] = this.currentValue; después del ciclo while.

class InsertionSort {

  constructor() {
    this.currentValue;
  }

  sort = array => {

    const n = array.length;

    for (let i = 1; i < n; i++) {
      /* currentValue es la posición que va a iterar y comparar con las posiciones anteriores a el.
       currentValue es la posicion donde van a estar los valores menores y van a pasar a la izquierda del array
       porque estamos organizando de menor a mayor */
      this.currentValue = array[i];
      let j = i - 1;

      while (j >= 0 && array[j] > this.currentValue) {

        array[j + 1] = array[j];
        /*restamos a 'j' - 1 para que cada ciclo compare el currentValue con las posiciones anteriores hasta que la condición
        no se cumpla*/
        j = j - 1;
        // console.log(j + 1, j,  'j - in', this.currentValue);

      }
      // Este console.log ayuda a entender el algoritmo
      console.log(` j = ${j} | j + 1 = ${j + 1} current = ${this.currentValue}`);
      /* Cuando la condición del ciclo while no se cumple, 'j' queda en la posición donde el valor es menor al currentValue,
       entonces tenemos que poner el currenteValue a una posición siguiente a 'j' o sea 'j + 1', porque sería en siguiente
       número mayor, del orden 'menor a mayor', así se va organizando de menor a mayor*/

       /*En esta parte del código 'j + 1' define la posición del valor que estabamos comparando en el ciclo while que acabo de
       finalizar*/
      array[j + 1] = this.currentValue;


    }
  }
}

const arrayRandom = [];
for (let i = 0; i < 5; i++) {

  const numRandom = Math.floor(Math.random() * 500 );
  arrayRandom.push(numRandom);

}
console.log(arrayRandom, ' Before sort');

const insertion = new InsertionSort();
insertion.sort(arrayRandom)

console.log(arrayRandom, ' After sort');

Algo que aprendí de freddy en el curso de programación básica es que cuando tengas dudas , utiliza la consola para ver como avanza tu código.
Inserté algunos printf para que se entienda los movimientos y el funcionamiento del la acción después del while.
|
El while simplemente va corriendo los valores a la derecha y cuando no se cumple la condición de “j>=0” la declaracion “arr[j+1] = currentVal;” hace que el primer valor sea igual al currentVal definido al iniciar el ciclo for

#include <stdio.h> 
#include <math.h> 
  
/* Función de insertion Sort*/
void insertionSort(int arr[], int n) 
{ 
   int i, currentVal, j; 
   for (i = 1; i < n; i++) 
   { 
       printf("i: %d \n", i);
       currentVal= arr[i];
       printf("currentVal = %d \n", currentVal);
       j = i-1;
       printf("j: %d \n", j);
  
       /* mueve los elementos del arreglo arr[0..i-1],que son mayores que el valor de la posición actual del recorrido, a una posición adelante de su posición actual */
       while (j >= 0 && arr[j] > currentVal)
       {   
           printf("antes arr[%d] = %d \n", j+1, arr[j+1]);
           arr[j+1] = arr[j];
           printf("arr[%d] = %d \n",j , arr[j]);
           printf("ahora arr[%d] = %d \n", j+1, arr[j+1]);
           j = j-1;
           printf("j: %d \n", j);
       } 
       arr[j+1] = currentVal;
       printf("arr[%d] ahora es = %d \n \n", j+1, arr[j+1]);
       printArray(arr, n); 
   } 
} 
  
// función auxiliar para imprimir un arrary de tamaño n 
void printArray(int arr[], int n) 
{ 
   int i; 
   for (i=0; i < n; i++) 
       printf("%d ", arr[i]); 
   printf("\n \n"); 
} 
  
  
  
/* Driver program to test insertion sort */
int main() 
{ 
    int arr[] = {6, 4, 3, 11, 10}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    
    printf("El array sin ordenar: \n");
    printArray(arr, n);
    insertionSort(arr, n);

    printf("El array ordenado: \n");
    printArray(arr, n); 
  
    return 0; 
} 

Quedaria algo asi la consola:

El array sin ordenar: 
6 4 3 11 10

i: 1
currentVal = 4        
j: 0
antes arr[1] = 4      
arr[0] = 6
ahora arr[1] = 6      
j: -1
arr[0] ahora es = 4   

4 6 3 11 10

i: 2
currentVal = 3        
j: 1
antes arr[2] = 3      
arr[1] = 6
ahora arr[2] = 6      
j: 0
antes arr[1] = 6      
arr[0] = 4
ahora arr[1] = 4      
j: -1
arr[0] ahora es = 3   

3 4 6 11 10

i: 3
currentVal = 11       
j: 2
arr[3] ahora es = 11  

3 4 6 11 10

i: 4
currentVal = 10       
j: 3
antes arr[4] = 10
arr[3] = 11
ahora arr[4] = 11
j: 2
arr[3] ahora es = 10

3 4 6 10 11

El array ordenado:
3 4 6 10 11

java script

Insertion Sort in Python with details:

i 1
current_val: 4
j = i-1: 0
while j: 0
array[j + 1]: 6
j-=1: -1
array[j+1]: 4

i 2
current_val: 3
j = i-1: 1
while j: 1
array[j + 1]: 6
j-=1: 0
array[j+1]: 3

while j: 0
array[j + 1]: 4
j-=1: -1
array[j+1]: 3

i 3
current_val: 11
j = i-1: 2

i 4
current_val: 10
j = i-1: 3
while j: 3
array[j + 1]: 11
j-=1: 2
array[j+1]: 10

Sorted Array in Ascending Order:
[3, 4, 6, 10, 11]

ejemplo en Java:

public class InsertionSort {
    public int[] ordenar(int[] arr){

        for(int i = 0; i + 1 < arr.length; i++){
            for(int j = i + 1; j > 0; j--){
                if(arr[j] < arr[j - 1]){
                    int tmp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        for(int i : arr) {
            System.out.println("Ordenado: " + i);
        }
        return arr;
    }
}

Me parece que el orden de los cursos no es el adecuado. Primero debería ir el curso de Introducción al C, luego el de funciones en C y seguido a estos control de flujo en C y recién ahí deberían poner el curso de Estructura de datos y algoritmos, porque a la persona que no sabe programar se le va a complicar seguir el diseño de los algoritmos

“The sizeof operator gives the amount of storage, in bytes, required to store an object of the type of the operand. This operator allows you to avoid specifying machine-dependent data sizes in your programs.”

Font: https://docs.microsoft.com/en-us/cpp/c-language/sizeof-operator-c?view=msvc-170

Mi solución en JavaScript

function insertionSort(){
    for(let i = 1; i<inputs.length; i++){
        for(let j=i;j>=0;j-- ){
            if(inputs[j]<inputs[j-1]){
            let aux = inputs[j]
            inputs[j] = inputs[j-1]
            inputs[j-1] = aux
            }
        }
    }
}

Un pequeño aporte en Js

const InsertionSort = array =>{
    let long = array.length;
    let valorIndex, j;

    for(let i=1; i<long; i++){
        valorIndex = array[i];
        j=i;

        while(j>= 1 && array[j-1] > valorIndex){ 
            array[j] = array[j-1];
            j--;
        }
        array[j] = valorIndex;
    }
}

let ordenAsc = array =>{
    let arrOrdenado = [];

    console.log('En orden ascendente: ')
    for(let i=0; i<array.length; i++){
        arrOrdenado.push(array[i])
    }
    console.log(arrOrdenado)
}

let ordenDes = array =>{
    let arrOrdenado = [];
    console.log('En orden descendente:')

    for(let i=array.length-1; i>=0; i--){
        arrOrdenado.push(array[i])
    }
    console.log(arrOrdenado)
}

array = [10, 40, 1, 200, 4, 55, 2];

InsertionSort(array)
ordenAsc(array)
ordenDes(array)

Genial!

Compañer@s, me podrían por favor indicar como funciona el ciclo for?, de que manera se dispara ese ciclo para volver a dar toda la vuelta hasta que quede el arreglo ordenado?, haciendo la prueba de escritorio solo recorro una vez el arreglo, pero no se en que momento se empieza a repetir el ciclo for.

Muchas gracias por su ayuda,

Feliz noche.

Genial!!, el bloque while se usa para reubicar el arreglo y el for para recorrer todos los elementos del arreglo.

Hola Amig@s,

Me podrían indicar en que parte del programa se aplica la libreria math.h?, en el while?

Mil gracias

si, cuesta entender el algoritmo

void insertionSort3(int arr[], int n)
{
int i, currentVal;
for (i = 0; i < n-1; i++)
{
if(arr[i] > arr[i+1]){
currentVal = arr[i];
arr[i] = arr[i+1];
arr[i+1] = currentVal;
i = -1;
}
}
}

Creo que la anterior lógica también pertenece a insertion sort.

La verdad un poco complejo, no he podido entenderlo muy bien

Test Comment.

public void insertionSort(ArrayList<Integer> arrayList, int size) {

        int i;
        int currentValue;
        int j;

        for (i= 1; i<size; i++) {
            currentValue = arrayList.get(i); //Obtenemos el valor actual a comparar.
            j = i-1;

            /*
            * Mueve los elementos del arreglo arrayList[0..i-1], que son mayores que el
            * valor de la posición actual del recorrido, a una posición adelante de su
            * posición actual.
            * */
            while (j >= 0 && arrayList.get(j) > currentValue) {
                arrayList.set(j+1,arrayList.get(j));
                j = j - 1;
            }

            arrayList.set(j+1,currentValue);

        }

        printInsertionSort(arrayList,size);

    }

    public void printInsertionSort(ArrayList<Integer> arrayList, int size) {
        int i;

        System.out.print("[");
        for (i=0; i<size; i++) {
            System.out.print(arrayList.get(i) + ", ");
        }
        System.out.println("]");
    }

    public void mainInsertionSort() {
        /*Declaración de variables*/
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> arrayInsertion = new ArrayList();
        int tamanoArray;
        int datoArray;

        System.out.println("¿Cuántos elementos tendrá tu arreglo de datos?");
        tamanoArray = scanner.nextInt();

        for (int i=0; i<tamanoArray; i++) {
            System.out.print("Ingresa un número: ");
            System.out.println();
            arrayInsertion.add(datoArray = scanner.nextInt());
        }

        System.out.print("El array quedó de la siguiente manera: [");
        for (int i=0; i<tamanoArray; i++){
            System.out.print(arrayInsertion.get(i) + ", ");
        }

        System.out.print("]");
        System.out.println();
        System.out.println("El array ordenado queda de la siguiente manera:");
        insertionSort(arrayInsertion,tamanoArray);

    }

Mi implementación en Java

class Main {
  public static void main(String[] args) {
    int[] array = {10,5,8,-1,9,2,1};
    for(int i=0; i<array.length; i++)
      for(int j=i; j<array.length; j++)
        if(array[i]>array[j]){
          int temp = array[i];
          array[i] = array[j];
          array[j] = temp;
        }
    
    for(int x=0; x<array.length; x++)
      System.out.println(array[x]);
  }
}

La verdad este algoritmo es bastante complejo y fue un poco difícil de entender

Mi aporte.

function insertionSort(data, orderBy){
    let i = 0, j = 0;
    let order = (orderBy== "asc" || orderBy == "ASC") ? "A" : (orderBy == "desc" || orderBy == "DESC" ? "D" : "A") //Si no se especifica el ordenamiento, por default es Ascedente
    for(i = 1; i < data.length; i++){
        j = i;
        while( j > 0 && ( order == "A" ? (data[j] < data[j-1]) : ( (data[j] > data[j-1]) ) ) ){
            change(data,j,j-1);
            j--;
        }
    }

}

function change(data,starPosition,finalPosition){
    var tempValue = data[finalPosition];
    data[finalPosition] = data[starPosition];
    data[starPosition] = tempValue;
}

let vector = [4,3,0,-1,100,55];

insertionSort(vector,"desc")

Me costo entenderlo, pero se logró 💪. Les comparto mi código (use un for en vez de un while)

function insertionSort() {
  for (let i = 1; i < values.length; i++) {
    let tmp = values[i]
    let j = i-1
    console.log("---\nBefore: " + values + " i=" + i + " j=" + j);
    for (j; j >= 0 && values[j] > tmp; j--) {      
      values[j+1] = values[j]      
    }
    values[j+1] = tmp
    console.log("After: " + values + "\n---");
  }
}
// Main
values = [6,4,3,11,10]
console.log(values);
insertionSort()
console.log(values);

Este código espero que les ayude a quienes aún no entienden bien el funcionamiento del algoritmo, muestra cada cambio y el valor de los indices.

#include <stdio.h>

void swapNumbers(int * n1, int * n2){
    int temp = * n1;
    * n1 = * n2;
    * n2 = temp;
}

void insertionSort(int secuencia[], int n){
    for (int i = 1; i < n; i++) {
        for(int j = i-1; j >= 0; j--){
            if(secuencia[j+1]<secuencia[j]){
                swapNumbers(&secuencia[j], &secuencia[j+1]);
            }
        }
    }
}

void printSequence(int secuencia[], int n){
    for (int i = 0; i < n; i++){
        printf("[%d]: %d\n", i, secuencia[i]);
    }
}

int main(int argc, const char * argv[]){
    int secuencia[] = {10, 20, 8, 9, 4, 15, 80, 1, -35};
    int n = sizeof(secuencia)/sizeof(secuencia[0]);
    insertionSort(secuencia, n);    
    printSequence(secuencia, n);
    return 0;
}```

No entendí pero lo voy a practicar

Resumen: INSERTION SORT:
Es un algoritmo que ordena cada valor individualmente, de menor a mayor. Comienza comparando de a dos números hasta que queden ordenados de menor a mayor.

La practica hace al maestro, debemos seguir practicando, gracias por la clase 😃

Esto yo lo conocía como método burbuja, es el mismo o son diferentes?

Comparto dos enlaces que me han parecido muy útiles.

1. Una conversación sobre insertion sort y bubble sort: https://stackoverflow.com/questions/17270628/insertion-sort-vs-bubble-sort-algorithms
2. Una comparativa: https://www.geeksforgeeks.org/comparison-among-bubble-sort-selection-sort-and-insertion-sort/

Mi solución en python para el insert sort -> https://colab.research.google.com/drive/1H7WzH2AtZjKJbeoULSjKqjVeCaP8OdO3

despues de media tratando de entender y compilar lo logre

lo hice segun entendi como funcionaba el algoritmo

ok

Ok

#include <stdio.h> 
#include <math.h> 
  
/* Función de insertion Sort*/
void insertionSort(int arr[], int n) 
{ 
   int i, currentVal, j; 
   for (i = 1; i < n; i++) 
   { 
       currentVal= arr[i]; //obtenemos el valor actual a comparar
       j = i-1;
  
 
       while (j >= 0 && arr[j] > currentVal) 
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       } 
       arr[j+1] = currentVal; 
   } 
} 
  
// función auxiliar para imprimir un arrary de tamaño n 
void printArray(int arr[], int n) 
{ 
   int i; 
   for (i=0; i < n; i++) 
       printf("%d ", arr[i]); 
   printf("\n"); 
} 
  
  
  

int main() 
{ 
    int arr[] = {6, 4, 3, 11, 10}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    insertionSort(arr, n); 
    printArray(arr, n); 
  
    return 0; 
} ```

Codigo en Python

def insertion(arr):
    n = len(arr)
    for i in range(1,n):
        currentVal = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > currentVal:
            arr[j+1] = arr[j]
            j = j - 1
        arr[j+1] = currentVal

arr = [6,4,3,11,10]
insertion(arr)
print(arr)```

Con print para validar los valores

#include <stdio.h>
#include <math.h>

void insertionSort(int arr[], int n)
{
   int i, currentVal, j;
   for (i = 1; i < n; i++) //empieza del 2 valor
   {
       currentVal= arr[i]; //obtenemos el valor actual a comparar
       printf("\ncurrentVal = arr[%d]: %d\n",i,arr[i]);
       j = i-1;
       while (j >= 0 && arr[j] > currentVal)
       {
           printf("Entra al while\n");
           printf("arr[%d]: %d > currentVal: %d\n",j,arr[j],currentVal);
           printf("Como es mayor el valor inicial lo lleva al siguiente lugar\n");
           arr[j+1] = arr[j];
           printf("arr[%d]:%d\n",j,arr[j]);
           printf("arr[%d]:%d\n",j+1,arr[j+1]);
           j = j-1;
           printf("Disminuye j-1: %d\n",j);
       }
       arr[j+1] = currentVal;
       printf("Sale del while y arr[%d]: %d\n",j+1,arr[j+1]);
   }
}
void printArray(int arr[], int n)
{
   int i;
   for (i=0; i < n; i++)
       printf("%d ", arr[i]);
   printf("\n");
}

int main()
{
    int arr[] = {6, 4, 3, 11, 10};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr, n);
    printArray(arr, n);
    return 0;
}

#include <iostream>

using namespace std;

//------------------------------------------------------------------
void insertionSort(int values[], int n)
{
    int i, previous, value, index;
    for ( i = 0; i < n - 1; i++ )
    {
        value = values[i];
        previous = values[i-1];
        index = i;
        while (index != -1)
        {
            if ( previous > value)
            {
                values[index-1] = value;
                // cout << value;
                values[index] = previous;
                index--;
                previous = values[index-1];
                value = values[index];
            } else {
                index = -1;
            }
        }
    }
}

//------------------------------------------------------------------
void printDatos(int values[], int n)
{
    int i;
    for ( i = 0; i < n - 1; i++ )
    {
        cout << values[i] << " ";
    }
    cout << "Hola";
}

//------------------------------------------------------------------
int main()
{
    int values[10] = {1992,100,2,5,4,60,70,14,15}, n;
    n = sizeof(values)/sizeof(values[0]);
    insertionSort(values, n);
    printDatos(values, n);
    return 0;
}

Entendido

#include <stdio.h>

void insertionSort(int vector[], int n)
{
int currentVal, j;
for(int i = 1; i < n; i++)
{
currentVal = vector[i];

    j = i - 1;
    
    while( j >= 0 && vector[j] > currentVal)
    {
        vector[j + 1] = vector[j];
        j = j - 1;
    }
    vector[j + 1] = currentVal;
}

}

int imprimir(int v[], int n)
{
for(int i = 0; i < n; i++)
printf("%d, “, v[i]);
printf(”\nFin del ordenamiento");
}

main(int argc, char const *argv[])
{
int vec[] = {6, 7, 10, 8, 5, 1, 3, 2, 9, 4};
int n = sizeof(vec) / sizeof(vec[0]);

insertionSort(vec, n);
imprimir(vec, n);

return 0;

}

uff, este me costo mucho más

Mi solución en Python tiene en cuenta una lista de tamaño dinámico

import random

def insertion(ulist):
    n = len(ulist)
    for i in range(1,n):
        currentVal = ulist[i]
        j = i - 1
        while j >= 0 and ulist[j] > currentVal:
            ulist[j+1] = ulist[j]
            j = j - 1
        ulist[j+1] = currentVal
    return ulist

print("Lista Desordenada")

unordered = list(range(10)) #Se escoge el tamaño del listado desordenado.
random.shuffle(unordered)
print(unordered)

ordered=insertion(unordered)
print(ordered)```

Mi codigo en JS

//We create the array
var entry_vector = [4, 1992, 0, 5, -1, 60, 70, 14, 15]
//Create a var n that has the size of the array
var n = entry_vector.length

//We create a function to make an Insertion Sort
function insertionSort(value, size){
    /*This first for is for the whole cycle, this initiate at 1 to compare
    with the previous value in the array */
    for (let i = 1; i < size; i++) {
        let valueCom = value[i];

        //var j is equal to actual position - 1
        let j = i-1;

        /*In this While if array[position-1] that is equal to array[j]
        is mayor than array[actualposition] then run the code*/
        while (j>=0 && value[j]>valueCom) {
            /* array */
            value[j+1] = value[j];
            j--
        }
        //After the while we assign the array[position+1] to the value to Compare
        value[j+1]=valueCom;
    }
}

//This main function just run the functions
function main(){
    console.log(entry_vector);
    insertionSort(entry_vector,n);
    console.log(entry_vector)
    console.log("Order has ended")
}

main();

Ya lo comprendi al fin!!

Genial!!! gracias 😃

    public static void main(String[] args) {

  	int arrayInsertion[] = {8,4,1,5,3,6,5,9,2};
   	insertionSort(arrayInsertion);
    }
    public static void insertionSort(int arrayInsertion[]){

        for (int i = 1; i < arrayInsertion.length ; i++) {
            /*Toma la posición 1 del array y la asigna a la variable
            * current*/
            int current = arrayInsertion[i];
            // En una primera iteración j = i-1 = 1-1 = 0            
            int j = i-1; 
            /* (Ejemplo, primera iteración)
            * En el bucle while, j=0 y arrayInsertion será mayor a la variable current
            * arrayInsertion[0]= 8
            * current = arrayInsertion[i] = arrayInsertion[1] = arrayInsertion [4]
            * se cumple la condición y entra a operar
            * arrayInsertion[0+1]=arrayInsertion[0] , es decir, estamos asignando lo que hay en la posición 0
            * a la posición 1 (arrayInsertion[1]=8)
            * Disminuimos el valor de J, con el fin de asignar el valor menor a la posición 0. Fin del bucle
            * 
            * arrayInsertion [j+1] = current = arrayInsertion[-1+1]=arrayInsertion[1]
            * Lo que hacemos en esta línea es asignar el valor actual a la posición 0 del array.
            * 
            * y así continua para las demás iteraciones...
            * */
            
            while(j>=0 && arrayInsertion[j] > current){
                arrayInsertion[j+1] = arrayInsertion[j];
                j=j-1;
            }
            arrayInsertion[j+1] = current;
        }

        for (int i = 0; i < arrayInsertion.length ; i++) {
            System.out.println("El array ordenado es: ");
            System.out.print(arrayInsertion[i]+ " ");
        }

    }```

Perfecto, queda más clara la explicación del algoritmo de ordenamiento Insert Sort

Muy ingenioso el ciclo While

Más eficiente que el ordenamiento burbuja.

Me costó un poquito seguirle el flujo a la función insertionSort . Pero cuando la entendí me gusto mucho el ingenio de ese ciclo While 😄

no me funciono a la primera ya que me equivoque copiando y no aparecia nada

¿Cuál es la diferencia entre bubble sort e insertion sort?
A como entiendo el algoritmo practicamente se hace lo mismo

Insertion Sort en Python!

def insertionSort(list_):

  for i in range(1,len(list_)):
    currentValue = list_[i]
    j = i - 1
    while (j >= 0) and (currentValue < list_[j]):
      list_[j+1] = list_[j]
      j -= 1
    list_[j+1] = currentValue
  return list_

if __name__ == '__main__':
  messy_list = [5,9,2,6,1,3,7,8]
  print(messy_list)
  ordered_list = insertionSort(messy_list)
  print(ordered_list)

Python

import random

def ordenar(num):
    lista = [random.randint(0, 100) for i in range(num)]
    print(lista)

    for i in range(1, len(lista)):
        k = 1
        n = False
        for j in range(i - 1, -1, -1):
            if lista[i] < lista[j]:
                k = j
                n = True
                continue
            else:
                break
        if n:
            lista.insert(k, lista[i])
            del lista[i + 1]
    print(lista)


if __name__ == '__main__':
    num = int(input('Cuantos numeros necesitas: '))
    ordenar(num)

¿Qué no es igual a bubblesort?

Interesante implementación.

#include <stdio.h>
#include <math.h>

// Función de insertion Sort
void insertionSort(int arr[], int n) {
    int i, currentVal, j;
    for (i = 1; i < n; i++) {
        currentVal = arr[i]; //obtenemos el valor actual a comparar
        j = i - 1;
       // mueve los elementos del arreglo arr[0..i-1],que son mayores que el valor de la posición actual del recorrido, a una posición adelante de su posición actual
        while (j >= 0 && arr[j] > currentVal) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j+1] = currentVal;
    }
}

// función auxiliar para imprimir un arrary de tamaño n
int printArr(int arrIn[], int n) {
    for(int i = 0; i < n; i++){
        if(i == n - 1) {
            printf("%d", arrIn[i]);
        } else {
            printf("%d, ", arrIn[i]);
        }
    }
    printf("\nFin del ordenamiento\n");
}

// Driver program to test insertion sort
int main() {
    int arr[] = {6, 4, 3, 11, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printArr(arr, n);
    return 0;
}

Lo hice un poco distinto xD

#include <stdio.h>

//Introducir elementos
void getElements(int cant, int array[]){
	
	int i;
	
	for(i=0;i<cant;i++){
		
		printf("Introduzca el elemento %d \n", i+1);
		scanf("%d", &array[i]);
		printf("\n");
	}
	
}

//Imprimir elementos
void showElements(int cant, int array[]){
	
	int i;
	
	for(i=0;i<cant;i++){
		printf("%d, ", array[i]);
	}
	
	printf("\n");
}


//Ordenamiento de los elementos
void orderElements(int cant, int array[]){
	
	int i, pos, aux;
	
	for(i=0;i<cant;i++){
		
		pos = i;
		aux = array[i];		
		
		while((pos>0) && (array[pos-1] > aux)){
			array[pos] = array[pos-1];
			pos--;
		}
		
		array[pos] = aux;
	}
}


//Funcion principal MAIN

int main(){
	
	int n;
	printf("Ingrese el numero de elmentos que desea introducir \n");
	scanf("%d", &n);
	
	int myArray[n];
	
	getElements(n, myArray);
	
	printf("Elementos desordenados \n");
	
	showElements(n, myArray);
	
	orderElements(n, myArray);
	
	printf("Elementos Ordenados \n");
	
	showElements(n, myArray);
	
	
	return 0;
}