Informe De To Y Busqueda

Métodos de

Orden

y

Búsqueda

Por Felipe Llancaleo P.

Licenciatura en ciencia de la computación Año 2008

Profesores: Rosa Barrera

C.

Igor

Caracci

M.

Alfonso Lobos

B.

Índice: Introducción……………………………………………………………….3

Métodos de ordenamiento: Burbuja(Bubblesort)……………………………………………………. 4 Inserción(Insertion sort)……………………………………………… 7 Selección(Selection sort)…………………………………………….. 10 Rápida(Quick sort)………………………………………………………. 13 Shell……………………………………………………………………………… 15

Tabla comparativa………………………………………………………… 18

Métodos de búsqueda: Secuencial……………………………………………………………………. 19 Binaria…………………………………………………………………………. 21 Binaria recursiva…………………………………………………………. 23

Tabla comparativa………………………………………………….. 24

Biblografía………………………………………………………………….. 25

2

Introducción:

A continuación se presentan métodos de ordenamiento y búsqueda, los cuales sirven para administrar de una manera eficiente datos numéricos, de carácter, o alfanuméricos.

En el mundo actual, el procesamiento de datos es fundamental, ya que información nueva se crea todos los días, como por ejemplo nacimientos (Rut), facturas de una empresa(rol), numeros telefónicos, encuestas ,etc. y el manejo de estos datos de manera ordenada ayuda a tener una estructura en lo que se desee utilizar aquellos datos.

El ordenamiento se refiere a ordenar un arreglo de manera lógica, es decir mayor a menor o menor a mayor; los métodos que se exponen son básicos en el lenguaje de programación.

La búsqueda se refiere a la búsqueda de datos en específico, o sea, se verifica si en un arreglo existen aquellos datos.

3

Métodos de ordenamiento: Métodos directos: Burbuja(Bubble sort): El algoritmo lo que hace es revisar un par de elementos y evaluar cuál es mayor, intercambiándose de posición si el número en la posición anterior es mayor al que le prosigue. 4-3
3-4 Se inicia el proceso con el primer y segundo elemento, luego el segundo elemento con el tercero y así sucesivamente, hasta dejar el mayor elemento en la última posición del arreglo. Luego realiza el mismo procedimiento hasta igualar la cantidad de elementos existentes en el arreglo. Funcionamiento del algoritmo

Evalúa en n-1(n largo arreglo) iteraciones los valores del arreglo en a[i] y a[i+1], i inicializado en 0, y sumando una unidad por cada vuelta, ordenándolos si a[i]>a[i+1], sino los deja en la misma posición, así hasta llegar a la posición n-1, donde queda el mayor elemento del arreglo, cumpliéndose la primera iteración. Se le llama burbuja por la homología con el comportamiento de las burbujas, en por ser más livianas que el medio en que están(agua, aire) tienden a subir, en este caso subiría una burbuja(la mayor, que queda en la posición n-1) por cada iteración. Ejemplo de la 1era vuelta:

4

En el ejemplo de la 1era vuelta se encuentran en verde los elementos analizados por el algoritmo, ordenándolos. Este proceso se repite hasta que los elementos ya están ordenados. Ejemplo de la 2da vuelta:

Ejemplo de la 3ra vuelta:

En esta pasada ya queda ordenado el arreglo por lo que no es necesario seguir haciendo comparaciones lo que se evita con el interruptor. Seudocódigo

Inicio (arreglo a, n(largo) ) { pasada=0; //se inicializa el numero de pasadas en 0. mientras( pasada
// El índice ji se inicializa en 0.

mientras(ji a[ji+1]) //si el primer número es mayor que el segundo { interruptor=1; //se asigna 1 a interruptor . aux=a[ji];

//auxiliar igual al primer número.

5

a[ji]=a[ji+1]; //primer numero igual al segundo. a[ji+1]=aux; //segundo número igual al auxilar. } ji +1;

// se le suma una unidad al índice ji.

} pasada + 1 ; //se le suma una unidad a pasada. } }

