Metodos de busqueda y ordenacion

Métodos de búsqueda y ordenación | 4 de noviembre
2011
|
ALUMNO : MORENO REYES , ROBERT | LENGUAJE DE PROGRAMACION I |
UNIVERSIDAD NACIONAL
TECNOLÓGICA
Del cono sur de lima

INGENIERIA DE SISTEMAS

MÉTODOS DE BÚSQUEDA Y ORDENACIÓN

Métodos de Ordenamiento: * Ordenación por inserciónEL ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenarpara 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 ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndosecuando 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.-------------------------------------------------
-------------------------------------------------
Ejemplo de funcionamiento--------------------------------------------------------------------------------------------------
En el siguiente ejemplo, 32 debe ser insertado entre 26 y 47, y por lo tanto 47, 59 y 96 deben ser desplazados.-------------------------------------------------
k+1-------------------------------------------------
11 26 47 59 96 32 -------------------------------------------------
11 26 47 59 96-------------------------------------------------
11 2632 47 59 96En la implementación computacional, el elemento k+1 va comparándose de atrás para adelante, deteniéndose con el primer elemento menor. Simultáneamente se van haciendo los desplazamientos.-------------------------------------------------
11 26 47 59 96 32-------------------------------------------------
11 26 47 59 96-------------------------------------------------
11 26 47 5996-------------------------------------------------
11 26 47 59 96-------------------------------------------------
11 26 32 47 59 96Código en Javapublic static void insertSort (int[] v) { int aux; int j; for (int i=1; i<v.length; i++) { j=i; aux = v[i]; for (j=i-1; j>=0 && v[j]>aux; j--){ v[j+1] = v[j]; v[j] = aux;} } } * Ordenamiento de BurbujaLa Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la 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 significaque 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.//Ordenamiento porBurbuja 
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;}//fin if
}// fin 2 for
}//fin 1 for
return n;
}//fin |
Métodos de Búsqueda.

La recuperación de información es una de las aplicacionesmás importantes de las computadoras. La búsqueda de información está relacionada con las tablas para consultas. Estas tablas contienen una cantidad de información que se almacenan en forma de listas de parejas de datos. Por ejemplo un catálogo con una lista de libros de matemáticas, en donde es necesario buscar con frecuencia elementos en una lista. Existen diferentes tipos de búsqueda, pero en...