Métodos de ordenamiento
Introducción
Una de las operaciones más importantes en el manejo de datos es el ordenamiento. La ordenación (o sort en inglés), es reagrupar u organizar los elementos de un grupo de datos en una secuencia específica de orden (relación de orden), ya sea de mayor a menor, menor a mayor o, en caso de tratarse de otro tipo de datos como caracteres, ordenar por orden alfabético de manera descendente o ascendente. Muchas de estas operaciones las vemos en las hojas de cálculo como MS Excel, en páginas de internet y bases de datos.
Nos centraremos en los métodos o algoritmos más populares, analizando la cantidad de comparaciones que suceden, el tiempo que demora y ejemplificando con pseudocódigo o código en lenguaje de programación; ya que estas características son las que nos permiten tomar la decisión de qué algoritmos usar; es decir, dependiendo de los recursos de cómputo que tengamos o el tiempo para realizar el ordenamiento.
Muchos lenguajes de programación ya incluyen funciones de ordenamiento optimizadas, por lo cual tal vez no sea necesario que llegues a programarlas en la práctica, pero el hecho de que se sepa cómo implementar diferentes métodos de ordenamiento, es una práctica indispensable para desarrollar habilidades en cualquier programador.
Ordenamiento
La ordenación o clasificación de datos es una operación consistente en disponer un conjunto-estructura- de datos en algún determinado orden con respecto a uno de los campos de elementos del conjunto.
Por ejemplo, cada elemento del conjunto de datos de una guía de teléfono tiene un campo nombre, un campo dirección, un campo número de teléfono, la guía telefónica está dispuesta en orden alfabético de nombres, los elementos numéricos se organizan en orden creciente o decreciente de acuerdo al valor numérico del elemento.
En terminología de ordenación el elemento por el cual esta ordenado un conjunto de datos se denomina clave.
Una colección de datos (estructura) puede ser almacenada en un archivo, un array, un array de registros, una lista enlazada o un árbol.
Cuando los datos están almacenados en un array, una lista enlazada o un árbol se denomina ordenación interna. Si los datos están almacenados en un archivo el proceso de ordenación se llama ordenación externa.
Una lista se dice que esta ordenada por la clave K si la lista está en orden ascendente o descendente con respecto a esta clave.
La lista se dice que está en orden ascendente así:
i < j implica que K[i] <= K[j]
y se dice que está en orden descendente así:
i > j implica que K[i] >= K[j]
para todos los elementos de la lista
Por ejemplo:
4 5 14 21 32 45 orden ascendente
75 70 35 16 14 12 orden descendente
Zacarías Rodríguez Martínez López García orden descendente
Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento.
El ordenamiento se efectúa con base en el valor de algún campo en un registro.
El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.
Tipos de ordenamientos:
Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.
Los internos:
Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a [1], a [500], etc.).
Los externos:
Son aquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc.), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc.).
Autor: Lucas Mórea
¿Cómo se sabe cuál es el mejor algoritmo?
La eficiencia es el factor que mide la calidad y rendimiento de un algoritmo. En este caso de la operación de ordenación se consideran dos criterios al momento de decidir:
1. Tiempo menor de ejecución en computadoras.
2. Menor número de instrucciones.
Sin embargo no siempre es fácil efectuar estas medidas, puede no disponerse de instrucciones para medida de tiempo, y las instrucciones pueden variar dependiendo del lenguaje y del propio estilo del programador. Por esta razón el mejor criterio para medir la eficiencia de un algoritmo es aislar una operación específica clave en la ordenación y contar el número de veces que se realiza. Así en el caso de los algoritmos de ordenación, se utilizara como medida de su eficiencia el número de comparaciones entre elementos efectuados.
El algoritmo de ordenación A será más eficiente que el B, si requiere menor número de comparaciones.
Los métodos de ordenación se suelen dividir en dos grandes grupos:
- Directos burbuja, selección , inserción
- Indirectos Shell
En el caso de listas pequeñas, los métodos directos se muestran eficientes, sobre todo porque los algoritmos son sencillos, su uso es muy frecuente. Sin embargo en listas más grandes estos métodos se muestran ineficaces y es preciso recurrir a los métodos avanzados.
Algoritmos de Ordenación Básicos
Los algoritmos presentan diferencias entre ellos que los conviertes en más o menos eficientes y prácticos según sea la rapidez y eficiencia demostrada para cada uno de ellos.
Los algoritmos básicos de ordenación más simples y clásicos son:
- Ordenación por Selección.
- Ordenación por Inserción.
- Ordenación por Burbuja.
Los métodos más recomendados son: selección e inserción, aunque se estudiará el método de la burbuja. Por aquello de ser el más sencillo aunque a la par es el más ineficiente: por esta causa no recomendamos su uso, pero si conocer su técnica.
Autor: Luis Joyanes Aguilar
Clasificación de los algoritmos de ordenamiento de información:
El hecho de que la información está ordenada, nos sirve para poder encontrarla y accesarla de manera más eficiente ya que de lo contrario se tendría que hacer de manera secuencial.
Autor: Lucas Mórea
Método de ordenamiento por intercambio directo Bubble Sort(Burbuja)
El bubble sort, también conocido como ordenamiento burbuja, funciona de la siguiente manera: Se va comparando cada elemento del arreglo con el siguiente; si un elemento es mayor que el que le sigue, entonces se intercambian; esto producirá que en el arreglo quede como su último elemento, el más grande. Este proceso deberá repetirse recorriendo todo el arreglo hasta que no ocurra ningún intercambio. Los elementos quevan quedando ordenados ya no se comparan. "Baja el más pesado".
Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados este método también es conocido como intercambio directo.
Ejemplo:
Sea un arreglo de 6 números de empleados: :
Primera pasada:
<-- Se cambia el 21 por el 40.
<-- Se cambia el 40 por el 4.
<-- Se cambia el 9 por el 40.
<-- Se cambia el 40 por el 10.
<-- Se cambia el 35 por el 40.
Segunda pasada:
<-- Se cambia el 21 por el 4.
<-- Se cambia el 9 por el 21.
<-- Se cambia el 21 por el 10
Ya están ordenados, pero para comprobarlo habría que acabar esta segunda comprobación y hacer una tercera.
Para su implementación generalmente definimos una función donde A=arreglo y
N=tamaño como sigue:
int bubblesort(int A[],int N){
int i,j,AUX;
for(i=2;i<=N;i++){ //avanza
for(j=N;j>=i;j--){ //retrocede
if(A[j-1]>A[j]){ //si a > p intercambio
AUX=A[j-1];
A[j-1]=A[j];
A[j]=AUX;
}
}
}
return 1;
}
Método de la burbuja implementación
En esta implementación de la función bubblesort utilizamos un for anidado con los índices i y j para ir comparando y ordenando los elementos durante el recorrido del arreglo.
Análisis de eficiencia del método de intercambio directo
Este método es el más fácil de implementar; sin embargo con mayor volumen de datos es el más ineficiente.
En el método bubble Sort tendremos consecutivas comparaciones entre pares de números de tal manera que en la primera pasada tendremos (n-1) comparaciones y en la segunda (n-2) y así sucesivamente hasta llegar a 2 y 1 comparaciones entre elementos dependiendo de tamaño del arreglo. Expresado en otros términos, esta operación se reduce a: BS = (n2 -n)/2 donde BS es el método bubble Sort. El número de elementos a ordenar dependen de si el arreglo está ordenado, desordenado o en orden inverso. Esto es: Para un arreglo ordenado = 0, para uno desordenado = 0.75 * (n2 - n) y para uno con orden inverso será = 1.5 * (n2 - n). El tiempo necesario para ejecutar el algoritmo Bubble Sort es proporcional a n2, donde n es el número de elementos del arreglo. Mientras más elementos contenidos en el arreglo, mayor será el número de comparaciones y menor la calidad de este método.
Intercambio inverso
El método por intercambio inverso es otra modalidad de intercambio, así tenemos que: Ordenando los elementos del arreglo usando el método bubblesort, se transporta en cada pasada el elemento más pequeño a la parte izquierda del arreglo A de N elementos.
Un ejemplo de pseudocódigo para este proceso sería:
bubblesort1(A,N)
Inicio
Declarar i,j,aux:entero
Para i = 2 hasta N haga
Para j = i hasta 2 inc (-1) haga
Si (A[j-1]>A[j]) entonces
Aux = A[j-1]
A[j-1] = A[j]
A[j] = aux
Fin si
Fin para
Fin para
Fin
Intercambio inverso contrario al anterior
El intercambio inverso es una mejora al método bubble Sort que consiste en la modalidad de que en cada pasada del arreglo el valor más grande se lleva a la derecha en lugar de la izquierda. Se tienen dos etapas, en la primera se trasladan los elementos más pequeños hacia la izquierda almacenando en una variable el último elemento intercambiado. En la segunda, se trasladan los elementos más grandes hacia la parte derecha del arreglo almacenando en otra variable la posición del último elemento
intercambiado.
Un pseudocódigo para este proceso sería:
bubblesort2(A,N)
Inicio
Declarar i,j,aux:entero
Para i = 1 hasta N-1 haga
Para j = 1 hasta N-i haga
Si (A[j]>A[j+1]) entonces
Aux = A[j]
A[j] = A[j+1]
A[j+1] = aux
Fin si
Fin para
Fin para
Fin
