Bienvenido al Curso

1

Introducci贸n al curso b谩sico de algoritmos y estructuras de datos

Introducci贸n a los algoritmos

2

驴Qu茅 entiende una computadora?

3

Lenguajes de programaci贸n

4

Estructuras de datos

5

驴Qu茅 es un algoritmo?

6

Metodolog铆a para la construcci贸n de un algoritmo

7

Variables y tipos de datos

8

User defined data types

9

Instalando Ubuntu Bash en Windows

10

Creando nuestro user defined data type

11

Abstract Data Types b谩sicos: Lists, Stacks, Queues

12

Explicaci贸n gr谩fica Data Types b谩sicos

13

Glosario de funciones para Abstract Data Types

14

Clases y objetos

15

Creando tu primera Queue: Arrays

16

Creando tu primera Queue: implementaci贸n.

17

Creando tu primera Queue: implementar la funci贸n enQueue

18

Creando tu primera Queue: implementar la funci贸n deQueue

19

Creando tu primera Queue: main code

Algoritmos de ordenamiento

20

Algoritmos de ordenamiento

21

Bubble sort

22

Bubble sort: implementaci贸n

23

Bubble sort: main code

24

Insertion sort

25

Desaf铆o: implementa un algoritmo de ordenamiento

Recursividad

26

Recursividad

27

La funci贸n Factorial, calculando el factorial recursivamente

28

Manejo de cadenas de caracteres

29

Arte: Generando arte recursivo

Divide and conquer y programaci贸n din谩mica

30

Divide and Conquer (divide y vencer谩s)

31

Qu茅 es la programaci贸n din谩mica (divide y vencer谩s v2.0)

32

MergeSort

33

Desaf铆o: Buscar el algortimo m谩s r谩pido de sort

34

Implementando QuickSort con Python

35

Implementando QuickSort con Python: main code

Algoritmos 'Greedy'

36

Qu茅 son los Greedy Algorithm

37

Ejercicio de programaci贸n greedy

38

Ejercio de programaci贸n greedy: main code

Grafos y 谩rboles

39

Grafos y sus aplicaciones

40

脕rboles

驴C贸mo comparar Algoritmos?

41

C贸mo comparar algoritmos y ritmo de crecimiento

驴Qu茅 sigue?

42

Cierre del curso y siguientes pasos

Insertion sort

24/42

Lectura

Insertion Sort es un algoritmo simple que ordena individualmente cada valor, como lo har铆as al ordenar un set de cartas del juego UNO en tu mano.

...

Reg铆strate o inicia sesi贸n para leer el resto del contenido.

Aportes 95

Preguntas 5

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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 鈥渏>=0鈥 la declaracion 鈥渁rr[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

鈥淭he 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/

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