Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Arreglos: Métodos de Búsqueda e Ordenación

No description
by

Ricardo Ros

on 21 August 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Arreglos: Métodos de Búsqueda e Ordenación

UNIVERSIDAD FERMÍN TORO
DECANATO DE INGENIERÍA
ESCUELA DE COMPUTACIÓN

ORDENACIÓN POR EL MÉTODO DE LA BURBUJA
Búsqueda
La búsqueda es la operación más importante en el procesamiento de información, ya que permite recuperar datos previamente almacenados. El resultado de una búsqueda puede ser un éxito, si se encuentra la información o un fracaso, si no la encuentra.

La búsqueda se puede aplicar sobre elementos previamente ordenados o sobre elementos desordenados, en el primer caso la búsqueda es más fácil, en cambio en el segundo se dificulta un poco más el proceso, sobre todo cuando de se trata de encontrar una cantidad de elementos similares.

Los métodos de búsqueda se clasifican en:
- Búsqueda interna.
- Búsqueda externa.

La recuperación de información es una de las aplicaciones má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.

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

Una búsqueda es el proceso mediante el cual podemos localizar un elemento con un valor específico dentro de un conjunto de datos. Terminamos con éxito la búsqueda cuando el elemento es encontrado.

A continuación veremos algunos de los algoritmos de búsqueda que existen.
Búsqueda secuencial
Búsqueda binaria
Arreglos: Métodos de Búsqueda e Ordenación
Integrante:
Ros, Ricardo.

Cabudare, Mayo 2015
Este método consiste en acomodar el vector moviendo el mayor hasta la última casilla comenzando desde la casilla cero del vector hasta haber acomodado el número más grande el la última posición, una vez acomodado el más grande, prosigue a encontrar y acomodar el siguiente más grande comparando de nuevo los números desde el inicio del vector, y así sigue hasta ordenar todo los elementos el arreglo.

Entonces, este algoritmo es muy deficiente porque al ir comparando las casillas para buscar el siguiente más grande, éste vuelve a comparar las ya ordenadas. A pesar de ser el algoritmo de ordenamiento más deficiente que hay, éste es el más usado en todos los lenguajes de programación.

Dado un vector a1, a2, a3, ... an
1) Comparar a^1 con a^2 e intercambiarlos si a1>a2 (o a12)
2) Seguir hasta que todo se haya comparado an-1 con an
3) Repetir el proceso anterior n-1 veces

Algoritmo: Complejidad

