ORDENACION
Ahora vamos a ver problemas clásicos de la programación de vectores que es la Ordenación.
Ordenar los elementos de un vector mediante algún criterio es una operación típica y en absoluto trivial. Por ejemplo, un vector de números enteros puede ordenarse de menor a mayor. Si el vector original es este:
0 1 2 3 4
+---+---+----+---+---+
| 5 | 3 | 14 | 9 | 8 |
+---+---+----+---+---+
…si lo ordenamos de forma creciente (de menor a mayor), nos quedará este otro vector:
0 1 2 3 4
+---+---+---+---+----+
| 3 | 5 | 8 | 9 | 14 |
+---+---+---+---+----+
Del mismo modo, se pueden ordenar los elementos con cualquier otro criterio: de mayor a menor, primero los pares y luego los impares, o cualquier otro que nos resulte útil para resolver un problema.
Métodos de ordenación de vectores hay muchos, desde los más simples (e ineficientes) hasta los más elaborados, y constituyen un área de estudio muy interesante dentro de la algorítmica.
A continuación mostraremos tres métodos de ordenación muy populares:
- El método de la burbuja (o de intercambio directo), un método sencillo de entender pero bastante lento
- El método de selección, otro método simple e ineficiente.
- El método de inserción, un algoritmo bastante sencillo.
Ordenación por INTERCAMBIO (burbuja)
El método de la burbuja es muy ineficiente, es decir, tarda mucho tiempo en ordenar un vector si éste es muy largo. Pero es fácil de entender, así que vamos a comenzar por aquí.
La idea general es simple: tomaremos los dos primeros elementos y los compararemos. Si están desordenados, intercambiamos sus posiciones. Si están ordenados, los dejamos como están.
Después haremos lo mismo con los elementos segundo y tercero (comparar y, si es necesario, intercambiar). Luego, con el tercero y el cuarto. Después con el cuarto y el quinto, y así sucesivamente hasta recorrer el vector completo.
Cuando lleguemos al final, el vector no estará todavía ordenado, pero el elemento más grande del vector habrá subido hasta la última posición, igual que una burbuja de aire en el agua.
Si volvemos a repetir el proceso desde el principio, el segundo elemento más grande habrá subido hasta la penúltima posición del vector. Y, la siguiente vez, el tercer elemento más grande subirá hasta la antepenúltima posición. Y así hasta que ordenemos todos los elementos.
Si el vector tiene N elementos, hay que repetir el recorrido N veces, aunque en cada repetición podemos quedarnos una posición más abajo del final, ya que sabemos con seguridad que los últimos elementos están colocados en su sitio.
El algoritmo funciona exactamente igual si recorremos el vector desde el final hacia el principio, sólo que, en ese caso, son los elementos más pequeños los que van descendiendo y colocándose en su posición definitiva en cada iteración del algoritmo.
En la siguiente implementación, usamos este segundo enfoque: repetimos el proceso tantas veces como elementos tenga el vector (LONGITUD_VECTOR) y, en cada repetición, recorremos el vector desde el final hacia atrás, comparando e intercambiando pares adyacentes de elementos.
void ordena_vector(int v[LONGITUD_VECTOR])
{
int i, j, elem;
for (i = 1; i < LONGITUD_VECTOR; i++)
{
for (j = LONGITUD_VECTOR - 1; j >=i; j--)
{
if (v[j-1] > v[j])
{
elem = v[j-1];
v[j-1] = v[j];
v[j] = elem;
}
}
}
}
El método de la burbuja necesita muchos pasos para completarse (y por eso tarda tanto y se dice que es un algoritmo ineficiente). En concreto, si vector tiene N elementos, hay que ejecutar alrededor de N*N pasos para completar la ordenación. Por eso no es un método práctico cuando se trata de vectores muy grandes.
Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.
Otro código de burbuja
void ordena_vector(int v[LONGITUD_VECTOR])
{
int i, j, elem;
for (j=1; j <= LONGITUD_VECTOR; j++)
{
for (i=0; i< LONGITUD_VECTOR -1; i++)
{
if (v[i] > v[i+1])
{
elem = a[i];
v[i] = v[i+1];
v[i+1] = elem;
}
}
}
}
