Capitulo III Ordenamiento y Busqueda

Ordenamiento y Búsqueda

Giannina Costa Lizama

OrdenamientoOrdenamiento

Ordenar es colocar información de una forma especial basados en un criterio (menor a mayor o mayor a menor).

Los métodos de ordenamiento cumplen un rol en si mismo o sirven como parte de otros procedimientos mas complejos.

La función que cumplen los métodos de ordenamiento es facilitar la búsqueda de información.

OrdenamientoOrdenamiento

¿Cuándo es conveniente usar un método de ordenamiento?

Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.

Criterios de OrdenamientoCriterios de Ordenamiento

Estabilidad : Comportamiento de registro con

claves iguales. Se debe mantener el orden relativo.

Requerimientos de Memoria:Cuando se requiere de

memoria adicional para realizar su labor (variables).


Tiempo de Ejecución:No tiene que ver con la dificultad

sino con el rendimiento.Se debe determinar cuantas veces el algoritmo necesita comparar.

Las complejidades mas comunes son:O(1): Complejidad constanteO(n2): Complejidad CuadráticaO(nlog(n)): Complejidad Logarítmica

Cada algoritmo se comporta de forma diferente dependiendo de la información que contenga.


•Eficiencia en el tiempo de ejecución:Se mide por el

numero de comparaciones e intercambios que se deben realizar.

Ejemplo: Siendo n numero de elementos a ordenar. Se dice que el algoritmo es de O(n2), cuando compara n veces los n elementos (n*n=n2)

Tipos de OrdenamientosTipos de Ordenamientos Ordenamientos Internos:

Son aquellos en los cuales los valores a ordenar están en memoria principal (ram). El tiempo que se requiere para acceder a cualquier elemento es el mismo. Almacena temporalmente datos como programas que la cpu esta procesando.

Ordenamientos Externos

Son aquellos en los que los valores a ordenar están en memoria secuendaria (disco duro, cinta): El tiempo que se requiere para acceder a cualquier elemento depende de la ultima posición accezada.

Algoritmos de OrdenamientoAlgoritmos de OrdenamientoAlgoritmo de ordenamiento Internos Selección

InserciónDirectaBinaria

IntercambioBurbujaQuicksort

Mezcla

Algoritmo de ordenamiento ExternosNatural Merging Straight Merging

Algoritmo de Ordenamiento Algoritmo de Ordenamiento InternoInterno

1.- Algoritmo de Selección:

Consiste en encontrar el menor de todos los elementos de la lista e intercambiarlo con el que esta en la primera posición.

Luego el segundo mas pequeño y así en forma sucesiva hasta ordenar toda la lista.

Es la selección repetitiva de la clave menor restante en una lista de datos no ordenados.

Algoritmo de Algoritmo de Ordenamiento InternoOrdenamiento Interno1.- Algoritmo de Selección:Es un algoritmo lento

No obstante ya que solo realiza un intercambio en cada ejecución del ciclo externo, puede ser una buena opción para listas con registros grandes y claves pequeñas.

Ejemplo:

4 - 3 - 5 - 2 - 1 1 - 3 - 5 - 2 - 4 1 - 2 - 5 - 3 - 4 1 - 2 - 3 - 5 - 4 1 - 2 - 3 - 4 - 5

Algoritmo de Ordenamiento InternoAlgoritmo de Ordenamiento Interno1.- Algoritmo de Selección

1.Buscar elemento mas pequeño de la lista

2.-Intercambiar este elemento con el elemento ubicado en la primera posición de la lista.

3.-Buscar el segundo mas pequeño de la lista

4.-Intercambiar este elemento con el elemento que ocupa la segunda posición dentro de la lista

5.-Repetir este proceso hasta ordenar toda la lista

Algoritmo de Ordenamiento InternoAlgoritmo de Ordenamiento Interno1.- Algoritmo de Selección

Estabilidad: No es estable, ya que puede que el orden

adyacentede los datos se pierda

Requerimiento de memoria: Solo necesita una variable

adicionalpara realizar los intercambios. No requiere memoria adicional.

Tiempo de ejecución: La complejidad es O(n2).

Este algoritmo presenta un comportamiento constante independiente

del orden de los datos.

Algoritmo de Algoritmo de Ordenamiento InternoOrdenamiento Interno

Ventajas

