Los métodos de ordenamiento son algoritmos que permiten clasificar un conjunto de datos de acuerdo a un determinado orden o criterio de clasificación.
Normalmente los criterios que utilizan los métodos de ordenamiento para clasificar sus datos son a través de un orden ascendente (menor a mayor valor) o descendente (mayor a menor valor).
Tipos de ordenamiento
En las ciencias de la computación, existen dos tipos de ordenamiento:
- Ordenamiento interno: Es aquel que se realiza directamente en la memoria principal de la computadora, es decir en la memoria RAM.
- Ordenamiento externo: Es aquel en el cual los datos no caben en la memoria principal y por lo tanto ocupan una memoria secundaria, es decir utilizando archivos almacenados en el disco duro.
Eficiencia de los métodos de ordenamiento
Para determinar qué tan eficaz es un método de ordenamiento, se utilizan algunos parámetros, entre los que más destacan los siguientes:
- El número de pasos que se requieren para realizar un ordenamiento total.
- El total de comparaciones entre las llaves para ordenar la totalidad de registros. (Comparación entre llaves costosa)
- El número de intercambios de registros. (Cuando la operación de registro es costosa)
Métodos de ordenamiento famosos
Debido a que la necesidad de ordenar datos es muy frecuente en muchos de los algoritmos utilizados en los distintos lenguajes de programación, Sean establecido algunos métodos estándares para realizar el ordenamiento de datos.
Algunos de los métodos o algoritmos de ordenamiento más famosos que son utilizados en las ciencias de la computación son los siguientes:
Bubblesort (Método burbuja)
El método burbuja, también conocido como intercambio directo es un método muy utilizado para ordenar una lista dentro de un arreglo. Su funcionamiento es muy intuitivo:
- Comparamos un elemento con el adyacente.
- Si el elemento es mayor, lo intercambiamos.
- Pasar al siguiente par de elementos hasta terminar la lista.
- Repasar de nuevo el mismo algoritmo en toda la lista n-1 veces.
Complejidad de Bubblesort
El análisis de complejidad de este método de ordenamiento es el siguiente:
c = (n-1) + (n-2) + ... + 2 + 1 = (n*(n-1))/2
En donde c es el número total de comparaciones por el método burbuja, y simplificando esa expresión tenemos que:
c = (n2-n)/2
Cuál es el número de comparaciones necesarias para este ordenamiento, es decir que su complejidad en el peor de los casos es del orden O(n2).
El término “O” significa cota superior asintótica, también conocida como notación O grande en la Teoría de complejidad computacional, y significa que ningún valor puede ser mayor al máximo valor de esa cota.
Código de Bubblesort en Lenguaje C
El código en lenguaje C para efectuar un ordenamiento por el algoritmo bubblesort es el siguiente:
void bubblesort(int A[], int n){
int x,y;
for(x=0; x<n-1; x++)
for(y=n-1; y>x; y--)
if(A[y] < A[y-1])
intercambia(&A[y], &A[y-1]);
}
Y un ejemplo de uso lo mostramos en el siguiente artículo:
Quicksort
El algoritmo Quicksort es uno de los métodos de ordenamiento más eficaces en cuanto complejidad. También conocido como el método del pivote, consta de una serie de pasos que ordena una lista utilizando el siguiente procedimiento:
- Selecciona un elemento x al azar.
- Busca por la izquierda de x un elemento mayor.
- Busca por la derecha de x un elemento menor.
- Si los índices izquierdo y derecho no se han cruzado, intercambiar el elemento mayor.
- Regresar al paso 2 mientras no se crucen los índices izquierdo y derecho.
- Intercambiar x con el elemento de la derecha.
- Dividir el arreglo en dos subarreglos, en donde x es un nuevo pivote y el subarreglo izquierdo contiene elementos menores o iguales que x, mientras que el subarreglo derecho contiene valores mayores que x.
- Realizar Quicksort con el arreglo izquierdo.
- Realizar Quicksort con el arreglo derecho.
Complejidad de Quicksort
La complejidad del algoritmo Quicksort varía en tres casos diferentes:
- Mejor caso: Sucede cuando en cada pasada se selecciona el elemento central del conjunto. La complejidad en este caso es O(log n).
- Caso promedio: Es el tiempo promedio de ejecución, el cual es c = (n-1)* log n, es decir: O(n*log n).
- Peor caso: Sucede cuando el arreglo está arreglado o en orden inverso, su complejidad es c = (n2+n)/2-1, y por lo tanto es del orden O(n2).
Código de QuickSort en lenguaje C
El código para efectuar un ordenamiento por QuickSort es el siguiente:
void quicksort(int A, int x, int y)
{
int ind, z;
ind = pivote(A, x, y);
if(ind >= 0) {
z = particion(A, x, y, A[ind]);
quicksort(A, x, z-1);
quicksort(A, z, y);
}
}
La función necesaria para realizar una partición en el método de Quicksort es el siguiente:
int particion(int A[], int x, int y, int v) {
int l, r;
l = x;
r = y;
do {
intercambia(A[l], A[r])
while(compara(A[l], v) < 0) l++;
while(compara(A[r], v) >= 0) r--;
} while (l < r);
return 1;
}
Y la función pivote es la siguiente:
int pivote(int A[], int x, int y) {
int z, r;
for(z=x+1; z<=y; z++) {
r = compara(A[z], A[x]);
if(r < 0)
return x;
else if(r > 0)
return z;
}
return -1;
}
Para ver un ejemplo de uso del algoritmo Quicksort, porfavor visita el siguiente artículo:
Método de selección
El método de selección es muy sencillo, este algoritmo consiste en ordenar el menor elemento de una lista en cada interacción, colocándolo en su posición dentro de la lista.
El procedimiento para efectuar un ordenamiento con este algoritmo es el siguiente:
- Seleccionar el menor elemento en cada iteración de toda la lista.
- Colocarlo en su lugar intercambiando el elemento.
- Repetir el procedimiento con el resto de los elementos de la lista.
Complejidad del algoritmo de selección
El algoritmo de selección requiere acomodar un array utilizando el array original. Por lo tanto, requiere realizar el siguiente número de operaciones:
c = (n-1) + (n-2) + ... + 2 + 1 = (n*(n-1))/2
Y por lo tanto el número de operaciones realizadas es del orden O(n2):
c = (n2-n)/2
Código del algoritmo de selección en lenguaje C
El código en lenguaje C para realizar este algoritmo es el siguiente:
void selection(int A[], int n) {
int x, y, xmin;
for(x=0; x<n-1; x++) {
xmin = x;
for(y=x+1; y>n; y++)
if(A[y] < A[xmin]) xmin = y;
intercambia(&A[x], &A[xmin]);
}
}
Ejemplo de uso del algoritmo de selección:
9 - 3 - 8 - 2 - 5 2 - 3 - 8 - 9 - 5 2 - 3 - 8 - 9 - 5 2 - 3 - 5 - 9 - 8 2 - 3 - 5 - 8 - 9
Método de inserción
La inserción es uno de los métodos de ordenamiento más semejantes a los utilizados en forma natural al del ser humano. El método consiste en insertar elementos en forma ordenada en una lista directamente en el orden que le corresponde.
Aunque ésta operación en forma humana podría consistir en una única operación, debido a nuestras capacidades cognitivas, para una computadora implica el uso de un algoritmo que consiste en tomar un elemento y colocarlo en un arreglo nuevo en la posición que le corresponde.
Análisis de complejidad del algoritmo de inserción
Cuando los datos se encuentran en forma ordenada, tenemos el caso óptimo, en donde solo se efectúan n comparaciones, es decir una complejidad Θ(n).
En el peor caso, los datos están ordenados en orden inverso. En éste caso tenemos las mismas operaciones que en el algoritmo de selección:
c = (n-1) + (n-2) + ... + 2 + 1 = (n*(n-1))/2
Así en el peor caso tenemos de complejidad: Θ(n2).
La cota ajustada asintótica (Θ) guarda una relación con las cotas asintóticas superior e inferior, es decir el valor obedece tanto la notación O grande (O) y también la notación inferior asintótica (Ω), por lo tanto Θ(n2) también es O(n2) y Ω(n2).
Código del algoritmo de inserción en lenguaje C
El código en lenguaje C para realizar el algoritmo de inserción es el siguiente:
void insertion(int A[], int n) {
int x,y;
for(x=1; x<n; x++) {
y = x;
while(y > 0 && A[y] < A[y-1]) {
intercambia(&A[y], &A[y-1]);
y--;
}
}
}
Y a continuación te mostramos un ejemplo del uso del algoritmo de selección:
Primer arreglo (Arreglo original):
9 - 4 - 6 - 2 - 1
Segundo arreglo (Arreglo ordenado):
9 4 - 9 4 - 6 - 9 2 - 4 - 6 - 9 1 - 2 - 4 - 6 - 9
¿Qué es la complejidad en los métodos de ordenamiento?
La complejidad en los métodos de ordenamiento significa en términos simple, la cantidad de operaciones que requiere un algoritmo para completarse.
Aunque en ejemplos sencillos y cortos no haya gran diferencia entre una complejidad de orden O(n) y otra de orden O(n2), a gran escala el cambio en el número de operaciones es significativo en cuanto a tiempos de ejecución y coste computacional.
Ejemplo de complejidad en los métodos de ordenamiento
Si un algoritmo requiere de 5 iteraciones (valor de n) para completarse con los métodos de ordenamiento, podemos ver que el número de operaciones no cambia mucho.
O(n) ≈ 5 operaciones O(n2) ≈ 25 operaciones O(n3) ≈ 125 operaciones
Pero si el algoritmo requiere 450 operaciones para completarse, el valor del orden si importa, véase el siguiente ejemplo:
O(n) ≈ 450 operaciones O(n2) ≈ 202500 operaciones O(n3) ≈ 191,125,000 operaciones
Lo cual significa que el número de operaciones cambia de solo 450 operaciones a ¡casi 200 millones! en solo pasar del lineal al cúbico.
Ésta diferencia podría significar de un cálculo que se podría hacer en pocos segundos vs otro cálculo que requiere varios meses en completarse, aún teniendo el mismo resultado.
Por esa razón, es bueno analizar la complejidad de los métodos de ordenamiento, para reducir costos computacionales y optimizar los algoritmos.