En este caso en el pseudocódigo, se usa una variable llamada “interruptor” el cual tiene entrega un valor de verdad(0=F, 1=V), para evitar comprobaciones innecesarias. Este comprueba si se ha producido algún intercambio, si no, significa que el arreglo está ordenado, así logrando optimizar el algoritmo mediante menos pasadas. Ventajas Fácil implementación. Rápido en algoritmos de menor tamaño. Si se optimiza con el “interruptor” y el arreglo está ordenado tiene una complejidad de 0(n). Uso de poca memoria.

Desventajas Lento en arreglos de mayor tamaño por el número de comparaciones e intercambios.

6

Inserción(Insertion Sort): Este método lo que realiza es analizar cada elemento y comprobar si su inferior es mayor, desplazando la los elementos anteriores hasta que deje de encontrar un número mayor al número evaluado o haya llegado a la primera posición del arreglo.

1-3-4-5-2 analizando el 2 queda
1-2-3-4-5 Recorre el arreglo en n pasadas desde a[1] hasta llegar al a[n-1] elemento. Usa dos índices (i,j) para sus dos ciclos, el primer ciclo con el índice i va subiendo de posición en el arreglo, y en el segundo ciclo con el índice j va comprobando elementos anteriores hasta llegar al elemento que es menor que el analizado o al inicio del arreglo para ponerlo en su nueva posición. Este proceso también se puede realizar de forma inversa partiendo desde el penúltimo elemento y analizando si su superior es menor.

Ejemplo de la 1era vuelta:

Ejemplo de la 2da vuelta:

En esta vuelta no tiene intercambios porque 8 es mayor que los números antecesores a su posición. 7

Ejemplo de la 3ra y 4ta vuelta:

En la tercera vuelta el índice está en el número 2. Al hacer intercambios el número queda en el inicio del arreglo desplazando posiciones hacia la derecha. Sucede lo mismo en la siguiente vuelta quedando ordenado el arreglo.

Seudocódigo

Inicio (arreglo a, n(largo) ) { // índice i se inicia en la posición dos. i=1; //Ciclo principal: hasta que llegue al elemento a[n-1]. mientras(i0 y aux < que su uno inferior mientras(j>0 y aux< a[j-1]) {

//a[j] se iguala a su inferior. a[j]=a[j-1]; //se reduce j en una unidad. j-1;

}

8

// se posiciona correctamente a[i]. a[j]=aux; //se aumenta i en una unidad. i+1; }

}

Ventajas Fácil implementación. Rápido en algoritmos de menor tamaño. Uso de poca memoria.

Desventajas Lento en arreglos de mayor tamaño por el número de comparaciones e intercambios.

9

Por Selección(Selection Sort): Este algoritmo reconoce en cada iteración el menor de los elementos y lo pone al inicio del arreglo, en la siguiente iteración se realiza el mismo proceso dejando el segundo elemento menor en la segunda posición hasta llegar a la última posición. Ejemplo de la 1era vuelta:

En esta primera vuelta se analiza el primer elemento del arreglo, el cual debe ser el menor, por lo que va comparando a[0] con los siguientes, ordenándolos. Como llega al final del arreglo se determina que en la posición a[0] queda el menor elemento.

Ejemplo de la 2da vuelta:

Al igual que en la 1era vuelta se realiza el mismo procedimiento pero ahora desde la posición 1, asignando el segundo menor elemento a a[2].

10

Ejemplo de la 3ra vuelta:

Luego de estas iteraciones el arreglo queda ordenado en la cuarta vuelta.

Seudocódigo

Inicio (arreglo a, n(largo) ) { // índice i se inicializa en cero. i=0; //hasta que i llegue a n-2. mientras(i
// índice j se iguala a i más una unidad. j=i+1; // hasta que j llegue hasta n-1. mientras(j
//si el inferior es mayor que el superior elemento. si (a[i]>a[j]) { //a[i] se guarda en un auxiliar. aux=a[i]; // el inferior se pone en la posición del superior. a[i]=a[j]; // se reemplaza el superior por el inferior. a[j]=aux; }

j+1; //se suma una unidad al índice j. } i+1;//se suma una unidad al índice i. }

}

11