Fácil implementación No requiere memoria adicionalRealiza pocos intercambios (n)Rendimiento constante. Existe poca diferencia entre el mejor y el peor caso.

Desventajas

LentoRealiza numerosas comparaciones

1.- Algoritmo de Selección

2.- Algoritmo de Inserción2.- Algoritmo de InserciónMétodo similar al utilizado cuando se ordenan las cartas de

una baraja.

Se tiene el primer elemento y este es comparado con el segundo, si es mayor queda ubicado a la derecha (mantiene su posición), si es menor se copia el contenido de este elemento en una variable temporal, el primer elemento se copia en la posición que ocupaba este y luego el segundo elemento que se encuentra en una variable temporal es insertado en la primera posición.

Algoritmo de Ordenamiento Interno

2.- Algoritmo de Inserción2.- Algoritmo de InserciónEjemplo:

4 - 3 - 5 - 2 - 1 4 - 4 - 5 - 2 - 1 3 - 4 - 5 - 2 - 1 3 - 4 - 5 - 5 - 1 3 - 4 - 4 - 5 - 1 3 - 3 - 4 - 5 - 1 2 - 3 - 4 - 5 - 1 2 - 3 - 4 - 5 - 5 2 - 3 - 4 - 4 - 5 2 - 3 - 3 - 4 - 5 2 - 2 - 3 - 4 - 5 1 - 2 - 3 - 4 - 5


Comparar 4 con 3 .3 es menor que 4, se desplaza una posición a la derecha y se copia el 3. Variable=3

Comparar 5 con 4 como es mayor que 4 queda igual.

Comparar 2 con 5. 2 es menor que 5, se desplaza una posición a la derecha y se continua comparando con 4, luego con 3. variable=2.

2.- Algoritmo de Inserción2.- Algoritmo de Inserción

Estabilidad:

Este algoritmo nunca intercambia registros con claves iguales. Por lo tanto es estable.

Requerimiento de memoria:

Una variable adicional para realizar los intercambios.

Tiempo de ejecución: La complejidad es O(n2).


2.- Algoritmo de Inserción2.- Algoritmo de Inserción

Ventajas

Fácil implementación Requerimiento mínimos de memoria

Desventajas

LentoRealiza numerosas comparaciones


3.- Algoritmo de Intercambio3.- Algoritmo de Intercambio

La idea de los algoritmos de intercambio es la de comparar pares de valores (claves) e intercambiarlos sino están en sus posiciones relativas correctas.

Los algoritmos veremos dos algoritmos:

burbuja quicksort


3.1.- Algoritmo de Intercambio Burbuja3.1.- Algoritmo de Intercambio Burbuja

Es el algoritmo mas sencillo, pues consiste en realizar ciclos repetidamente a través de la lista, comparando los elementos adyacentes de dos en dos.

Si un elemento es mayor que el que esta en la siguiente posiciónse intercambia.



Ejemplo:

4 - 3 - 5 - 2 - 1 3 - 4 - 5 - 2 - 1 3 - 4 - 2 - 5 - 1 3 - 4 - 2 - 1 - 5

3 - 2 - 1 - 4 - 5 2 - 1 - 3 - 4 - 5 1 - 2 - 3 - 4 - 5


Se comienza comparando el 2do con el 1ero 4 es mayor que 3 se intercambia.Luego se continua con el 5 que queda idemLuego el 2 se cambia con 5Luego se compara 5 con 1 y se intercambia


Estabilidad: Este algoritmo nunca intercambia registro con claves iguales, por lo tanto es un algoritmo estable.

Requerimiento de memoria:Requiere de una variable adicional para realizar intercambios.

Tiempo de ejecución: Su tiempo es de O(n2)


3.1.- Algoritmo de Intercambio Burbuja3.1.- Algoritmo de Intercambio BurbujaVentajas

Fácil implementación No requiere memoria adicional

Desventajas

Muy LentoRealiza numerosas comparaciones Realiza numerosos intercambios


3.2.- Algoritmo de Intercambio Quicksort3.2.- Algoritmo de Intercambio QuicksortConocido también como ordenamiento por partición o intercambio.

El método de ordenación QUICKSORT es actualmente el más eficiente y veloz de los métodos de ordenación interna.

Es también conocido con el nombre de método rápido y de ordenación por partición.

Este método es una mejora sustancial del método de Intercambio directo y recibe el nombre de QUICKSORT (rápido) por la velocidad con que ordena los elementos del arreglo.


