Metodos de ordenamiento (INSERCIÓN)

METODO DE INSERCIÓN

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

PROGRAMA QUE CAPTURA 5 NOMBRES Y EL PROMEDIO DE 3 CALIFICACIONES Y LOS ORDENA DE MANERA ASCENDENTE Y DESCENDENTE CON EL METODO DE LA INSERCIÓN.

#include<conio.h>
#include<iostream.h>
#include<string.h>

void main()
{
clrscr();
char nombre[5][10];
int cal[5][3];
int suma;
float prom[5];
int i,j,k;
int aux;
char nombreaux[10];

   for(i=0;i<5;i++){
      suma=0;
     cout<<"Introduze el nombre:"<<endl;
       cin>>nombre[i];
   
   for(j=0;j<3;j++){
    
         cout<<"calificacion"<<endl;
              cin>>cal[i][j];
       
       suma=suma+cal[i][j];
       }
       prom[i]=suma/3;
}

for(i=1;i<5;i++) //metodo de inserción
{
 
  aux=prom[i];
  strcpy(nombreaux,nombre[i]);
  for(j=i-1;j>=0;j--)
  {                  
    if(aux>prom[j]) 
    {
      prom[j+1]=aux;
strcpy(nombre[j+1],nombreaux);

      break;         
    }
    else             
      prom[j+1]=prom[j];
strcpy(nombre[j+1],nombre[j]);
  }
  if(j==-1)    
    prom[0]=aux;
strcpy(nombre[0],nombreaux);
}


cout << "Las promedios ordenados de manera descendente son: \n"<<endl;
  for(i=4;i>=0;i--){
    cout<<nombre[i]<<" : "<<prom[i]<<endl;
}
getch();
}