Concepto

Uno de los procedimientos más comunes y útiles en el procesamiento de datos, es la ordenación de los mismos. Se considera ordenar al proceso de reorganizar un conjunto dado de objetos en una secuencia determinada (patrón de arreglo). El objetivo de este proceso generalmente es facilitar la búsqueda de uno o más elementos pertenecientes a un conjunto.

Como ejemplos de conjunto de datos ordenados tenemos:

Meses del año (ordenados de 1 al 12).
Listado de estudiantes (ordenados alfabéticamente).
Guías Telefónicas (ordenadas por País/por región/por sector/por orden alfabético)

La ordenación, tanto numérica como alfanumérica, sigue las mismas reglas que empleamos nosotros en la vida normal. Esto es, un dato numérico es mayor que otro cuando su valor es más grande, y una cadena de caracteres es mayor que otra cuando esta después por orden alfabético.

Los métodos de ordenación, pueden agruparse en dos grandes grupos:

Los internos: Es cuando los datos están disponibles en un área de la memoria principal, como cuando se leen un conjunto de datos desde el teclado.
Los externos: Los datos están guardados en un medio externo, como puede ser un fichero, una base de datos, etc. En donde los datos están alojados en el disco duro u otro medio físico.

En este sección explicaremos solo tres modos de ordenamiento, los mas usados como son:

Algoritmo de Ordenamiento Burbuja (Buble Sort)
Algoritmo de Ordenamiento Insercion
Algoritmo de Ordenamiento Quick Sort

Método de Burbuja (Bubble Sort)

El método de ordenamiento de burbuja, es un algoritmo que se aplica para poder ordenar una cantidad de datos ya sea de forma ascendente o descendente.

Es el algoritmo más fácil de implementar, pero a cambio pagamos un alto precio en procesamiento, ya que este método evalúa los datos muchas veces y en ocasiones innecesariamente (como por ejemplo cuando son iguales).

A estas alturas posiblemente ya tengas conocimiento de sencillos pasos para ordenar datos, como por ejemplo, Determinar cual es el mayor o menor de dos números, pues aplicando este método podremos ordenar array, estructuras y cualquier tipo de dato NO atómico (es decir que se pueda dividir)

Este libro trata de programación en C, entonces a continuación nos aplicamos a esto:

Explicación

Este metodo necesita de lo siguiente para implementarse:

Un array o estructura que ordenar (>1 elemento).
Dos variables contadoras de ciclos (i,j por ejemplo).
Una variable temporal (para almacenar un dato momentaneamente).
Dos ciclos y un Condicional...

....
//DE MENOR A MAYOR (Ascendente)
#define Nelementos 4
....

int i,j;                //Variables contadoras del ciclo.
int lista[Nelementos]={6,9,3,1}; //Declaracion e inicializacion de un arreglo de 4 elementos.
int temp=0;             //Variable temporal.

for (i=1;i<Nelementos;i++)
{
       for (j=0; j < Nelementos-i ;j++) // for(j=0; j < Nelementos-i; j++) es menor y no menor igual
       {
          if (lista[j] > lista[j+1])//Condicion mayor-menor
          {
            temp=lista[j];
            lista[j]=lista[j+1];
            lista[j+1]=temp;
          }
       }
}
//Para cambiar el modo de ordenamiento solo debemos cambiar la condicion < ó >

Explicando un poco lo que dice el codigo tenemos:

Iniciamos i a 1, de esta forma correremos el ciclo solamente 3 veces. Asi evitamos correr ciclos innecesariamente.
El segundo for, se ejecutara 3 veces por cada primer ciclo.
La condicion nos dice:

Si, el valor de lista 0 es mayor al valor de lista 1, es decir
Si, 6 > 9, pero como la condicion no se cumple, pasamos del ciclo y J=1.
Si, el valor de lista 1 es mayor al valor de lista 2, es decir
Si, 9 > 3, como es verdadera hacemos:

Guardamos momentaneamente en la variable temporal el valor de lista 1, es decir 9.
En la posicion de lista 1, guardamos el valor de lista 2, es decir 3.
En la posicion de lista 2, guardamos el valor de temp, es decir 9

Volvemos nuevamente al ciclo, ahora J=2...

Si, el valor de lista 2 es mayor al valor de lista 3, es decir
Si, 9 > 1, (recuerda que anteriormente movimos al 9 a la posicion de 3), es verdadera =>