Este algoritmo se basa en el principio “dividir para vencer”.

La idea principal de este algoritmo es dividir el arreglo en dos sub arreglos.

La primera parte de los elementos deben ser menores que el pivote.

La segunda parte de los elementos deben ser mayores que el pivote.

3.2.- Algoritmo de Intercambio Quicksort


Idea para ordenar:Idea para ordenar:

Se pasan los elementos mayores a la derecha y los menores a la izquierda (intercambiando un menor por una mayor).

Se repite la operación para cada lado del pivote.

Esta operación se realiza hasta que los punteros se “crucen”.



Ejemplo:Ejemplo:

65 70 50 85 55 50 45 90

Se elige como pivote álazar el primer elemento del arreglo, en este caso 65



Busca entonces el primer elemento mayor al pivote, en este Busca entonces el primer elemento mayor al pivote, en este caso 70.caso 70.El mismo tiempo se busca el último elemento no mayor que el El mismo tiempo se busca el último elemento no mayor que el pivote, en este caso 45pivote, en este caso 45

65 70 50 85 55 50 45 90

Entonces se intercambian

65 45 50 85 55 50 70 90



Se vuelve a explorar en ambas direcciones, siempre Se vuelve a explorar en ambas direcciones, siempre comparando los elementos con el pivote.comparando los elementos con el pivote.

65 45 50 85 55 50 70 90

Entonces se intercambian

65 45 50 50 55 85 70 90



Se vuelve a explorar en ambas direcciones, pero en este caso Se vuelve a explorar en ambas direcciones, pero en este caso se intercambian los punteros.se intercambian los punteros.

65 45 50 50 55 85 70 90

Entonces ya no se intercambian los elementos, en ese caso se intercambia el pivote con el elemento menor.

55 45 50 50 65 85 70 90



La primera partición ya está lista. Entonces se ordenan La primera partición ya está lista. Entonces se ordenan recursivamente los sub vectores con el mismo método.recursivamente los sub vectores con el mismo método.

Se debe entonces para cada sub vector elegir un nuevo pivote y ordenar.

55 45 50 50 65 85 70 90



4.- Ordenación por mezclas4.- Ordenación por mezclas• Existen dos métodos conocidos de mezclas :

1. El primero permite combinar dos vectores ordenados de r y s elementos en un único vector ordenado de tamaño n + s, al que se le denomina Mezcla.Una de las formas más fáciles de ordenar es concatenar ambos vectores y luego utilizar algún algoritmo para su ordenación. Es importante señalar que no siempre los vectores utilizados tienen el mismo tamaño, lo que debe ser considerado al momento de acabar las comparaciones, porque todos los elementos que no se compararon deben de ingresarse al vector resultante.

PROCEDIMIENTO MEZCLAR(DAT,IZQP,IZQU,DERP,DERU)INICIO

IZQA <- IZQPDERA <- DERPIND <- IZQPMIENTRAS (IZQA <= IZQU) Y (DERA <= DERU) HAZ

SI ARREGLO[IZQA] < DAT[DERA] ENTONCESTEMPORAL[IND] <- ARREGLO[IZQA]IZQA <- IZQA + 1

EN CASO CONTRARIOTEMPORAL[IND] <- ARREGLO[DERA]DERA <- DERA + 1

IND <- IND +1MIENTRAS IZQA <= IZQU HAZ

TEMPORAL[IND] <- ARREGLO[IZQA]IZQA <- IZQA + 1IND <- IND +1

MIENTRAS DERA <= DERU HAZTEMPORAL[IND] <=DAT[DERA]DERA <- DERA + 1IND <- IND + 1

PARA IND <- IZQP HASTA DERU HAZARREGLO[IND] <- TEMPORAL[IND]

FIN

2. El segundo método es donde la idea central consiste en dividir en dos mitades el vector o la lista, cada una de ellas se ordena y luego se mezclan. Este procedimiento se repite recursivamente para cada sub-lista.

Procedure SortMezcla{

if i = j then return xi

else{

m=( i + j - 1 ) / 2return merge( SortMezcla(i,m),

SortMezcla(m+1,j) )}

}

PROCEDIMIENTO MEZCLAR( Dat, IZQP, IZQU, DERP, DERU )IZQA = IZQPDERA = DERPIND = IZQPMientras (IZQA <= IZQU) Y (DERA <= DERU) Hacer

