MTODOS UTILIZADOS EN ALGORITMOS
ORDENAMIENTO
BSQUEDA
MTODO DE LA BURBUJA
MTODO DE QUICKSORT
MTODO DE SHELLSORT
La Ordenacin de burbuja (Bubble Sort
en ingls) es un sencillo algoritmo de
ordenamiento. Funciona revisando cada
elemento de la lista que va a ser ordenada
con el siguiente, intercambindolos de
posicin si estn en el orden equivocado.
Es necesario revisar varias veces toda la
lista hasta que no se necesiten ms
intercambios, lo cual significa que 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 pequeas
"burbujas". Tambin es conocido como
el mtodo del intercambio directo. Dado
que solo usa comparaciones para operar
elementos, se lo considera un algoritmo
de comparacin, siendo el ms sencillo
de implementar.
El ordenamiento rpido (quicksort en ingls) es
un algoritmo creado por el cientfico britnico en
computacin C. A. R. Hoare basado en la tcnica
de divide y vencers, que permite, en promedio,
ordenar n elementos en un tiempo proporcional
a n log n.
El algoritmo bsico del mtodo
Quicksort consiste en tomar cualquier elemento de
la lista al cual denominaremos como pivote,
dependiendo de la particin en que se elija, el
algoritmo ser ms o menos eficiente. Tomar un
elemento cualquiera como pivote tiene la ventaja
de no requerir ningn clculo adicional, lo cual lo
hace bastante rpido. Sin embargo, esta eleccin
a ciegas siempre provoca que el algoritmo tenga
un orden de O(n) para ciertas permutaciones de
los elementos en la lista.
El ordenamiento Shell (Shell sort en ingls) es un
algoritmo de ordenamiento.
El mtodo
se
denomina Shell en honor de su inventor
Donald Shell. Su implementacin original,
requiere O(n2) comparaciones e intercambios en el
peor caso. Un cambio menor presentado en el
libro de V. Pratt produce una implementacin con
un rendimiento de O(n log2 n) en el peor caso.
Esto es mejor que las O(n2) comparaciones
requeridas por algoritmos simples pero peor que el
ptimo O(n log n). Aunque es fcil desarrollar un
sentido intuitivo de cmo funciona este algoritmo,
es muy difcil analizar su tiempo de ejecucin.
El algoritmo Shell sort mejora el ordenamiento
por insercin comparando elementos separados
por un espacio de varias posiciones. Esto permite
que un elemento haga "pasos ms grandes" hacia
su posicin esperada. Los pasos mltiples sobre
los datos se hacen con tamaos de espacio cada
vez ms pequeos. El ltimo paso del Shell sort es
un simple ordenamiento por insercin, pero para
entonces, ya est garantizado que los datos del
vector estn casi ordenados.
MTODO DE MERGESORT
El algoritmo de ordenamiento por mezcla (merge sort en ingls) es un
algoritmo de ordenamiento externo estable basado en la tcnica
divide y vencers. Es de complejidad O(n log n). Fue desarrollado en
1945 por John Von Neumann.
El ordenamiento por mezcla incorpora dos ideas principales para
mejorar su tiempo de ejecucin:
-Una lista pequea necesitar menos pasos para ordenarse que una lista
grande.
-Se necesitan menos pasos para construir una lista ordenada a partir de
dos listas tambin ordenadas, que a partir de dos listas desordenadas.
MTODO DE HEAPSORT
SECUENCIAL
BINARIA
Este mtodo 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 Bsqueda o
Elemento encontrado y otro que
diga
posicin=
en
caso
contrario, visualizar un mensaje
similar a Elemento no existe en
la Lista. Este tipo de bsqueda
compara cada elemento del vector
con el valor a encontrar hasta que
este se consiga o se termine de
leer el vector completo.
Es un mtodo que se basa en la divisin
sucesiva del espacio ocupado por el vector
en sucesivas mitades, hasta encontrar el
elemento buscado.
Esta bsqueda utiliza un mtodo de
divide y vencers para localizar el valor
deseado. Con este mtodo se examina
primero el elemento central de la lista; si
este es el elemento buscado entonces la
bsqueda ha terminado. En caso contrario
se determina si el elemento buscado est
en la primera o segunda mitad de la lista y
a continuacin se repite el proceso
anterior, utilizando el elemento central de
esta sublista. Este tipo de bsqueda se
utiliza en vectores ordenados.
HASH
En este mtodo se requiere que los elementos estn ordenados. El mtodo consiste en asignar
el ndice a cada elemento mediante una transformacin del elemento, esto se hace mediante una
El ordenamiento por montculos (heapsort en ingls) es un algoritmo de
funcin de conversin llamada funcin hash. Hay diferentes funciones para transformar el
ordenamiento no recursivo, no estable, con complejidad computacional
elemento y el nmero
obtenido es el ndice del elemento. La principal forma de transformar el
INCLUDEPICTURE "http://upload.wikimedia.org/math/f/2/9/f296a521bff060cd02c3ef6ee7931dd7.png"
\* MERGEFORMATINET
elemento es asignarlo directamente, es decir al 0 le corresponde el ndice 0, al 1 el 1, y as
sucesivamente pero cuando los elementos son muy grandes se desperdicia mucho espacio ya
Este algoritmo consiste en almacenar todos los elementos del vector a
que necesitamos arreglo grandes para almacenarlos y estos quedan con muchos espacios libres,
ordenar en un montculo (heap), y luego extraer el nodo que queda como
para utilizar mejor el espacio se utilizan funciones ms complejas. La funcin de hash ideal
nodo raz del montculo (cima) en sucesivas iteraciones obteniendo el
debera ser biyectiva, esto es, que a cada elemento le corresponda un ndice, y que a cada ndice
conjunto ordenado. Basa su funcionamiento en una propiedad de los
le corresponda un elemento, pero no siempre es fcil encontrar esa funcin, e incluso a veces es
montculos, por la cual, la cima contiene siempre el menor elemento (o
intil, ya que puedes no saber el nmero de elementos a almacenar.
el mayor, segn se haya definido el montculo) de todos los
almacenados en l.
