El algoritmo de ordenamiento por inserción es un algoritmo de facil aplicación que permite el ordenamiento de una lista.
Su funcionamiento consiste en el recorrido por la lista seleccionando en cada iteración un valor como clave y compararlo con el resto insertándolo en el lugar correspondiente.
Estabilidad: Estable
Método: Inserción
Comparativo: Si
Uso de memoria: 1
Complejidad computacional:
Mejor caso:
Caso promedio:
Peor caso:
Ordenamiento por inserción
Comenzamos con una lista de elementos no ordenados
Se selecciona el segundo valor como clave y se lo compara con los valores ubicados a su izquierda y se inserta en el lugar correspondiente
Se selecciona el siguiente número como clave y se repite el proceso para todos los valores anteriores
Se selecciona la siguiente clave
Finalmente se selecciona la última clave
Al finalizar el algoritmo tenemos como resultado la lista ordenado
Código en C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<stdio.h> #define N 5 void mostrarLista(int*); int main(int argc, char** argv){ int arreglo[N]={5,2,4,1,3}; int i,key,j; //Recorrer el arreglo for (i = 1; i < N; i++){ key = *(arreglo+i); j = i-1; //Comparar el valor selecionado con todos los valores anteriores while (j >= 0 && *(arreglo+j) > key){ //Insertar el valor donde corresponda *(arreglo+j+1) = *(arreglo+j); j = j-1; } *(arreglo+j+1) = key; mostrarLista(arreglo); } mostrarLista(arreglo); return 0; } //Función para mostrar estado de la lista void mostrarLista(int *lista){ int i; for (i=0; i< N; i++){ printf("%d ",*(lista+i)); } printf("\n");; } |
Código en PHP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
<?php error_reporting(E_ALL); ini_set('display_errors', 1); $arreglo[0]=5; $arreglo[1]=2; $arreglo[2]=4; $arreglo[3]=1; $arreglo[4]=3; $n=count($arreglo); //Recorrer el arreglo for ($i = 1; $i < $n; $i++) { $key = $arreglo[$i]; $j = $i-1; //Comparar el valor selecionado con todos los valores anteriores while ($j >= 0 && $arreglo[$j] > $key) { //Insertar el valor donde corresponda $arreglo[$j+1] = $arreglo[$j]; $j = $j-1; } $arreglo[$j+1] = $key; mostrarLista($arreglo, $n); } mostrarLista($arreglo, $n); //Función para mostrar estado de la lista function mostrarLista($lista, $lon) { for ($i=0; $i< $lon; $i++) { echo $lista[$i]." "; } echo "<br />"; } |
Espero que les sea de utilidad!