Algoritmo de ordenamiento

Algoritmo de ordenamiento por selección 

Consiste en encontrar el menor de todos los elementos del arreglo o vector e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenarlo todo. Su implementación requiere O(n2) comparaciones e intercambios para ordenar una secuencia de elementos.

Descripción

Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación de intercambiar los elementos sería más costosa en este caso. Su funcionamiento se puede definir de forma general como:

• Buscar el mínimo elemento entre una posición i y el final de la lista
• Intercambiar el mínimo con el elemento de la posición i

Así, se puede escribir el siguiente pseudocódigo para ordenar una lista de n elementos indexados desde el 1:

para i=1 hasta n-1;

   minimo = i;
   para j=i+1 hasta n
       si lista[j] < lista[minimo] entonces
           minimo = j 
       fin si
   fin para
   intercambiar(lista[i], lista[minimo])

fin para

Algoritmo de ordenamiento por inserción 

Este algoritmo también es bastante sencillo. ¿Has jugado cartas?. ¿Cómo las vas ordenando cuando las recibes? Yo lo hago de esta manera: tomo la primera y la coloco en mi mano. Luego tomo la segunda y la comparo con la que tengo: si es mayor, la pongo a la derecha, y si es menor a la izquierda (también me fijo en el color, pero omitiré esa parte para concentrarme en la idea principal). Después tomo la tercera y la comparo con las que tengo en la mano, desplazándola hasta que quede en su posición final. Continúo haciendo esto, insertando cada carta en la posición que le corresponde, hasta que las tengo todas en orden. ¿Lo haces así tu también? Bueno, pues si es así entonces comprenderás fácilmente este algoritmo, porque es el mismo concepto.Para simular esto en un programa necesitamos tener en cuenta algo: no podemos desplazar los elementos así como así o se perderá un elemento. Lo que hacemos es guardar una copia del elemento actual (que sería como la carta que tomamos) y desplazar todos los elementos mayores hacia la derecha. Luego copiamos el elemento guardado en la posición del último elemento que se desplazó.

 pseudocodigo en C++

  for (i=1; i<TAM; i++)

   temp= lista[i]
       j=i-1 ;
   while ((lista[j]> temp) && (j>0=0))
          lista[j+1]=lista[j];
       j--;
   lista[j+1]=temp;
   







pseudocodigo en C++

#include <iostream>
#include <math.h>
#include<conio.h>
#include<stdio.h>


using namespace std;

int num[100000],v[100000],n;

void insercion()
{
 int tem;
 for (int q=1;q<n;q++)
 {
 tem=num[q];
 for (int j=q;j>0 && tem<num[j-1];j--)
 {
   num[j]=num[j-1];
   num[j-1]=tem;
  }
 }
} 
void imprimir()
{
  for (int h=0;h<n;h++)
 {
  cout<<("\t%d",num[h]);
 }
}


void num_ordenados()
{
 int valor_temporal;
 for (int q=0;q<n-1;q++)//declaramos dos ciclos para poder ir comparando 0-1,1-2,2-3,...hasta n.
 {
  for (int w=q+1;w<n;w++)
  {
   if (v[w]<v[q])
   {
    valor_temporal=v[w];//se asigna el valor encontrado*/
    v[w]=v[q];//ahora el valor de v[q] toma el de v[w] para poder compararlo de nuevo con el siguiente numero*/
    v[q]=valor_temporal;
   }
  }
 }
}
void orden()//para poder imprimirlos en orden*/
{
 for (int t=0;t<n;t++)
 {
 cout<<("\t%d\n",v[t]);
 }
}


int main ()
{
   int opcion;
 do
 {      //INICIO DEL DO - WHILE
  cout<<"********* Metodos de ordenamiento **********\n\n"; 
  cout<<" 1) Ordenamiento de burbuja  \n";
  cout<<" 2) Ordenamiento de insercion \n";
  cout<<" 3) Ordenamiento de seleccion  \n";
  cout<<"       DIGITE <0> PARA SALIR \n\n";
  cout<<"*************************************\n\n";
  cout<<"   ELIJA UNA OPCION : "; cin>>opcion;
    //2)ASIGNACION
    switch (opcion)
    { //INICIO DEL CASO 1
    case 1: 
     {// CONTENIDO 1 (INICO)
       cout<<"*******  Ordenamiento de burbuja ******\n\n";
    
       int temp;
 int arreglo[10]={8,4,2,9,6,3,5,7,1,10};
 cout<<"8,4,2,9,6,3,5,7,1,10\n";
 
 for (int b=0;b<11;b++) //*esto sirve para que el arreglo pueda compararce las veces nesesarias y asi poder imprimir los numeros ordenados ejemplo de esto aqui
 { 
   for (int i=0;i<8;i++)
   {
   if (arreglo[i+1]<arreglo[i])
  {
   temp=arreglo[i];
   arreglo[i]=arreglo[i+1];
   arreglo[i+1]=temp;
   
  }
   }
    }
    printf("\nordenamiento por el emtodo de burbuja (bubblesort)\n \n");
    for (int x=0;x<9;x++)
 {
    cout<<("%d\n\n",arreglo[x]);cout<<"\n";
 }
       cout<<"***********************\n\n";
    } //FIN DEL CASO 1
     break;      
    case 2: 
     {//INICIO DEL CASO 2
    
       cout<<"\n******* Ordenamiento de  insercion ***************\n\n";

{
 cout<<("cant. de numeros: ");
 scanf("%d",&n);
 for (int y=0;y<n;y++)
 {
  printf("valor %d: ",y+1);
  scanf("%d",&num[y]);
 }
 printf("\n orden ingresados:\n\n");
 imprimir();
 insercion();
 printf("\n\n metodo de insercion:\n\n");
 imprimir();cout<<"\n";

}

       cout<<"*********************************\n\n";
     } //FIN DEL CASO 2
    break;
    case 3: 
     {//INICIO DEL CASO 3
       cout<<"******* Ordenamiento de seleccion ***************\n\n";
       {
 printf("cant. de numeros: ");
 scanf("%d",&n);
 for (int i=0; i<=n-1;i++)
 {
  printf("\n ingreso  numero %d: ",i+1);
  scanf("%d",&v[i]);
 }
 printf("\n orden   en el que fueron ingresado:\n\n");
 orden(); //lamamos nuetra operacion para imprimirlo con el orden en el que fueron ingresados*/
 num_ordenados();   //ego ya con el metoo de seleccion*/
 printf("\n");
 printf("\n  metodo de seleccion:\n\n");
 orden();cout<<"\n";
 
 
}
   
       cout<<"*********************************\n\n";
     } //FIN DEL CASO 3
    break;
     
   }// FIN DE SWITCH  
 }while (opcion !=0); // FIN DEL DO - WHILE

  cout<<endl;cout<<"\n";  
    
    
    system("pause");
    return 0;
}