/*
-Victor de la Rocha
-vyk2rr@gmail.com
-www.algoritmia.info
-Jueves 10/AGO/05
-Programa 2, Practica 1
-Insertion Sort (Ordenamiento por insercion)
-Program that orders an adjustment with the arrangement algorithm 'insertion sort'
-Programa que ordena un arreglo con el algoritmo de ordenacion 'ordenamiento por insercion'
*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
int fillrand(int A[],int N,int R){
         int c;
         for(c=1;c<=N;c++){
                 A[c]=rand()%R;
             }     
         return 1;
     }
 
int insertionsort(int A[],int N){
         int i,k,AUX;
         for(i=2;i<=N;i++){
                 AUX=A[i];
                 k=i-1;
                 while(k==1&&AUX<A[k]){
                         A[k+1]=A[k];
                         k=k-1;
                     }
                 A[k+1]=AUX;
             }
         return 1;
     }
 
int salida(int A[],int N){
         int c;
         for(c=1;c<=N;c++){
                 printf("%d, ",A[c]);
             }
         return 1;
     }
 
void main(){
         int A[10];
         randomize();
         clrscr();
         fillrand(A,10,100);
         printf("INSERTION SORTn");
         printf("Datos a ordenar: n");
         salida(A,10);
         printf("nnDatos ordenados: n");
         insertionsort(A,10);
         salida(A,10);
         getch();
     }
 
/*
INSERCION(A,N)
{El algoritmo ordena los elementos del arreglo utilizando el método de inserción directa. A es un arreglo de N elementos}
{I, AUX y K son variables de tipo entero}
1. Repetir con I desde 2 hasta N
        Hacer AUX <--  A[I] y K <--  I – 1
        1.1 Repetir mientas K =  1) y (AUX < A[K])
                Hacer A[K+1] <--  A[K] y K <--  K - 1
                1.2 {Fin del ciclo del paso 1.1}
                Hacer A[K+1] <--  AUX
2. {Fin del ciclo del paso 1}
*/