• Author / Uploaded
• anon-126312

• Categories
• Matemática discreta
• Ciencias de la computación teórica
• Conceptos matemáticos
• Algoritmos y estructuras de datos
• Áreas de la informática

Citation preview

BURBUJA MEJORADA Una nueva version del metodo de la burbuja seria limitando el numero de comparaciones, dijimos que era inutil que se compare consigo misma. Si tenemos una lista de 10.000 elementos, entonces son 10.000 comparaciones que estan sobrando. Imaginemos si tenemos 1.000.000 de elementos. El metodo seria mucho mas optimo con “n” comparaciones menos (n = total de elementos).

4 – INSERCION Y SELECCION Bueno veamos como funciona el algoritmo de Selección: 1. Necesitamos recorrer cada uno de los elementos del vector (si tenemos 10 elementos, nuestro ciclo girará 10 veces) y por cada vuelta necesitamos hacer lo siguiente: o Buscamos el menor numero, comenzando en la posición actual del ciclo exterior + 1 hasta terminar el vector. o Una vez que encontramos el numero menor, lo intercambiamos con el numero que este dentro del vector en la posición de la vuelta externa (es decir, que si por ejemplo es la vuelta #3, entonces intercambiaremos vector[3] por la variable "minimo" ) o Si no se encontró un numero menor, entonces no sucede nada 2. Hacemos esto hasta que el ciclo externo recorra todas las posiciones del vector

Y bueno aquí esta una imagen para que te des idea visual de como funciona:

Y también te dejo el algoritmo "codificado" para que veas más o menos lo que necesitas hacer: para i=1 hasta n-1 minimo = i; para j=i+1 hasta n si lista[j] < lista[minimo] entonces minimo = j /* (!) */ fin si fin para intercambiar(lista[i], lista[minimo]) fin para

Insercion(int matrix[]) { int i, temp, j; for (i = 1; i < matrix.length; i++) { temp = matrix[i]; j = i - 1; while ( (matrix[j] > temp) && (j >= 0) ) { matrix[j + 1] = matrix[j]; j--;

} matrix[j + 1] = temp; } } Seleccion(int[]matrix) { int i, j, k, p, buffer, limit = matrix.length-1; for(k = 0; k < limit; k++) { p = k; for(i = k+1; i pivot) { to--; } if(from