Ventajas Fácil implementación. No requiere memoria adicional. Realiza pocos intercambios. Desventajas: Lento. Realiza numerosas comparaciones. Poca diferencia entre el peor y el mejor caso.

12

Métodos Indirectos o Avanzados: Rápida(Quicksort): Se elige un elemento del arreglo, puede ser cualquiera, se ubican los elementos restantes al lado derecho e izquierdo, mayores(der) y menores(izq) que el elemento, respectivamente. Luego se separan en 2 arreglos, se realiza el mismo proceso recursivamente para der e izq, mientras tengan un largo mayor a 1.

Esquema gráfico

Ejemplo de la 1era vuelta: i

j

i

j

i

j

En este ejemplo se toma a n/2 como pivote y se van ordenando el arreglo de acuerdo a él, de tal manera que los menores queden a la izquierda de pivote, y sus

13

mayores a la derecha de él. Al terminar se obtienen la sub lista izquierda y la sub lista derecha. Seudocódigo Inicio quicksort(arreglo, primero, ultimo) { // se establece la primera posición. Primero =0; // se establece la última posición. ultimo =n-1; // se establece la posición central. central = (primero + ultimo)/2; //se sitúa el pivote en el centro. pivote = a[central]; // índice i se sitúa en el inicio del arreglo. i = primero; // índice i se sitúa en el término del arreglo. j = ultimo; //hasta que i sea mayor que j, o sea, hasta que pasen al pivote los índices. mientras (i <= j) {//hasta un elemento mayor o igual que pivote que va //a sub lista derecha. mientras (a[i] < pivote) // se aumenta en una unidad i. i+1; //hasta un elemento menor o igual que pivote //a sub lista izquierda. mientras (a[j] > pivote) // se disminuye en una unidad j. j-1; // si i es menor o igual que j si (i<=j) {//a[i] se copia a un auxiliar. aux = a[i]; //a[i] se iguala a a[j]. a[i] = a[j]; //a[j] se iguala a a[i]. a[j] = aux; //aumenta i en una unidad. i+1; //disminuye j en una unidad. j-1; } } //si primero es menor que j, envía lista izquierda si (primero < j) quicksort(a, primero, j);. //si último es mayor que i, envía lista derecha. si (i < ultimo) quicksort(a, i, ultimo); }

14

Ventajas : Trabaja más rápido con arreglos grandes. Desventajas: Mayor complejidad en implementación. Es recursivo lo que le hace consumir mayor memoria. El desempeño es n^2 en su peor caso.

Shell: Es una mejora del método de inserción directa, utilizado cuando el array tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial es n/2 (siendo n el número de elementos, y siendo división entera). Se van dando pasadas hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto tenga valor 1, lo que equivaldría a comparar por el método de inserción, pero sin realizar tantas comparaciones porque el arreglo estaría mediamente ordenado.

Ejemplo de la 1ra vuelta:

En este ejemplo el salto equivale a 2(5/2=2.5) por lo que analiza un elemento por medio ordenándolos.

15

Ejemplo de la 2da vuelta:

En la segunda vuelta el salto se divide por 2 quedando igual a 1, por lo que se analiza de igual manera que la inserción directa, anteriores

o sea

viendo los elementos

y desplazando posiciones hasta poner en correcta posición los

elementos. Seudocódigo

Inicio ShellSort(arreglo a, n(largo arreglo)) { //se inicializa el salto en la mitad del largo del arreglo. salto = n / 2; //hasta que salto sea igual a uno.(llega a revisar por inserción directa) mientras (salto >= 1) {// índice i se iguala a salto. i=salto; //hasta que i llegue a n-1. //hasta que analice todos los elementos usando el salto. mientras(i= 0 y a[j] > aux) {//a[j+salto] se iguala a a[j]. a[j + salto] = a[j]; // a índice j se le resta salto. j= j- salto; } //se instala en correcta posición el elemento guardado en aux. a[j + salto] = aux; //se suma una unidad a i.

16

i=i+1; } //se disminuye el salto, dividiéndolo en dos. salto = salto/2; } }

Para mejorar el algoritmo existe una fórmula que es en vez de tener un salto “constante” es usar una secuencia de números siempre y cuando termine en 1, asegurando el análisis elemento a elemento. Una secuencia conocida es la de Robert Sedgewick : {1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1}. Aquí se muestra una tabla de diferencia usando la secuencia de Sedgewick y el método original de salto.

Tamaño

Intercambios Shell Intercambios Sedgewick

1000

8800

7500

5000

61000

53000

10000

150000

120000

30000

520000

460000

100000

2700000

1700000

500000

18 millones

9 millones

1 millón

44 millones

17 millones

5 millones 270 millones

99 millones

10 millones 640 millones

220 millones

Ventajas: Posee complejidad O(n2) pudiendo llegar en el mejor de los casos al orden de O(n). Desventajas: Mayor complejidad de implementación. Realiza demasiadas comparaciones, a medida que crece el número de elementos crece también el tiempo de ejecución.

17

Ejemplo de procesamiento de datos Probando los métodos con un número de 1710 datos. Este arreglo de 1710 datos fue creado a partir de 123 números: los primeros 100 numeros naturales, disminuyendo desde 100 hasta 1, los 23 restantes números aleatorios, luego solo se copió la misma lista repitiendola para crear un arreglo de numero mayor y así evaluar de mejor manera el desempeño de cada método. Método Tiempo

Burbuja 0.203 s

Inserción 0.3755s

Selección 0.187s

Quicksort 0.218s

Shell 0.187s

Tipo de método y características

Método

Burbuja

Inserción

Selección

Comprobaciones

n(n-1)/2 O(n2) 1 auxiliar 2 índices si

n(n+1) O(n2) 1 auxiliar 2 índices si

n(n-1)/2 O(n2) 1 auxiliar 2 índices no

Complejidad Variables creadas Estabilidad

Quicksort depende

O(n log2(n)) 3 variables 2 índices no

Shell

O(n2) O(n2) 2 variables 2 índices no

O()=Notación de Landau, también llamada "o minúscula" y "O mayúscula", es una notación para la comparación asintótica de funciones, lo que permite establecer la cota inferior asintótica, la cota superior asintótica y la cota ajustada asintótica O(1) : Complejidad constante. O(n2) : Complejidad cuadrática. O(n log(n)) : Complejidad logarítmica.

18

Métodos de Búsqueda:

Búsqueda secuencial o Lineal:

La búsqueda secuencial busca un elemento de una lista utilizando un valor destino llamado clave. En una búsqueda secuencial, los elementos de una lista o vector se exploran (se examinan) en secuencia, uno después de otro. El algoritmo de búsqueda secuencial compara cada elemento del array con la clave de búsqueda. Dado que el array no está en un orden prefijado, es probable que el elemento a buscar pueda ser el primer elemento, el último elemento o cualquier otro. De promedio, al menos el programa tendrá que comparar la clave de búsqueda con la mitad de los elementos del array. El método de búsqueda lineal funcionará bien con arrays pequeños o no ordenados, al terminar el algoritmo devuelve el índice de la posición donde encontró la clave.

Ejemplo 1

En este ejemplo el elemento a buscar es el 3, se recorre el arreglo desde su inicio hasta su fin unitariamente, verificando cada elemento del conjunto. Lo encuentra en la última posición por lo que retorna el valor 4, que es el índice de posición del número 3 en el arreglo.

19

Ejemplo 2

En este segundo ejemplo también se recorre de la misma manera el arreglo, pero en este caso el elemento buscado no se encuentra por lo que se retorna un valor de -1, que no existe en las posiciones del arreglo. Si se utilizara el índice del arreglo para evitar usar -1 y caer en equivocaciones habría que utilizar una condición como: si(índice mayor o igual que cero) realizar acción;

Seudocódigo Inicio ( arreglo a, clave, n(largo arreglo) ) {//índice i se inicializa en cero. i=0; //hasta que i llegue a n-1 y que recorra todo el arreglo mientras (i < n) {// arreglo[i] es igual a clave si (a[i] = clave) //retorna índice i, posición donde encontró la clave. retorna i; //se suma una unidad a i. i+1; } Sino //resultado se iguala a -1. resultado=-1;

20

retorna resultado;

//retorna -1

}

Ventajas: Utilizarlo en arreglos desordenados u ordenados, ya que puede recorrer todo el arreglo. Desventajas: Su uso en arreglos de gran tamaño, ya que el elemento puede estar al final del arreglo.

Búsqueda Binaria: La búsqueda binaria se aplica a una lista ordenada. Se tiene una variable mitad, la que sirve para ver si es mayor o menor que el elemento que se busca, si es menor se buscan en elementos de la derecha del arreglo, si es mayor se busca en los menores, luego mitad pasa a ser la posición de este nuevo “miniarreglo” hasta que encuentre o no la clave. En general, si los datos de la lista están ordenados se puede utilizar esa información para acortar el tiempo de búsqueda. Utiliza un método similar al del algoritmo quick sort, sin usar recursividad, ya que va “dividiendo” el arreglo, haciendo más práctico su desempeño.

Ejemplo 1

En este caso del arreglo como el largo es 5, el elemento central es 2, y como no es el número buscado (5) verifica si es mayor o menor, como es mayor sigue buscando hacia la derecha, luego analiza el sub arreglo 4 y 5 hasta encontrar el elemento y retornar el valor 4.

21

Ejemplo 2

El caso contrario en el ejemplo dos donde no encuentra la clave, pero realiza el mismo procedimiento, pero al no encontrar el elemento buscado retorna un valor igual a -1. Al igual que la búsqueda lineal para utilizar el valor de retorno se tiene que utilizar una condición.

Seudocódigo Inicio SearchBinaria(arreglo a, n(largo arreglo), clave) {//se asigna a primero la posición cero. primero = 0; //se asigna a último la posición n-1. último = n-1; //hasta que primero sea mayor que último. mientras (primero <= último) { central = (primero + último)/2 // valorCentral=elemento central del arreglo. valorCentral = lista[central]; //si clave es igual a vC. // retorna ìndice central si (clave = valorCentral) return central;

.

//sino si clave es menor que elemento central se analiza los elementos de la //derecha. sino si(clave < valorCentral) //último = central menos una unidad. último = central -1; sino //se analizan los elementos de la izquierda primero= central + 1; // sino primero =central más una unidad.

a

} retorna -1; }