Guardamos momentaneamente en la variable temporal el valor de lista 2, es decir 9.
En la posicion de lista 2, guardamos el valor de lista 3, es decir 1.
En la posicion de lista 3, guardamos el valor de temp, es decir 9.

De esta forma el ciclo se repite hasta que todos los datos se hallan movido. Como veras hasta ahora solo hemos estado moviendo el 9. Tu lista se veria asi:

Original: 6 9 3 1

1er Mov: 6 3 9 1
2do Mov: 6 3 1 9

Si bien ya esta mas ordenada que la original, aun falta bastante, pero recuerda que estábamos en el primer ciclo del primer for (i).

Acá te dejo como serán los demás movimientos:

Segundo Ciclo i:

3 6 1 9
3 1 6 9

Tercer Ciclo i:

1 3 6 9
YA!

En un principio, pensaba no presentarles las variaciones que hay de este algoritmo, pero revisando en varios libros me percate de que aunque es el mismo algoritmo y funciona de la misma forma (con sus ventajas y desventajas), Creo que es preferible mostrarselos para evitar confusiones y enredos innecesarios.

Variantes

Buscando en varios libros e Internet me he encontrado numerosas variantes, y por motivos pedagógicos voy a mostrarlos, ya que considero que aunque sean el mismo algoritmo, su diferente implementacion puede llevar a confusiones.

En lo personal considero que el algoritmo planteado al principio es el que mejor se expresa (entiende), y es el que recomiendo implementar, pero hay libros que lo implementan de otra forma, por lo que los que se guían con el, pueden tener confusiones a la hora de apoyarse con este libro.

Variante: 1 Ciclo.

Aunque en realidad usa dos ciclos un while y un for, el while hace la función de nuestro primer for. Sin embargo la demás implementaciones son técnicamente las mismas, solo que en vez de usar una variable ya preparada (j en nuestro caso), este evalúa con la variable i. </source>

Variante: Restar

Esta es una de las mas usuales que he visto en los libros, folletos y otros. Todo es igual, pero cambian las condiciones, de esta forma se trabaja a la inversa de nuestro algoritmo.

Ejemplos

El algoritmo burbuja esta preparado para correr con todo tipo de datos NO atomicos, es por esto que no importa si el arreglo es de tipo char, int, float, etc. Funcionara con sus respectivas modificaciones.

El siguiente ejemplo ordenara una lista de tamaño 6, que esta ordenada. Recuerden como buena practica:

Definir las variables en un solo punto del codigo.
Definir el tamaño del array como constante.
Usar la indentacion correspondiente (Tabulaciones).

//Realizado por Master crack cocaino 
//UNAN-LEON Nicaragua.

#include <stdio.h>
#define TAM 6

int main()
{

int lista[TAM]={12,10,5,6,1,3};	 //Declaracion e Inicializacion de un array
int temp=0; 			 //Variable temporal
int i,j;			 //variables corredoras del ciclo

printf("La lista DESORDENADA es: \n");

for (i=0;i<TAM;i++)
   printf("%3d",lista[i]);	//impresion de la lista con espacio de 3 lineas (%3d)

for (i=1;i<TAM;i++)
{
	for (j=0;j<TAM-1;j++)
	{
		if (lista[j] > lista[j+1])	 //condicion
		{
			temp = lista[j];	 //temp guarda momentaneamente el valor de lista[j]
			lista[j]=lista[j+1];  //Asigno al la posicion lista[j], lo que hay en lista[j+1]
			lista[j+1]=temp;	//obtendra un nuevo valor por parte de temp.
		}
	}

}

printf("\nLos valores ORDENADOS de lista son: \n");
for(i=0;i<TAM;i++)
    printf("%3d",lista[i]);

return 0;
}

//Revisado por: Gustavo A. Chavarria.
//UNAN-LEON Nicaragua

Método de Inserción

Este método se podría decir que es algo superior al método de la burbuja, ya que logra evaluar menos veces la condición. Sin embargo aun es un algoritmo muy pobre y que utiliza recursos técnicamente igual que el algoritmo burbuja.

Concepto

El algoritmo consiste en ordenar los dos primeros elementos de la matriz, luego se inserta el tercer elemento en la posición correcta con respecto a los dos primeros, a continuación se inserta el cuarto elemento en la posición correcta con respecto a los tres primeros elementos ya ordenados y así sucesivamente hasta llegar al ultimo elemento de la matriz.

