Algoritmo de Ordenamiento por Inserción.
El ordenamiento por insercion es una algoritmo de clasificacion que coloca cada elemento en un lugar adecuado segun cada paso y funciona de la misma manera que cuando jugamos cartas.
Este algoritmo es usado cuando:
*El arreglo tiene un pequeño numero de elementos.
*Hay pocos elelemtos a ser ordenados a la izquierda del elemento.
Algoritmo:
insertionSort(array)
for step = 1 to n
key <- array[step]
j <- step–1
while key > array[j] and j > = 0
array[j+1] <- array[j]
j <- j–1
end while
array[j+1] <- key
end for
end insertionSort
C++
#include <iostream>
using namespace std;
void printArray(int array[], int size){
for(int i=0; i < size; i++){
cout<<array[i]<<" ";
}
cout<<endl;
}
void insertionSort(int array[], int size){
for(int step=1; step<size; step++){
int key = array[step];
int j=step-1;
while(key<array[j] && j>=0){
// For descending order, change key<array[j] to key>array[j].
array[j+1] = array[j];
--j;
}
array[j+1]=key;
}
}
int main(){
int data[] = {9, 5, 1, 4, 3};
int size = sizeof(data)/sizeof(data[0]);
insertionSort(data, size);
cout<<"Sorted array in ascending order:\n";
printArray(data, size);
}