22

Ventajas: En un arreglo ordenado se realiza una búsqueda más rápida, disminuyendo en más o menos la mitad de comparaciones que si fuera buscando elemento a elemento. Fácil implementación. Desventaja: Su uso en un arreglo desordenado se hace imposible.

Búsqueda Binaria recursiva Este algoritmo realiza los mismos pasos de la búsqueda binaria, pero recursivamente como quicksort. BusquedaBin (arreglo a, clave, izqda, dcha) { if(dchaa[centro]) return(BusquedaBin(a,clave,centro+1,dcha)); else return(centro); } }

Ventajas: Uso en arreglos grandes. Rapidez de búsqueda. Fácil implementación. Desventajas: Uso solo en arreglos ordenados o semiordenados. Uso de memoria por la recursividad.

23

Método Complejidad Variables creadas

Lineal

Binario

Binario Recursivo

O(n2) 1 índice

O(log n) 3 variables

O(log n) 1 auxiliar

24

Bibliografía y referencias http://www.algoritmia.net/articles.php?id=31 http://c.conclase.net/orden/index.html http://profesores.elo.utfsm.cl/~agv/elo320/01and02/index1s02.html http://dei.inf.uc3m.es/docencia/p_s_ciclo/ada/web/ejercicios/tema7.pdf http://elvex.ugr.es/decsai/java/pdf/6B-Sort.pdf http://www.cimat.mx:88/~jbhayet/CLASES/PROGRAMACION/clase23.pdf http://www.estudiando.cedetec.cl/ACOD/consolaRecursosEducativos/conRec_cargaRecur so.php?idRecurso=13 http://www.estudiando.cedetec.cl/ACOD/consolaRecursosEducativos/conRec_cargaRecur so.php?idRecurso=14 http://latecladeescape.com/w0/con-nombre-propio/ordenacion-por-el-metodo-de-shellshellsort.html Programación en c++ -Luis Joyanes Aguilar Edición Mc Graw Hill

25