for(i=0; i < n-1; i++){ T(n2)

for(j=0; j < n-1; j++){ T(n)

if(vec[j] > vec[j+1]){ T(1)

aux=vec[j]; T(1)

vec[j]=vec[j+1]; T(1)

vec[j+1]=aux;} T(1)
Ir comparando desde la casilla 0 numero tras número hasta encontrar uno mayor, si este es realmente el mayor de todo el vector se llevará hasta la última casilla, si no es así, será reemplazado por uno mayor que él.

Este procedimiento seguirá así hasta que halla ordenado todas las casillas del vector.

Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario.
PROCEDIMIENTO
EJEMPLO
Ordenaciones
Ordenar es un proceso para reorganizar un conjunto dado de objetos en una secuencia especificada. El objetivo de este proceso es facilitar la búsqueda subsiguiente de los elementos del conjunto ordenado. El elemento por el cual está ordenado un conjunto de datos (o se está buscando) se denomina clave.

Ejemplos de objetos ordenados: guías de teléfonos, índices de libros, diccionarios, bibliotecas, etc.

Teniendo en cuenta que un conjunto de datos puede ser almacenado en un arreglo, en un archivo, en un arreglo de registros, una lista enlazada o un árbol, los métodos de ordenación se dividen en dos categorías:

(1) Ordenación Interna: los datos se almacenan en un arreglo, una lista enlazada o un árbol;
(2) Ordenación Externa: los datos se almacenan en un archivo.

La importancia de mantener nuestros arreglos ordenados radica en que es mucho más rápido tener acceso a un dato en un arreglo ordenado que en uno desordenado.

Existen muchos algoritmos para la ordenación de elementos en arreglos, enseguida veremos algunos de ellos.

Ordenación por Burbuja
Ordenación por Burbuja
Selección Directa
Selección Directa
El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere operaciones para ordenar una lista de n elementos.

Este método consiste en seleccionar el elemento más pequeño de nuestra lista para colocarlo al inicio y así excluirlo de la lista.

Para ahorrar espacio, siempre que vayamos a colocar un elemento en su posición correcta lo intercambiaremos por aquel que la esté ocupando en ese momento.

El algoritmo de selección directa es el siguiente:

i <- 1

mientras i<= N haz

min <-i

j <- i + 1

mientras j <= N haz

si arreglo[j] < [min] entonces

min <-j

j <- j + 1

intercambia(arreglo[min],arreglo[i])

i <- i +1
Descripción del algoritmo
Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lista
• Intercambiarlo con el primero
• Buscar el siguiente mínimo en el resto de la lista
• Intercambiarlo con el segundo

Y en general:
• Buscar el mínimo elemento entre una posición i y el final de la lista
• Intercambiar el mínimo con el elemento de la posición i

De esta manera se puede escribir el siguiente pseudocódigo para ordenar una lista de n elementos indexados desde el 1:

para i=1 hasta n-1
mínimo = i;
para j=i+1 hasta n
si lista[j] < lista[mínimo] entonces
mínimo = j /* (!) */
fin si
fin para
intercambiar(lista[i], lista[mínimo])
fin para
Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación intercambiar() sería más costosa en este caso. Este algoritmo realiza muchas menos operaciones intercambiar() que el de la burbuja, por lo que lo mejora en algo. Si la línea comentada con (!) se sustituyera por intercambiar(lista[i], lista[j]) tendríamos una versión del algoritmo de la burbuja (naturalmente eliminando el orden intercambiar del final).

Otra desventaja de este algoritmo respecto a otros como el de burbuja o de inserción directa es que no mejora su rendimiento cuando los datos ya están ordenados o parcialmente ordenados. Así como, por ejemplo, en el caso de la ordenación de burbuja se requeriría una única pasada para detectar que el vector ya está ordenado y finalizar, en la ordenación por selección se realizarían el mismo número de pasadas independientemente de si los datos están ordenados o no.


Descripción del algoritmo
Ordenación por Mezcla
Ordenación por Mezcla

El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n).

Este algoritmo consiste en partir el arreglo por la mitad, ordenar la mitad izquierda, ordenar la mitad derecha y mezclar las dos mitades ordenadas en un arreglo ordenado. Este último paso consiste en ir comparando pares sucesivos de elementos (uno de cada mitad) y poniendo el valor más pequeño en el siguiente hueco.

procedimiento mezclar(dat,izqp,izqu,derp,deru)

inicio

izqa <- izqp

dera <- derp

ind <- izqp

mientras (izqa <= izqu) y (dera <= deru) haz

si arreglo[izqa] < dat[dera] entonces

temporal[ind] <- arreglo[izqa]

izqa <- izqa + 1

en caso contrario

temporal[ind] <- arreglo[dera]

dera <- dera + 1

ind <- ind +1

mientras izqa <= izqu haz

temporal[ind] <- arreglo[izqa]

izqa <- izqa + 1

ind <- ind +1

mientras dera <= deru haz

temporal[ind] <=dat[dera]

dera <- dera + 1

ind <- ind + 1

para ind <- izqp hasta deru haz

arreglo[ind] <- temporal[ind]

fin

Descripción
Fue desarrollado en 1945 por John Von Neumann.

Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:

1. Si la longitud de la lista es 0 o 1, entonces ya está ordenada. En otro caso:
2. Dividir la lista desordenada en dos sub listas de aproximadamente la mitad del tamaño.
3. Ordenar cada sub lista recursivamente aplicando el ordenamiento por mezcla.
4. Mezclar las dos sub listas en una sola lista ordenada.

El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:

1. Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
2. Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.

A continuación se describe el algoritmo en pseudocódigo (se advierte de que no se incluyen casos especiales para vectores vacíos, etc.; una implementación en un lenguaje de programación real debería tener en cuenta estos detalles):
function mergesort(m)
var list left, right, result
if length(m) ≤ 1
return m
else
var middle = length(m) / 2
for each x in m up to middle - 1
add x to left
for each x in m at and after middle
add x to right
left = mergesort(left)
right = mergesort(right)
if last(left) ≤ first(right)
append right to left
return left
result = merge(left, right)
return result

function merge(left,right)
var list result
while length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
if length(left) > 0
append rest(left) to result
if length(right) > 0
append rest(right) to result
return result

Optimizando merge sort
En los ordenadores modernos, el principio de localidad puede ser primordial en la optimización de software, porque se usan jerarquías de memoria multinivel. Se han propuesto versiones de cache-consciente del algoritmo de ordenación por mezcla, cuyas operaciones han sido específicamente escogidas para minimizar el movimiento de entrada y salida de páginas de la memoria caché de la máquina. Por ejemplo, el algoritmo "tiled merge sort" deja de particionar sub arreglos cuando se han alcanzado sub arreglos de tamaño S, donde S es el número de elementos que caben en una única página en memoria. Cada uno de esos sub arreglos se ordenan con un algoritmo de ordenación in-situ, para evitar intercambios en memoria, y entonces se termina con el algoritmo de ordenamiento por mezcla en su versión recursiva estándar. Este algoritmo ha demostrado un mejor rendimiento en máquinas que se benefician de la optimización caché.

M.A. Kronrod sugirió en 1969 una versión alternativa del algoritmo de ordenamiento por mezcla que usaba espacio adicional constante. Este algoritmo fue refinado por Katajainen, Pasanen y Teuhola.

Comparación con otros algoritmos de ordenamiento
Aunque heapsort tiene los mismos límites de tiempo que merge sort, requiere sólo Θ (1) espacio auxiliar en lugar del Θ(n) de merge sort, y es a menudo más rápido en implementaciones prácticas. Quicksort, sin embargo, es considerado por mucho como el más rápido algoritmo de ordenamiento de propósito general. En el lado bueno, merge sort es un ordenamiento estable, paraleliza mejor, y es más eficiente manejando medios secuenciales de acceso lento. Merge sort es a menudo la mejor opción para ordenar una lista enlazada: en esta situación es relativamente fácil implementar merge sort de manera que sólo requiera Θ (1) espacio extra, y el mal rendimiento de las listas enlazadas ante el acceso aleatorio hace que otros algoritmos (como quicksort) den un bajo rendimiento, y para otros (como heapsort) sea algo imposible.

Para Perl 5.8, merge sort es el algoritmo de ordenamiento por defecto (lo era quicksort en versiones anteriores de Perl). En Java los métodos de ordenación de Arrays usan merge sort o una modificación de quicksort dependiendo de los tipos de datos y por cuestiones de eficiencia cambia a ordenamiento por inserción cuando se están ordenando menos de siete elementos en el arreglo.

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.

Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo.

Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del vector hasta encontrarlo, o hasta que se llegue al final. La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del vector.

A continuación se muestra el pseudocódigo del algoritmo:

Datos de entrada:
vec: vector en el que se desea buscar el dato
tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive. Puede representarse así: vec[0...tam) ó vec[0...tam-1].
dato: elemento que se quiere buscar.

Variables
pos: posición actual en el vector

pos = 0
while pos < tam:
if vec[pos] == dato:
Retorne verdadero y/o pos,
else:
pos = pos + 1
Fin (while)
Retorne falso,



int busquedaSimple(int vector[n], int n, int dato) {

int i;

for(i=0; i<n; i++){
if(dato==vector[i]) {
return i;
break;
}
}

return -1;

}


C
Búsqueda secuencial
Búsqueda binaria
Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado.

Esta búsqueda utiliza un método de “divide y vencerás” para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si este es el elemento buscado entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o segunda mitad de la lista y a continuación se repite el proceso anterior, utilizando el elemento central de esta sub lista. Este tipo de búsqueda se utiliza en vectores ordenados.

El método de búsqueda binaria divide el total de los elementos en dos, comparando el elemento buscado con el central, en caso de no ser iguales, se determina si el elemento buscado es menor o mayor al central, para determinar si la búsqueda continua del lado izquierdo (menor) o derecho (mayor) del central, repitiendo el mismo proceso de división y comparación, hasta encontrar el elemento buscado o que la división ya no sea posible.

Debemos destacar que este método de búsqueda solo funciona con estructuras de datos previamente ordenadas, dividiendo cada vez a la mitad el proceso de búsqueda, lo que hace que el método sea más eficiente.
Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.

Está altamente recomendado para buscar en arreglos de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del arreglo (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del arreglo que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del arreglo que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el arreglo.
Búsqueda binaria
Búsqueda binaria
A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central del arreglo

Datos de entrada:
vec: vector en el que se desea buscar el dato
tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive.
dato: elemento que se quiere buscar.

Variables
centro: subíndice central del intervalo
inf: límite inferior del intervalo
sup: límite superior del intervalo

inf = 0
sup = tam-1

Mientras inf <= sup:
centro = ((sup - inf) / 2) + inf // División entera: se trunca la fracción
Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario:
Si dato < vec[centro] entonces:
sup = centro - 1
En caso contrario:
inf = centro + 1
Fin (Mientras)
Devolver Falso

C
int busquedaBinaria(int vector[], int n, int dato) {
int centro,inf=0,sup=n-1;
while(inf<=sup){
centro=(sup+inf)/2;
if(vector[centro]==dato) return centro;
else if(dato < vector[centro]) sup=centro-1;
else inf=centro+1;
}
return -1;
}


Implementación recursiva en C++
#include <iostream>
#include <vector>

bool busqueda_dicotomica(const vector<int> &v, int principio, int fin, int &x){
bool res;
if(principio <= fin){
int m = (principio + fin)/2;
if(x < v[m]) res = busqueda_dicotomica(v, principio, m-1, x);
else if(x > v[m]) res = busqueda_dicotomica(v, m+1, fin, x);
else res = true;
}else res = false;
return res;
}
/*{Post: Si se encuentra devuelve true, sino false}*/

Búsqueda Hash
Búsqueda Hash
El método de búsqueda hash o por transformación de clave aumenta la velocidad de búsqueda sin necesidad de que los elementos estén previamente ordenados, comparándolo con los métodos anteriores. Además tiene la ventaja de que el tiempo de búsqueda es independiente del número de elementos de la estructura que los almacena.

Este método permite que el acceso a los datos sea por una llave que indica directamente la posición donde están guardados los datos que se buscan. Prácticamente trabaja con una función que transforma la llave o dato clave en una dirección (índice) dentro de la estructura y que en ocasiones puede generar una colisión, que se define como una misma dirección para dos o más claves distintas.

Para trabajar con este método de búsqueda debe elegir previamente dos cosas:

- Una función hash que sea fácil de calcular y que distribuya uniformemente las direcciones.
- Un método para resolver colisiones, generando posiciones alternativas.

Búsqueda Hash
Para encontrar la función hash no existe una regla que permita determinar cuál será la función más apropiada para generar un conjunto de claves que aseguren la máxima uniformidad en la distribución de las mismas. Algunas de las funciones hash más utilizadas son las siguientes:

- Función módulo (por división).
- Función cuadrada.
- Función plegamiento.
- Función truncamiento.

La función módulo o por división toma el residuo de la división entre la clave y el total de elementos de la estructura, generando la siguiente fórmula:

dirección = (clave % total elementos)

Para lograr una mayor uniformidad en la distribución de los elementos, se debe buscar que el valor que se usa en el total de elementos sea un número primo más cercano al tamaño de la estructura.

La idea principal de este método consiste en aplicar una función que traduce el valor del elemento buscado en un rango de direcciones relativas. Una desventaja importante de este método es que puede ocasionar colisiones.

funcion hash (valor_buscado)
inicio
hash <- valor_buscado mod numero_primo
fin
inicio <- hash (valor)
il <- inicio
encontrado <- falso
repite
si arreglo[il] = valor entonces
encontrado <- verdadero
en caso contrario
il <- (il +1) mod N
hasta encontrado o il = inicio
Búsqueda Hash
Full transcript