Eva P-7

Algoritmos de ordenamiento

 Introducción.

^

El ordenamiento es una labor común que realizamos continuamente. ¿Pero te has preguntado qué es ordenar? ¿No? Es que es algo tan corriente en nuestras vidas que no nos detenemos a pensar en ello. Ordenar es simplemente colocar información de una manera especial basándonos en un criterio de ordenamiento.

En la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás. Aquí voy a mostrarte algunas de las más comunes, tratando de hacerlo de una manera sencilla y comprensible.

TIPOS DE ORDENAMIENTOS :

1 Ordenamiento Burbuja (Bubblesort)

^

1. Descripción.

^

Este es el algoritmo más sencillo probablemente. Ideal para empezar. Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian. ¿Sencillo no?

APLICACION  :

2. Pseudocódigo en C.

^

Tabla de variables

Nombre	Tipo	Uso
lista	Cualquiera	Lista a ordenar
TAM	Constante entera	Tamaño de la lista
i	Entero	Contador
j	Entero	Contador
temp	El mismo que los elementos de la lista	Para realizar los intercambios

 
    1. for (i=1; i<TAM; i++)
    2.      for j=0 ; j<TAM - 1; j++)
    3.           if (lista[j] > lista[j+1])
    4.                temp = lista[j];
    5.                lista[j] = lista[j+1];
    6.                lista[j+1] = temp;

2 Ordenamiento por Inserción

^



1. Descripció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ó.



2. Pseudocódigo en C.

^
Tabla de variables

Nombre
Tipo
Uso

lista
Cualquiera
Lista a ordenar
TAM
Constante Entera
Tamaño de la lista
i
Entero
Contador
j
Entero
Contador
temp
El mismo que los elementos de la lista
Para realizar los intercambios

 
    1. for (i=1; i<TAM; i++)
    2.      temp = lista[i];
    3.      j = i - 1;
    4.      while ( (lista[j] > temp) && (j >= 0) )
    5.           lista[j+1] = lista[j];
    6.           j--;
    7.      lista[j+1] = temp;
 

APLICACION :

#include<conio.h>

#include<stdio.h>

int num[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++)

 {

  printf("\t%d",num[h]);

 }

}

main()

{

 printf("cant. de numeros: ");

 scanf("%d",&n);

 for (int y=0;y<n;y++)

 {

  printf("valor %d: ",y+1);

  scanf("%d",&num[y]);

 }

 printf("\norden ingresados:\n\n");

 imprimir();

 insercion();

 printf("\n\nmetodo de insercion:\n\n");

 imprimir();

 getch();

}


3 Ordenamiento Rápido (Quicksort)

^



1. Descripción.

^

Esta es probablemente la técnica más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). El algoritmo fundamental es el siguiente:

Eliges un elemento de la lista. Puede ser cualquiera (en Optimizando veremos una forma más efectiva). Lo llamaremos elemento de división.
Buscas la posición que le corresponde en la lista ordenada (explicado más abajo).
Acomodas los elementos de la lista a cada lado del elemento de división, de manera que a un lado queden todos los menores que él y al otro los mayores (explicado más abajo también). En este momento el elemento de división separa la lista en dos sublistas (de ahí su nombre).
Realizas esto de forma recursiva para cada sublista mientras éstas tengan un largo mayor que 1. Una vez terminado este proceso todos los elementos estarán ordenados.


Una idea preliminar para ubicar el elemento de división en su posición final sería contar la cantidad de elementos menores y colocarlo un lugar más arriba. Pero luego habría que mover todos estos elementos a la izquierda del elemento, para que se cumpla la condición y pueda aplicarse la recursividad. Reflexionando un poco más se obtiene un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos contador por la izquierda, y j, al que llamaremos contador por la derecha. El algoritmo es éste:

