Índice
Bueno, como dice el título de la entrada, voy a hablar sobre los algoritmos de ordenación, vamos a distinguir entre lentos y rápidos. La diferencia mas grande es la eficiencia, es decir, como se comportan al ordenar una gran entrada de datos, los lentos se comportan en un orden cuadrático, es decir, O(n²), mientras que los algoritmos rápidos se comportan, en un caso promedio en un orden logarítmico, osea, O (n log n).
Siempre que nos enseñan a ordenar un vector, o una lista, nos enseñan los algoritmos mas triviales y lógicos que cualquiera podría implementar. Estos algoritmos son:
- Ordenamiento burbuja (Bubblesort) .
- Ordenamiento por selección.
- Ordenamiento por inserción.
El ordenamiento por burbuja 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. Es un algoritmo estable. El inconveniente es que es muy lento.
static void burbuja_lims(int T[], int inicial, int final)
{
int i, j;
int aux;
for (i = inicial; i i; j--)
if (T[j] < T[j-1])
{
aux = T[j];
T[j] = T[j-1];
T[j-1] = aux;
}
}
El ordenamiento por inserción técnicamente es la forma mas lógica de ordenar cualquier cosa para un humano, por ejemplo, una baraja de cartas. Requiere O(n²).
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.
static void insercion_lims(int T[], int inicial, int final)
{
int i, j;
int aux;
for (i = inicial + 1; i < final; i++) {
j = i;
while ((T[j] 0)) {
aux = T[j];
T[j] = T[j-1];
T[j-1] = aux;
j--;
};
};
}
Por último, el ordenamiento por selección: Al igual que el algoritmo de inserción es muy trivial, puesto que recorre el vector o la lista, buscando el elemento mas pequeño y colocandolo en la posición 0 del vector, y así sucesivamente n-1 veces, tanto de grande como sea el vector. Al igual que los algoritmos anteriores, requiere O(n²) .
static void seleccion_lims(int T[], int inicial, int final)
{
int i, j, indice_menor;
int menor, aux;
for (i = inicial; i < final - 1; i++) {
indice_menor = i;
menor = T[i];
for (j = i; j < final; j++)
if (T[j] < menor) {
indice_menor = j;
menor = T[j];
}
aux = T[i];
T[i] = T[indice_menor];
T[indice_menor] = aux;
};
}
Ahora vamos a hablar de los rápidos que son los mas interesantes:
static void mergesort_lims(int T[], int inicial, int final)
{
if (final - inicial < UMBRAL_MS)
{
insercion_lims(T, inicial, final);
} else {
int k = (final - inicial)/2;
int * U = new int [k - inicial + 1];
assert(U);
int l, l2;
for (l = 0, l2 = inicial; l < k; l++, l2++)
U[l] = T[l2];
U[l] = INT_MAX;
int * V = new int [final - k + 1];
assert(V);
for (l = 0, l2 = k; l < final - k; l++, l2++)
V[l] = T[l2];
V[l] = INT_MAX;
mergesort_lims(U, 0, k);
mergesort_lims(V, 0, final - k);
fusion(T, inicial, final, U, V);
delete [] U;
delete [] V;
};
}
static void quicksort_lims(int T[], int inicial, int final)
{
int k;
if (final - inicial < UMBRAL_QS) {
insercion_lims(T, inicial, final);
} else {
dividir_qs(T, inicial, final, k);
quicksort_lims(T, inicial, k);
quicksort_lims(T, k + 1, final);
};
}
¿Has visto algún error?: Por favor, ayúdame a corregirlo contactando conmigo o comentando abajo.