Si Vector[ IZQA ] < Dat[ DERA ] EntoncesTemporal[ IND ] = Vector[ IZQA ]IZQA = IZQA + 1

En caso contrarioTemporal[ IND ] = Vector[ DERA ]DERA = DERA + 1IND = IND +1

FinsiFin MientrasMientras IZQA <= IZQU Hacer

Temporal[ IND ] = Vector[ IZQA ]IZQA = IZQA + 1IND = IND +1

Fin MientrasMientras DERA <= DERU Hacer

Temporal[ IND ] <= Dat[ DERA ]DERA = DERA + 1IND = IND + 1

Fin MientrasPara IND = IZQP Hasta DERU Hacer

Vector [ IND ] = Temporal[ IND ]

Es importante considerar al momento de elegir cualquiera de los algoritmos anteriores el volumen de datos con que se trabajará, es decir la cantidad de elementos, la memoria requerida para guardar dichos elementos y la estructura a utilizar (pila, árbol, cola, etc.)

La mayoría de estos factores tendrá una repercusión importante en la cantidad de comparaciones que se deban realizar para ordenar la estructura, y esto se traduce el en tiempo que demora dicho ordenamiento.

Algoritmo de Búsquedas

La búsqueda se refiere a la operación de encontrar la posición de un elemento entre un conjunto de elementos dados: lista, tabla o fichero.

Existen diferentes algoritmos de búsqueda.

El algoritmo elegido depende de la forma en que se encuentren organizados los datos.


La búsqueda por claves para localizar registros es, con frecuencia, una de las acciones que mayor consumo de tiempo conlleva, y por consiguiente el modo de los registros están dispuestos y la elección del modo utilizado para la búsqueda puede redundar en una diferencia sustancial en rendimiento del programa.


Todos los algoritmos de búsqueda tienen dos finalidades:

- Determinar si el elemento buscado se encuentra en el conjunto en el que se busca.- Si el elemento está en el conjunto, hallar la posición en la que se encuentra.


El problema de búsqueda puede ser de dos tipos:

Búsqueda externa: Esto es si existen muchos registros, puede ser necesario almacenarlos en archivos de disco o cinta, externo a la memoria de la computadora.

Búsqueda interna: En este caso los registros que se buscan se almacenan por completo dentro de la memoria de la computadora.


Los métodos más usuales de búsqueda son:

Búsqueda secuencial o lineal.Búsqueda binaria.Búsqueda por transformación de claves

(hash).

Búsqueda Secuencial

Supongamos una lista de elementos almacenados en un arreglo . El método más sencillo de buscar un elemento en una lista, es explorar secuencial mente la lista o, dicho en otras palabras, recorrer la lista desde el primer elemento al último. Si se encuentra el elemento buscado, se envía un mensaje similar a "Fin de búsqueda, elemento encontrado"; en caso contrario se envía un mensaje similar a "elemento no existe en la lista".


La búsqueda secuencial compara cada elemento de la lista con el valor deseado, hasta que esté encuentre o termina de leer la lista completa.La búsqueda secuencial no requiere ningún requisito por parte de la lista y, por consiguiente, no necesita estar ordenado. El recorrido la lista se realizará normalmente con estructuras repetitivas.


Pseudo código de búsqueda Secuencial

inicioleer(t)//recorrido de la listadesde i <-- 1 hasta n hacersi A [i] = t entoncesescribir (" Elemento encontrado ")escribir ("En posición", i)fin-sifin-desdefin

Algoritmo Búsqueda secuencial

for(i=j=0;i<N;i++) if(array[i]==elemento) { solucion[j]=i; j++; }


Este algoritmo se puede optimizar cuando el arreglo está ordenado, en cuyo caso la condición de salida cambiaría a:

for(i=j=0;array[i]<=elemento;i++)

o cuando sólo interesa conocer la primera ocurrencia del elemento en el array:

for(i=0;i<N;i++) if(array[i]==elemento) break;


Cuando sólo interesa la primera posición, se puede utilizar un centinela, esto es, dar a la posición siguiente al último elemento de array el valor del elemento, para estar segurode que se encuentra el elemento, y no tener que comprobara cada paso si seguimos buscando dentro de los límites del array:

array[N]=elemento;for(i=0;;i++) if(array[i]==elemento) break;Si al acabar el bucle, i vale N es que no se encontraba el elemento. El número medio de comparaciones que hay que hacer antes de encontrar el elemento buscado es de (N+1)/2.

Búsqueda Binaria

En una búsqueda secuencial se comienza con el primer elementodel arreglo o de la lista y se busca en el hasta que se encuentra el elemento deseado o se alcanza el final del vector. Aunque éste punto puede ser un método adecuado para pocos datos, se necesita una técnica más eficaz para conjuntos grandes de datos.

La búsqueda Binaria se utiliza en arreglos o listas ordenados yse basa en la constante división del espacio de búsqueda (recorrido en el arreglo o lista). Se comienza comparando el elemento que se busca, no con el primer elemento, sino con elemento central.

Búsqueda Binaria

Si el elemento buscado -t- es menor que el elemento central, entonces t deberá estar en la mitad izquierda o inferior del arreglo o lista.

Si es mayor que el valor central, deberá estar en la mitad derecha o superior, y si es igual al valor central, se habrá encontrado el elemento buscado.

El proceso de búsqueda debe terminar normalmente conociendosi la búsqueda ha tenido éxito ( se ha encontrado el elemento) obien no ha tenido éxito (no se ha encontrado el elemento) y normalmente se deberá devolver la posición del elemento buscado dentro del arreglo o lista.

Búsqueda Binaria

Ejemplo:Buscar el elemento 3 en el arreglo {1,2,3,4,5,6,7,8,9}

1.- Se toma el elemento central y se divide el array en dos:{1,2,3,4}-5-{6,7,8,9}

Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4}

2.-Se vuelve a dividir el array en dos:

{1}-2-{3,4}Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4}

3.- Se vuelve a dividir en dos:

{}-3-{4}Como el elemento buscado coincide con el central, lo hemos encontrado.Si al final de la búsqueda todavía no lo hemos encontrado, y el subarray a dividir está vacio {}, el elemento no se encuentra en el array.

Búsqueda Binaria

Algortimo Búsqueda_binaria inicioleer(k)//inicializar variablesbajo <-- 1alto <-- Ncentral <-- ent (bajo+alto)/2)mientras (bajo=< alto) y (x[central]<>k) hacersi k < x [central] entoncesalto <-- central -1si_nobajo <-- central +1fin_sicentral <-- ent ((bajo +alto) /2)fin_mientras

si k= x[central] entoncesescribir ("valor encontrado es ", central)si_noescribir ("valor no encontrado", central)si_noecribir ("valor no encontrado")fin_sifin

Búsqueda Binaria

En general, este método realiza log(2,N+1) comparaciones antes de encontrar el elemento, o antes de descubrir que no está. Este número es muy inferior que el necesario para la búsqueda lineal para casos grandes.Este método también se puede implementar de forma recursiva, siendo la función recursiva la que divide al array en dos más pequeños

2.2.- Búsqueda binaria en 2.2.- Búsqueda binaria en árbolesárboles• Para este método de búsqueda se utilizan siempre ejemplos de árboles binarios, ya que son los más fáciles de recorrer.

•Por lo general el árbol binario tiene sus elementos ordenados, entonces la búsqueda de un elemento determinado se realizará siempre por una rama de la raíz. Para este caso no existen elementos repetidos.

• En el caso de que el árbol no esté ordenado se deberá recorrerlo completamente hasta encontrar o no la información.

15 58

20 ~5

19 21

10 13

5 3~

6 84

2.2.- Búsqueda binaria en árboles

15 58

20 ~5

19 21 10 13

5 3~

6 84


PROCEDURE ABB( RAIZ, ELEM, POS)Si RAIZ = Null Entonces

POS = NullEn caso contrario

Si INFO( INFO ) = ELEM EntoncesPOS = RAIZ

En caso contrarioSi ELEM < INFO(RAIZ) Entonces

BUSCAR (IZQ( RAIZ ), ELEM, POS)

En caso contrarioBUSCAR (DER( RAIZ ), ELEM,

POS)Fin si

Fin siFin si


PROCEDURE BUSCAR (RAIZ, ELEM, POS)Si RAIZ = Null Entonces

POS = NullEn caso contrario

Si RAIZ*INFO = ELEM Entonces POS = RAIZ

En caso contrarioSi ELEM < RAIZ*INFO Entonces