Explicación

Ejemplos

void ordenamientoSeleccion(Tlista lista){

  Tlista actual, siguiente;   int t;
  actual = lista; int minimo;
  Tlista min=lista;
  
  while(actual->sgte!=NULL){
     minimo=actual->valor;
     min=actual;
     siguiente=actual->sgte;
     
     while(siguiente!=NULL){
        
        if(siguiente->valor < minimo){
        minimo = siguiente->valor;
        min = siguiente;
        }
        
        siguiente=siguiente->sgte;      
     }
     
     t= actual->valor;
     actual->valor=min->valor;
     min->valor=t;
     
     actual=actual->sgte;
     
  }

Método QuickSort:

Es el ultimo método del que hablaremos en este libro, es el algoritmo que mas calidad tiene, pudiendo llegar a lo mismo que el método burbuja e inserción, mas rápido y con uso de menos recursos.

Concepto

El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás. Esta es probablemente la técnica más rápida conocida. Fue desarrollada por Tony Hoare en 1960.

La idea del algoritmo es simple, se basa en la división en particiones de la lista a ordenar, por lo que se puede considerar que aplica la técnica divide y vencerás. El método es, posiblemente, el más pequeño de código, más rápido, más elegante, más interesante y eficiente de los algoritmos de ordenación conocidos.

Explicación

El método se basa en dividir los n elementos de la lista a ordenar en dos partes o particiones separadas por un elemento: una partición izquierda, un elemento central denominado pivote o elemento de partición, y una partición derecha. La partición o división se hace de tal forma que todos los elementos de la primera sublista (partición izquierda) son menores que todos los elementos de la segunda sublista (partición derecha). Las dos sublistas se ordenan entonces independientemente.
Para dividir la lista en particiones (sublistas) se elige uno de los elementos de la lista y se utiliza como pivote o elemento de partición. Si se elige una lista cualquiera con los elementos en orden aleatorio, se puede seleccionar cualquier elemento de la lista como pivote, por ejemplo, el primer elemento de la lista. Si la lista tiene algún orden parcial conocido, se puede tomar otra decisión para el pivote. Idealmente, el pivote se debe elegir de modo que se divida la lista exactamente por la mitad, de acuerdo al tamaño relativo de las claves.

Una vez que el pivote ha sido elegido, se utiliza para ordenar el resto de la lista en dos sublistas: una tiene todas las claves menores que el pivote y la otra, todos los elementos (claves) mayores que o iguales que el pivote (o al revés). Estas dos listas parciales se ordenan recursivamente utilizando el mismo algoritmo; es decir, se llama sucesivamente al propio algoritmo quicksort. La lista final ordenada se consigue concatenando la primera sublista, el pivote y la segunda lista, en ese orden, en una única lista. La primera etapa de quicksort es la división o «particionado» recursivo de la lista hasta que todas las sublistas constan de sólo un elemento.

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.

Algoritmo

void ordenar (int vect[], int ind_izq, int ind_der)
{
	int i, j; /* variables indice del vector */
	int elem; /* contiene un elemento del vector */

	i = ind_izq;
	j = ind_der;
	elem = vect[(ind_izq+ind_der)/2];
	do
	{
		while (vect[i] < elem) //recorrido del vector hacia la derecha
        {
            i++;
        }
		 
		while (elem < vect[j]) // recorrido del vector hacia la izquierda
        {
            j--;
        }
		 
		if (i <= j) /* intercambiar */
		{ 
			int aux; /* variable auxiliar */
			aux = vect[i];
			vect[i] = vect[j];
			vect[j] = aux;
			i++;
			j--;
		}
	} 
	while (i <= j);
           
    //Llamadas recursivas
	if (ind_izq < j) 
	{
		ordenar (vect, ind_izq, j);
	}
	if (i < ind_der) 
	{
		ordenar (vect, i, ind_der);
	}
}

Programación en C/Algoritmos y Estructuras de Datos

Sumario

Concepto

Método de Burbuja (Bubble Sort)

Explicación

Variantes

Variante: 1 Ciclo.

Variante: Restar

Ejemplos

Método de Inserción

Concepto

Explicación

Ejemplos

Método QuickSort:

Concepto

Explicación

Algoritmo