Recorres la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento).
Cuando lista[i] sea mayor que el elemento de división y lista[j] sea menor los intercambias.
Repites esto hasta que se crucen los índices.
El punto en que se cruzan los índices es la posición adecuada para colocar el elemento de división, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).


Al finalizar este procedimiento el elemento de división queda en una posición en que todos los elementos a su izquierda son menores que él, y los que están a su derecha son mayores.



2. Pseudocódigo en C.

^
Tabla de variables

Nombre
Tipo
Uso

lista
Cualquiera
Lista a ordenar
inf
Entero
Elemento inferior de la lista
sup
Entero
Elemento superior de la lista
elem_div
El mismo que los elementos de la lista
El elemento divisor
temp
El mismo que los elementos de la lista
Para realizar los intercambios
i
Entero
Contador por la izquierda
j
Entero
Contador por la derecha
cont
Entero
El ciclo continua mientras cont tenga el valor 1

 
 Nombre Procedimiento: OrdRap
 Parámetros: 
    lista a ordenar (lista) 
    índice inferior (inf) 
    índice superior (sup)
                   
    // Inicialización de variables
    1. elem_div = lista[sup];
    2. i = inf - 1;
    3. j = sup;
    4. cont = 1;
    
    // Verificamos que no se crucen los límites
    5. if (inf >= sup)
    6.      retornar;
    
    //  Clasificamos la sublista
    7. while (cont)
    8.      while (lista[++i] < elem_div);
    9.      while (lista[--j] > elem_div);
   10.      if (i < j)
   11.           temp = lista[i];
   12.           lista[i] = lista[j];
   13.           lista[j] = temp;
   14.      else
   15.           cont = 0;
   
   // Copiamos el elemento de división
   // en su posición final
   16. temp = lista[i];
   17. lista[i] = lista[sup];
   18. lista[sup] = temp;
   
   // Aplicamos el procedimiento
   // recursivamente a cada sublista
   19. OrdRap (lista, inf, i - 1);
   20. OrdRap (lista, i + 1, sup);
 

APLICACION:

#include "stdafx.h" 
#include "iostream" 
using namespace System; 
using namespace std; 

void quicksort_iteractivo(int A[],int ini,int fin) 
{ 
int pos,aux,band;///definicon de variables 
int i=ini; 
int j =fin; 
pos=ini; 
band=1; 
while (band==1) 
{ 
band=0; 
while((A[pos]<=A[j])&&(pos!=j)) 
{ 
j--; 
} 
if (pos!=j)///posición en j 

{ 
aux=A[pos]; 
A[pos]=A[j]; 
A[j]=aux; 
pos=j; 


for(int k=0;k<8;k++)cout<<A[k]<<" "; 
cout<<endl; 
cout<<"pos es igual a: "<<pos<<endl; 


while ((A[pos]>=A[i])&&(pos!=i)) 
{ 
i++; 
} 
if(pos!=i)/// posición en i 
{ 
band=1; 
aux=A[pos]; 
A[pos]=A[i]; 
A[i]=aux; 
pos=i; 


for(int k=0;k<8;k++)cout<<A[k]<<" "; 
cout<<endl; 
cout<<"pos es igual a: "<<pos<<endl; 

} 
} 
} 
if ((pos-1)>ini) 
{ ///condición 
quicksort_iteractivo(A,ini,pos-1); 
} 
if (fin>(pos+1)) 
{ 
quicksort_iteractivo(A,pos+1,fin); 
} 
} 

void main()///programa principal 
{ 
int A[100],n,c; 
cout<<"entre numero de elementos del vector"<<endl; 
cin>>n; 
for(c=0;c<n;c++) 
{ 
cout<<"entre elemento A["<<c<<"]= "<<endl; 
cin>>A[c]; 
} 
quicksort_iteractivo(A,0,n-1); 
cout<<"el vector ordenado es: "<<endl; 
for(c=0;c<n;c++) 
{ 
cout<<A[c]<<" "; 
} 
cout<<endl; 
}