Métodos de ordenamiento y búsqueda

Universidad tecnológica de aguascalientes |
Métodos de ordenamiento y búsqueda |
Desarrollo de aplicaciones web |
|
|
Barba Sánchez Juan CarlosCastro Rejón Jorge EnriqueGalarza Torres EstherGarcía Sánchez José LuisGómez Jasso Raúl Ángel |

Investigar e implementar los métodos de ordenamiento y búsqueda en JAVA, medir tiempos de respuesta de cada uno de ellos. |

ContenidoMétodos de ordenamiento 2
Burbuja 2
Burbuja dimensional 2
Inserción 3
Casilleros 3
Arrays.sort 5
Collections.sort 5
Métodos de búsqueda 6
Búsqueda Lineal 6
Búsqueda Lineal Recursiva 7
Búsqueda Binaria 8
Bibliografía 11

Métodos de ordenamiento
Burbuja
El Ordenamiento de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento dela lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas"burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.
public static int[] OrdenarBurbuja(int[] n){
int temp;
int t = n.length;
for (int i = 1; i < t; i++) {
for (int k = t- 1; k >= i; k--) {if(n[k] < n[k-1]){
temp = n[k];
n[k] = n[k-1];
n[k-1]= temp;
}
}
}
return n;
}
Burbuja dimensional
El ordenamiento de burbuja bidireccional (cocktail sort en inglés) es un algoritmo de ordenamiento que surge como una mejora del algoritmo ordenamiento de burbuja.
La manera detrabajar de este algoritmo es ir ordenando al mismo tiempo por los dos extremos del vector. De manera que tras la primera iteración, tanto el menor como el mayor elemento estarán en sus posiciones finales. De esta manera se reduce el número de comparaciones aunque la complejidad del algoritmo sigue siendo O(n²).
A continuación se muestra el código java:
public class CocktailSort {public static int izquierda,derecha,ultimo; //variables para ordenamiento
public static int arreglo[] = {10,23,6,4,223,2,112,3,6,34}; // predefino arreglo

public static void main(String[] args) {

izquierda = 1;
derecha = arreglo.length;
ultimo = arreglo.length-1;

do{
for(int i=arreglo.length-1;i>0;i--){
//Burbuja hacia la izquierda//Los valores menores van a la izquierda
if(arreglo[i-1] > arreglo[i]){
int aux = arreglo[i]; // variable auxiliar para poder hacer intercambio de
arreglo[i] = arreglo[i-1]; // posicion
arreglo[i-1] = aux;
ultimo = i;
}
}
izquierda = ultimo+1;
for(intj=1;j<arreglo.length;j++){
if(arreglo[j-1] > arreglo[j]){
int aux = arreglo[j];
arreglo[j] = arreglo[j-1];
arreglo[j-1] = aux;
ultimo = j;
}
}
derecha = ultimo-1;
}while(derecha >= izquierda);

for(int i=0;i<arreglo.length;i++){
System.out.println(arreglo[i]);
}
}Inserción
El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos...