-Ordenamiento externo
Ordenamiento externo es un término genérico para los algoritmos de ordenamiento que pueden manejar grandes cantidades de información. El ordenamiento externo se requiere cuando la información que se tiene que ordenar no cabe en la memoria principal de una computadora (típicamente la RAM) y un tipo de memoria más lenta (típicamente un disco duro) tiene que utilizarse en el proceso.
-Algoritmo de ordenación natural
Un algoritmo de ordenación natural es aquel que, dándole como entrada una secuencia ya ordenada (1, 2, 3, 4, 5, 6...), tardará para esa secuencia la menor cantidad de tiempo posible, comparándolo con el tiempo de proceso de otras secuencias desordenadas.
-Algoritmo de ordenación no natural
Un algoritmo de ordenación no natural es aquel que, dándole como entrada una secuencia inversamente ordenada (6, 5, 4, 3, 2, 1), tardará para esa secuencia la menor cantidad de tiempo posible, comparándolo con el tiempo de proceso de otras secuencias desordenadas.
Un algoritmo es un conjunto de operaciones matemáticas que dará origen a un resultado que se podrá conseguir a través de operaciones, con variables.
-Ordenamiento de burbuja
La posición de los elementos en el ordenamiento de burbuja juegan un papel muy importante en la determinación del rendimiento. Los elementos mayores al principio de la lista son rápidamente movidos hacia abajo, mientras los elementos menores en el fondo de la lista se mueven a la parte superior muy lentamente. Esto llevó a nombrar estos elementos conejos y tortugas, respectivamente.
//Ordenamiento por método de la Burbuja void ordenamientoBurbuja(int v[], int util_v) { int temp, i, j; for (i = 0; i < util_v -1 ; i++) { for (j = i + 1; j < util_v ; j++) { if (v[i] > v[j]) { temp = v[i]; v[i] = v[j]; v[j] = temp; } } } }
-Conejos y Tortugas (Yo-yos) (?)
Varios esfuerzos se han realizado para eliminar las tortugas véase Exterminación y mejorar la velocidad del ordenamiento de burbuja, la cual será más redonda que nunca. El Ordenamiento por sacudida es un buen ejemplo, aunque aún mantiene, en el peor de los casos, una complejidad O (n2). El ordenamiento por combinación compara los elementos primero en pedazos grandes de la lista, moviendo tortugas extremadamente rápido, antes de proceder a pedazos cada vez más pequeños para alisar la lista. Su velocidad promedio es comparable a algoritmos rápidos (y complejos) como el ordenamiento rápido.
-Ordenamiento por monticulos (Heapsort)
El ordenamiento por montículos (heapsort en inglés) es un algoritmo de ordenamiento no recursivo, no estable, con complejidad computacional Θ(nlogn)
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.
function heapsort(array A[0..n]):
montículo M
integer i := 124578
for i = 0..n:
insertar_en_monticulo(M, A[i])
for i = 0..n:
A[i] = extraer_cima_del_monticulo(M)
return A
-Ordenamiento por insercion
El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.
C
void insertionSort(int numbers[], int array_size) { int i, a, index; for (i=1; i < array_size; i++) { index = numbers[i]; for (a=i-1;a >= 0 && numbers[a] > index;a--) { numbers[a + 1] = numbers[a]; } numbers[a+1] = index; } }
-Ordenamiento 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).
Fue desarrollado en 1945 por John Von Neumann.
Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:
- Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:
- Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
- Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
- Mezclar las dos sublistas en una sola lista ordenada.
- Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
- Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas.
function mergesort(array A[x..y])
begin
if (x-y > 1)):
array A1 := mergesort(A[x..(int( x+y / 2))])
array A2 := mergesort(A[int(1+(x+y / 2))..y])
return merge(A1, A2)
else:
return A
end
function merge(array A1[0..n1], array A2[0..n2])
begin
integer p1 := 0
integer p2 := 0
array R[0..(n1 + n2 + 2)]//suponiendo que n1 y n2 son las posiciones
//del array y no el length de este mismo, de otro modo seria (n1 + n2)
while (p1 <= n1 or p2 <= n2):
if (p1 <= n1 and A1[p1] <= A2[p2]):
R[p1 + p2] := A1[p1]
p1 := p1 + 1
else
if (p2 <= n2 and A1[p1] > A2[p2]):
R[p1 + p2] := A2[p2]
p2 := p2 + 1
return R
end-Ordenamiento rapido
El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el matemático John von Neumann basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
El algoritmo consta de los siguientes pasos:
- Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
- Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
- La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
- Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
function quicksort(array)
var list, less, greater
if length(array) ≤ 1
return array
seleccionar y eliminar un valor pivote pivot en el array
for each x in array
if x < pivot then añadir x a less
else añadir x a greater
return concatenar(quicksort(less), pivot, quicksort(greater))-Ordenamiento por seleccion
El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos.
Su funcionamiento es el siguiente:
- Buscar el mínimo elemento de la lista
- Intercambiarlo con el primero
- Buscar el mínimo en el resto de la lista
- Intercambiarlo con el segundo
- 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
para i=1 hasta n-1
minimo = i;
para j=i+1 hasta n
si lista[j] < lista[minimo] entonces
minimo = j /* (!) */
fin si
fin para
intercambiar(lista[i], lista[minimo])
fin para-Ordenamiento Shell
El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación 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 fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:
- El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
- El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.
C++
void Shell( int Vector[], int Longitud ) { int I, J, Incremento, Temp; Incremento = Longitud / 2;//<Longitud> es el numero de elementos del vector while ( Incremento > 0 ) { for ( I = Incremento; I < Longitud; I++) { J = I; Temp = Vector[ I ]; while ( ( J >= Incremento ) && ( Vector[ J - Incremento ] > Temp ) ) { Vector[ J ] = Vector[ J - Incremento ]; J = J - Incremento; } Vector[ J ] = Temp; } Incremento = Incremento / 2; } }
Aqui les dejo otro link de unas animaciones de algunos de estos
algoritmos:
http://ingecomp.mforos.com/674005/3017040-animacion-de-algoritmos-de-ordenamiento-resubido/ -Bibliografia
http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento
Bien; 9 puntos.
ResponderEliminar