ORDENAMIENTO
Concepto
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 Ordenamiento
La ordenación o clasificación de datos consiste en la disposición de los mismos de acuerdo con algún valor o característica.
Por ejemplo, cada elemento de una agenda telefónica tiene un campo nombre, un campo dirección y un campo número telefónico. Por lo regular los datos en la agenda se encuentran organizados en un orden de la A la Z.
De la misma forma un lista ó vector de datos se dice que esta ordenado de manera ascendente, si X [ i ] <= X [ i +1] y, por otro lado, se dice que esta ordenado de manera descendente sí X [ i ] >= X [ i +1].
El proceso de ordenación es uno de los mecanismos más interesantes cuando llega el momento de mostrar que existen múltiples soluciones para un mismo problema, y que cada solución algorítmica tiene sus propias ventajas y desventajas.
Una forma de medir la eficiencia de un algoritmo de esta clase, es verificar el número de comparaciones entre valores clave, además del número de movimientos que se tengan que realizar entre elementos (intercambios) de la lista.
Los métodos de ordenamiento que trabajan con estructuras de datos residentes en memoria principal se denominan Ordenamientos Internos, mientras que las implementaciones que utilizan estructuras de datos residentes en archivos se conocen como Ordenamientos externos.
Ordenamiento Interno
Los métodos de ordenamiento interno trabajan en memoria principal y sus implementaciones son muy variadas, de manera que la elección del algoritmo adecuado debe realizarse con criterios de eficiencia (tiempo y ejecución) y en función de la memoria disponible. Dividiremos los métodos en dos grandes grupos:
• Directos (burbuja, selección e inserción).
• Logarítmicos (Shell sort, Merge sort, Heap sort, Quick sort, Radix).
En el caso de listas pequeñas, los métodos directos se desempeñan de manera relativamente eficientes, ya que la codificación del algoritmo correspondiente no es compleja. Su uso es muy frecuente. Sin embargo, en arreglos grandes las ordenaciones directas resultan ineficientes y se necesitara un método logarítmico para su solución.
Ordenamiento Externo
La ordenación de archivos se lleva a cabo cuando el volumen de los datos a tratar es demasiado grande y los mismos no caben en la memoria principal de la computadora.
Al ocurrir esta situación no pueden aplicarse los métodos de ordenación interna, de modo que debe pensarse en otro tipo de algoritmos para ordenar datos almacenados en archivos.
Por ordenación de archivos se entiende, entonces, la ordenación o clasificación de éstos, ascendente o descendentemente, de acuerdo con un campo determinado al que se denominará campo clave. La principal desventaja de esta ordenación es el tiempo de ejecución, debido a las sucesivas operaciones de entrada y salida.
Los dos métodos de ordenación externa más importantes son los basados en la mezcla directa y en la mezcla equilibrada.
Ejemplo
//Ordena burbuja, ordenamiento
//de un arreglo metodo burbuja
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
void mostrarArreglo(const int[], int); //prototipo de funcion que recibe un arreglo constante
void ordenarArreglo(int[], int); //prototipo que modifica y ordena elarreglo
void intercambiar(int&, int&); //prototipo, intercambialos valores de dos elementos
int main()
{
const int tamano = 15;
int arreglo[tamano] = {25,17,13,16,41,32,12,115,95,84,54,63,78,21,10};
cout << "Arreglo antes de ordenarse: " <<endl;
mostrarArreglo(arreglo,tamano);
cout << "Arreglo despues de ordenarse: " <<endl;
ordenarArreglo(arreglo,tamano);
mostrarArreglo(arreglo,tamano);
cout << "Fin del programa :)" << endl;
return 0;
}//fin de main
void mostrarArreglo(const int arreglo[], int tamano)
{
for (int i = 0 ; i < tamano ; i++)
cout << "arreglo["<< i << "]=" << arreglo[i]<< endl;
}
void ordenarArreglo(int arreglo[], int tamano)
{
for (int i = 0; i<tamano-1 ; i++)
for (int j = 0; j<tamano-1 ; j++)
if(arreglo[j] < arreglo[j+1])
intercambiar(arreglo[j],arreglo[j+1]);
}
void intercambiar(int &a, int &b)
{
int tmp = b;
b = a;
a = tmp;
}
