Método de Selección: Este método consiste en buscar el elemento más pequeño del arreglo y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segundo lugar, y así sucesivamente hasta colocar el último elemento.
Método de Inserción Directa: En este método lo que se hace es tener una sublista ordenada de elementos del arreglo e ir insertando el resto en el lugar adecuado para que la sublista no pierda el orden. La sublista ordenada se va haciendo cada vez mayor, de modo que al final la lista entera queda ordenada.
Método Shell: Es una mejora del método de inserción directa, utilizado cuando el arreglo 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 vale 1.
Método HeapSort:
El ordenamiento por montículos (Heap sort en inglés) es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O(n log n).
Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.
Ejemplo en:
http://es.wikipedia.org/wiki/Heapsort
Método QuickSort: Este método se basa en la táctica "divide y vencerás", que consiste en ir subdividiendo el arreglo en arreglos más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del arreglo como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el arreglo.Normalmente se toma como pivote el primer elemento de arreglo, y se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.
Método MergeSort:
Una técnica muy poderosa para el diseño de algoritmos es "Dividir para conquistar". Los algoritmos de este tipo se caracterizan por estar diseñados siguiendo estrictamente las siguientes fases:
Dividir: Se divide el problema en partes más pequeñas.
Conquistar: Se resuelven recursivamente los problemas más chicos.
Combinar: Los problemas mas chicos de combinan para resolver el grande.
Mezcla.
Ordenación por mezcla (Merg Sort).
Intercalación de archivos ó mezcla de archivos.Por intercalación de archivos se entiende la unión o fusión de dos o más archivos ordenados de acuerdo con un determinado campo en un solo archivo.
Ejemplo:
A: 06 09 18 20 35
B: 10 16 25 28 66 82 87
C: 06 09 10 16 18 20 25 28 35 66 82 87
Monticulo:
Ordenación por el método de heapsort
El método de ordenación heapsort es también conocido con el nombre "montículo" en el mundo de habla hispana. Su nombre se debe a su autor J. W. Williams quien lo bautió así. Es el más eficiente de los métodos de ordenación que trabajan con árboles.
La idea central de este algoritmo consiste en lo siguiente:
- Construir un montículo.
-Eliminar la raíza del montículo en forma repetida.
Definición. un montículo se define como "Para todo nodo del árbol se debe cumplir que su valor de cualquiera de sus hijos".
Para representar un montículo en un arreglo lineal:
El nodo k se almacena en la posición k correspondiente del arreglo.
El hijo izquierda del nodo k, se almacena en la posición 2 * k.
El hijo derecho del nodo k, se almacena en la posición 2 * k+1.
Inserción de un elemento en un montículo.
La inserción de un elemento en un motnículo se lleva a cabo de la siguiente manera:
Se inserta el elemento en la primera posición disponible.
Se verifica si su valor es mayor que el de su padre. Si se cumple está condición entonces se efectúa el intercambio. Sino se cumple está condición, entonces, el algoritmo se detiene y el elemento queda ubicado en su posición correcta en el montículo. Cabe aclarar que el paso 2 se aplica de manera recursiva y desde abajo hacia arriba.
METODO RADIX
El siguiente método que consideramos se denomina ordenamiento de raíz. Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan. Por ejemplo, el numero 235 es en notación decimal que se escribe con un 2 en la posición de centenas, un 3 en la posición de decenas y un 5 en la posición de unidades. El mas grande de dos enteros de igual longitud se determina del modo siguiente: empezar en el digito mas significativo y avanzar por los dígitos menos significativos mientras coincidan los dígitos correspondientes en los dos números. El numero con el digito mas grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos. Por supuesto, si coinciden todos los dígitos de ambos números, los números son iguales.
Búsqueda por hash
Hasta ahora las técnicas de localización de registros vistas, emplean un proceso de búsqueda que implica cierto tiempo y esfuerzo. El siguiente método nos permite encontrar directamente el registro buscado. La idea básica de este método consiste en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas. Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando R(k1 )= R(k2) Pero : K1 diferente de K2 decimos que hay una colisión. A dos llaves diferentes que les corresponda la misma dirección relativa se les llama sinónimos.
No hay comentarios:
Publicar un comentario