BUSCAR( RAIZ*IZQ, ELEM, POS )

En caso contrarioBUSCAR (RAIZ*DER, ELEM,

POS)Fin si

Fin siFin si


Búsqueda de HashingBúsqueda de Hashing• Existen dos métodos de búsquedas de Hashing,

ambos son método especial que permite convertir una clave dada en otra para optimizar su uso aunque produce “colisiones”.

• Las colisiones ocurren cuando por errores del sistema dos claves corresponden al mismo índice. Entonces se deben elegir nuevas claves para evitar este tipo de errores.

1. El primero es un método matemático que se utiliza generalmente cuando el número de claves es muy grande comparado con el número real de registros que va a manejar un archivo. Para este caso existen distintas funciones o métodos a utilizar.

Matemáticamente se debe elegir una función de transformación. Para ello se debe considerar lo siguiente:

◦ La función debe de distribuir las claves de manera uniforme sobre el conjunto de direcciones posibles.

◦ La función debe de ser rápida.

◦ Debe evitar las colisiones (o minimizarlas).

◦ Su cálculo debe ser fácil.

Búsqueda de Hashing

• Supongamos que existe una tabla con 7.000 elementos y que tenga claves numéricas, entonces podemos utilizar los siguientes métodos para encontrar un índice adecuado:

– Método del centro de los cuadrados.

– Método de la división.

– Método de desplazamiento.

– Método de plegamiento.


1 Método del centro de los cuadrados1 Método del centro de los cuadrados

Se multiplica la clave por sí misma y se toman los dígitos centrales ajustándolo al rango.

Clave 172148cuadrado 29634933904

Dirección 3493

dígitos centrales


2 Método de la división2 Método de la división

• Se divide la clave por un número primo ligeramente inferior al tamaño de la tabla o por un número que contenga factores primos menores a 20.

• La dirección resultante es el resto de la división.


La tabla tiene 7000 elementos.

Clave 172148

172148 MOD 6997

Dirección 4220

4220


3 Método de Desplazamiento3 Método de DesplazamientoLos dígitos exteriores se suman con los centrales y esto permite la nueva dirección.

Clave 542422241

2422 + 241 +54 = 2717

Dirección 2717


4 Método de plegamiento4 Método de plegamientoSe eligen varias columnas arbitrariamente, y de forma análoga al caso anterior se realiza la suma.

Clave 542422241

2422 + 142 +45 = 2609

Dirección 2609


2. La idea principal de este tipo de método Hashing consiste en aplicar una función que traduce el valor del elemento buscado en un rango de direcciones relativas. Una desventaja importante, como se mencionó anteriormente, es que ocasiona muchas colisiones.


FUNCION HASH (VALOR_BUSCADO)

HASH = VALOR_BUSCADO MOD NUMERO_PRIMO

INICIO = HASH (VALOR)

IL = INICIO

ENCONTRADO = FALSO

Repetir

Si Vector[ IL ] = VALOR Entonces

ENCONTRADO = VERDADERO

En caso contrario

IL = (IL +1) MOD N

Hasta ENCONTRADO O IL = INICIO


Ejemplo

Realizar una función que busque un elemento por método Hashing. El elemento buscado esta un rango de direcciones relativas.


FUNCION HASH (VALOR_BUSCADO)HASH = VALOR_BUSCADO MOD NUMERO_PRIMO

PROCEDURE BUSCARINICIO = HASH (VALOR)IL = INICIOENCONTRADO = FALSORepetir

Si Vector[ IL ] = VALOR EntoncesENCONTRADO = VERDADERO

En caso contrarioIL = (IL +1) MOD N

Hasta ENCONTRADO O IL = INICIO


Al igual que en los métodos de ordenamiento los métodos de búsqueda variarán dependiendo de las características de los datos, el volumen de ellos y el número de comparaciones que se deba realizar para encontrar el elemento deseado.

En algunos casos el método de búsqueda se deberá realizar luego de una ordenación de la estructura, esto permitirá que la búsqueda sea más eficiente es decir más rápida.


Nota: Ambos procesos pueden clasificarse como internos o externos dependiendo del lugar en el que se encuentre almacenada la información.

◦ Los internos se llevan a cabo en memoria principal.

◦ Los externos se realizan en memoria secundaria (discos flexibles, cintas, discos duros, etc.).


Documents

Capitulo III Ordenamiento y Busqueda