ORDENAMIENTO Y BUSQUEDA
En
arreglos simples
ORDENAMIENTO
Los algoritmos de ordenamiento nos permiten,
como su nombre lo dice, ordenar. Ordenar colecciones de datos como vectores,
matrices, colecciones de objetos. Nos centraremos en los métodos más populares,
analizando la cantidad de comparaciones que suceden, el tiempo que demora y
revisando el código, escrito en Java, de cada algoritmo.
MÉTODOS ITERATIVOS
Estos métodos son simples de entender y de
programar ya que son iterativos, simples ciclos y sentencias que hacen que el
vector pueda ser ordenado. Dentro de los Algoritmos iterativos encontramos:
– Burbuja
– Inserción
– Selección
– Shellsort
METODOS RECURSIVOS
Estos métodos son aún más
complejos, requieren de mayor atención y conocimiento para ser entendidos. Son
rápidos y efectivos, utilizan generalmente la técnica Divide y vencerás, que
consiste en dividir un problema grande en varios pequeños para que sea más
fácil resolverlos.
Mediante llamadas recursivas a sí mismos, es posible que el tiempo
de ejecución y de ordenación sea más óptimo. Dentro
de los algoritmos recursivos encontramos:
– Ordenamiento por Mezclas (merge sort)
– Ordenamiento Rápido (quick sort)
Dentro de cada método, inclusive, existen
variantes. Es decir, variaciones que han mejorado el algoritmo original.
BURBUJA
El método de la burbuja es uno de los más
simples, es tan fácil como comparar todos los elementos de una lista contra
todos, si se cumple que uno es mayor o menor a otro, entonces los intercambia
de posición.
Por ejemplo, imaginemos que tenemos el
siguiente vector: 5, 6, 1, 0, 3
Lo que haría una burbuja simple, seria
comenzar recorriendo los valores de izquierda a derecha, comenzando por el 5.
Lo compara con el 6, con el 1, con el 0 y con el 3, si es mayor o menor (dependiendo
si el orden es ascendente o descendente) se intercambian de posición. Luego
continua con el siguiente, con el 6, y lo compara con todos los elementos de la
lista, esperando ver si se cumple o no la misma condición que con el primer
elemento. Así, sucesivamente, hasta el último elemento de la lista.
Código java:
int temp;
for(int i = 0; i < limite; i++){
for(int j = 0; j < limite-1; j++){
if(vector[j] > vector[j+1]){
temp
= vector[j];
vector[j] = vector[j+1];
vector[j+1] = temp;
}
}
}
BURBUJA OPTIMIZADA
El hecho de que los elementos que están detrás del que se está
comparando, ya están ordenados, las comparaciones serian aún menos y el método
seria aún más efectivo. Si tenemos una lista de 10 elementos y estamos
analizando el quinto elemento, qué sentido tiene que el quinto se compare con
el primero, el segundo o el tercero, si supuestamente, ya están ordenados
Entonces optimizamos más aún el algoritmo, quedando nuestra versión final del
algoritmo optimizado de la siguiente manera:
Código
java:
int temp;
for (int i=0 ; i<limite -
1; i++)
for (int j=i+1;
j<limite; j++)
if (vector[i] >
vector[j]){
temp = vector[i];
vector[i] =
vector[j];
vector[j] =
temp;
}
Analizar la siguiente Variante:
boolean
hayCambios = true;
int temp;
for (int i = 0; hayCambios ; i++) {
hayCambios = false;
for (int j = 0; j < limite - 1; j++) {
if (vector[j] > vector[j + 1]) {
temp
= vector[i];
vector[i] = vector[j];
vector[j] = temp;
hayCambios = true;
}
}
}
INSERCIÓN:
El bucle principal de la ordenación por
inserción va examinando sucesivamente todos los elementos del vector desde el
segundo hasta el n-ésimo, e inserta cada uno en el lugar adecuado entre sus
precedesores dentro del vector.
Código java:
int i, temp, j;
for (i = 1; i
< vector.length; i++){
temp = vector[i];
j = i - 1;
while (
(vector[j] > temp) && (j >= 0){
vector[j +
1] = vector[j];
j--;
}
vector[j + 1] = temp;
}
SELECCION:
La ordenación por selección funciona seleccionando
el menor elemento del vector y llevándolo al principio; a continuación
selecciona el siguiente menor y lo pone en la segunda posición del vector y así
sucesivamente.
Código
java:
int i, j, k, p, buffer,
limit = vector.length-1;
for(k = 0; k < limit; k++){
p = k;
for(i
= k+1; i <= limit; i++)
if(vector[i] < vector[p]) p = i;
if(p != k){
buffer = vector[p];
vector[p] = vector[k];
vector[k] = buffer;
}
}
COMPARACION DE TIEMPOS
Se
han ordenado una cantidad determinada de elementos aleatorios en una lista
mediante distintos métodos de ordenamiento y se ha registrado el tiempo de
ejecución en segundos:
BUSQUEDA:
Puede
aplicar su método de búsqueda secuencial.
int busquedaSecuencial( int
key ){
for(int i=0,
i<n, i++){
if(vector[i]==key)
return
i; }
return -1;
}
Sin
embargo, cuando el vector está ordenado, el método de búsqueda puede mejorar en
tiempo, de la siguiente manera:
int
busquedaSecuencial( int key){
int i
= 0;
while(i<n
&& vector[i]<key){
i++;
}
if(i<n)
return i;
else
return-1;
}
También
se puede aplicar la búsqueda binaria cuando se tiene un vector ordenado, de la
siguiente manera:
int
busquedaBinaria (int key ){
int inicio =
0 ;
int fin =n-1;
while(
inicio <= fin ){
int
mitad <-(inicio + fin) / 2;
if(
vector[mitad] < key )
inicio = mitad + 1;
else
if( vector[mitad] > key )
fin = mitad –1;
else
return mitad; }
return -1;
}
0 comentarios:
Publicar un comentario