1).
Ordenamiento de burbuja
El Ordenamiento 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.
Descripcin
Una manera simple de expresar el ordenamiento de burbuja en pseudocdigo es
la siguiente:
Este algoritmo realiza el ordenamiento de una lista a den valores, en este caso
de n trminos numerados del 0al n-1, consta de dos bucles anidados uno con el
ndicei, que da un tamao menor al recorrido de la burbuja en sentido inverso
de 2 a n, y un segundo loop con el ndice j, con un recorrido desde 0 hasta n-i,
para cada iteracin del primer bucle, que indica el lugar de la burbuja.
La burbuja son dos trminos de la lista seguidos, j yj+1, que se comparan, si el
primero es menor que el segundo sus valores se intercambian.
Esta comparacin se repite en el centro de los dos bucles, dando lugar a la
postre a una lista ordenada, puede verse que el nmero de repeticiones sola
depende de n, y no del orden de los trminos, esto es si pasamos al algoritmo
una lista ya ordenada, realizara todas las comparaciones exactamente igual que
para una lista no ordenada, esta es una caracterstica de este algoritmo, luego
verano una variante que evita este inconveniente.
Para comprender el funcionamiento, veamos un ejemplo sencillo:
Tenemos una lista de nmeros que hay que ordenar:
Podemos ver que la lista que tiene cinco trminos, luego:
El ndice i har un recorrido de 2 hasta n:
Que en este caso ser de 2 a 5. Para cada uno de los valores
de i, j tomara sucesivamente los valores de 0 hasta n-i:
Para cada valor de j, obtenido en ese orden, se compara el
valor del ndice j con el siguiente:
Si
el
termino j es menor, en su caso podra se mayor, que el
termino j+1, los valores se permutan, en caso contrario
se contina con la iteracin.
Para el caso del ejemplo, tenemos que:
Para la primera iteracin del primer bucle:
y j tomara los valores de 0 hasta 3:
Cuando j vale 0, se comparan
, el 55 y el 86, dado que 55 < 86 no se
permutan el orden.
Ahora j vale 1 y se comparan
el 86 y el 48 Como 86 > 48, se
permutan, dando lugar a una nueva
lista.
Se
repite
el
proceso
hasta
que j valga 3, dando lugar a una re
lista super ordenada, podemos ver
que el termino de mayor valor esta
en el lugar ms alto.
Ahora i vale 3, y j har un recorrido de 0 a 2.
Primero j vale 0, se comparan
, el 55 y el 48, como 55 > 48 se permutan
dando lugar a la nueva lista.
Para j = 1 se compara el 55 con el 16 y se cambian de orden.
Para j = 2 se compara el 55 y el 82 y se dejan como estn, finalizando el bucle
con una lista mejor ordenada, puede verse que los dos valores ms altos ya
ocupan su lugar. No se ha realizado ninguna comparacin con el termino cuarto,
dado que ya se sabe que despus del primer ciclo es el mayor de la lista.
El
algoritmo
consiste
en
comparaciones
sucesivas
de
dos
trminos
consecutivos, ascendiendo de abajo a arriba en cada iteracin, como la
ascensin de las burbujas de aire en el agua, de ah el nombre del
procedimiento, en la primera iteracin el
recorrido ha sido completo, en el segundo se
ha dejado l ltimo termino, al tener ya el
mayor de los valores, en los sucesivos s ira
dejando
re
realizar
las
ultimas
comparaciones, como se puede ver.
Ahora ya i vale 4 y j recorrer los valores de
0 a 1.
Cuando j vale 0, se comparan
esto es
el 48 y el 16 dado que 48 es mayor que 16 se permutan los valores, dando lugar
a una lista algo ms ordenada que la anterior, desde esta nueva
ordenacin, j pasa a valer 1, con lo que se comparan los trminos
el 48 y
el 55 que quedan en el mismo orden.
En este caso la burbuja ha ascendido menos que en los casos anteriores, y la
lista esta ya ordenada, pero el algoritmo tendr que completarse, realizando una
ultima iteracin.
Hay que tener en cuenta que el bucle para realiza un nmero fijo de repeticiones
y para finalizar tendrn que completarse, aun en el caso extremo, de que la lista
estara previamente ordenada.
Por ltimo i vale 5 y j solo puede vale 0, con lo que
solo se realizara una comparacin de
el 16 y el
48, que ya estn ordenados y se dejan igual.
Los bucles finalizan y tambin el procedimiento,
dejando la lista ordenada.
Una variante que finaliza en caso de que la lista este
ordenada, puede ser la siguiente, empleando un
centinela ordenado, que detecta que no se ha modificado la lista en un recorrido
de la burbuja, y que por tanto la lista ya esta ordenada, finalizando.
2). Ordenamiento por insercin
El ordenamiento por insercin (insertion sort en ingls) es una manera muy natural de
ordenar para un ser humano, y puede usarse fcilmente 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. Despus,
cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se
compara con todos los elementos ya ordenados, detenindose cuando se encuentra un
elemento menor (todos los elementos mayores han sido desplazados una posicin a la
derecha). En este punto se inserta el elemento k+1 debiendo desplazarse los dems
elementos.
Ejemplo de funcionamiento
En el siguiente ejemplo, 32 debe ser insertado entre 26 y 47, y por lo tanto 47, 59 y 96 deben
ser desplazados.
k+1
11 26 47 59 96 32
11 26
47 59 96
11 26 32 47 59 96
En la implementacin computacional, el elemento k+1 va comparndose de atrs para
adelante, detenindose con el primer elemento menor. Simultneamente se van haciendo los
desplazamientos.
11
11
11
11
11
26
26
26
26
26
47 59 96
47 59
47
59
47 59
32 47 59
32
96
96
96
96
El algoritmo en pseudocdigo (con listas que empiezan por 0) debera ser como el siguiente:
algoritmo insertSort( A : lista de elementos ordenables )
para i=1 hasta longitud(A) hacer
index=A[i]
j=i-1
mientras j>=0 y A[j]>index hacer
A[j+1] = A[j]
j = j - 1
fin mientras
A[j+1] = index
fin para
fin algoritmo
Aunque este algoritmo tiene un mejor orden de complejidad que el de burbuja, es muy
ineficiente al compararlo con otros algoritmos comoquicksort. Sin embargo, para listas
relativamente pequeas el orden por insercin es una buena eleccin, no slo porque puede
ser ms rpido para cantidades pequeas de elementos sino particularmente debido a su
facilidad de programacin.
Java
public static void insertSort (int[] v) {
for (int i=1; i<[Link]; i++) {
int aux = v[i];
int j;
for (j=i-1; j>=0 && v[j]>aux; j--)
v[j+1] = v[j];
v[j+1] = aux;
}
}
3).Ordenamiento Shell
El ordenamiento Shell (Shell sort en ingls) es un algoritmo de ordenamiento. El mtodo
se denomina Shell en honor de su inventorDonald 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(nlog2 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 Shell sort es una generalizacin del ordenamiento por insercin, teniendo en cuenta dos
observaciones:
1. El ordenamiento por insercin es eficiente si la entrada est "casi ordenada".
2. El ordenamiento por insercin es ineficiente, en general, porque mueve los valores
slo una posicin cada vez.
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.
Ejemplo
Considere un pequeo valor que est inicialmente almacenado en el final del vector. Usando
un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por insercin,
tomar aproximadamente n comparaciones e intercambios para mover este valor hacia el
otro extremo del vector. El Shell sort primero mueve los valores usando tamaos de espacio
gigantes, de manera que un valor pequeo se mover bastantes posiciones hacia su
posicin final, con slo unas pocas comparaciones e intercambios.
Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una
tabla y ordene las columnas (usando unordenamiento por insercin). Repita este proceso,
cada vez con un nmero menor de columnas ms largas. Al final, la tabla tiene slo una
columna. Mientras que transformar la lista en una tabla hace ms fcil visualizarlo, el
algoritmo propiamente hace su ordenamiento en contexto (incrementando el ndice por el
tamao de paso, esto es usando i += tamao_de_paso en vez de i++).
Por ejemplo, considere una lista de nmeros como [ 13 14 94 33 82 25 59 94 65
23 45 27 73 25 39 10 ]. Si comenzamos con un tamao de paso de 5, podramos
visualizar esto dividiendo la lista de nmeros en una tabla con 5 columnas. Esto quedara
as:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Entonces ordenamos cada columna, lo que nos da
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Cuando lo leemos de nuevo como una nica lista de nmeros, obtenemos [ 10 14 73 25
23 13 27 94 33 39 25 59 94 65 82 45 ]. Aqu, el 10 que estaba en el extremo
final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada
usando un ordenamiento con un espacio de 3 posiciones, y despus un ordenamiento con
un espacio de 1 posicin (ordenamiento por insercin simple).
El Shell sort lleva este nombre en honor a su inventor, Donald Shell, que lo public en 1959.
Algunos libros de texto y referencias antiguas le llaman ordenacin "Shell-Metzner" por
Marlene Metzner Norton, pero segn Metzner, "No tengo nada que ver con el algoritmo de
ordenamiento, y mi nombre nunca debe adjuntarse a ste." [1]
[editar]Secuencia
de espacios
La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia
incremental funcionara siempre que el ltimo elemento sea 1. El algoritmo comienza
realizando un ordenamiento por insercin con espacio, siendo el espacio el primer nmero
en la secuencia de espacios. Continua para realizar un ordenamiento por insercin con
espacio para cada nmero en la secuencia, hasta que termina con un espacio de 1. Cuando
el espacio es 1, el ordenamiento por insercin con espacio es simplemente un ordenamiento
por insercin ordinario, garantizando que la lista final estar ordenada.
La secuencia de espacios que fue originalmente sugerida por Donald Shell deba comenzar
con N /
2 y dividir por la mitad el nmero hasta alcanzar 1. Aunque esta secuencia
proporciona mejoras de rendimiento significativas sobre los algoritmos cuadrticos como
el ordenamiento por insercin, se puede cambiar ligeramente para disminuir ms el tiempo
necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia
permite un ordenamiento O(n2) del peor caso, si los datos estn inicialmente en el vector
como (pequeo_1, grande_1, pequeo_2, grande_2, ...) - es decir, la mitad alta de los
nmeros estn situados, de forma ordenada, en las posiciones con ndice par y la mitad baja
de los nmeros estn situados de la misma manera en las posiciones con ndice impar.
Quizs la propiedad ms crucial del Shell sort es que los elementos permanecen kordenados incluso mientras el espacio disminuye. Se dice que un vector dividido en k
subvectores esta k-ordenado si cada uno de esos subvectores esta ordenado en caso de
considerarlo aislado. Por ejemplo, si una lista fue 5-ordenada y despus 3-ordenada, la lista
est ahora no slo 3-ordenada, sino tanto 5-ordenada como 3-ordenada. Si esto no fuera
cierto, el algoritmo deshara el trabajo que haba hecho en iteraciones previas, y no
conseguira un tiempo de ejecucin tan bajo.
Dependiendo de la eleccin de la secuencia de espacios, Shell sort tiene un tiempo de
ejecucin en el peor caso de O(n2) (usando los incrementos de Shell que comienzan con 1/2
O(n3 / 2) (usando los incrementos de
Hibbard de 2k 1), O(n4 / 3) (usando los incrementos de Sedgewick de 9(4i) 9(2i) + 1,
o 4i + 1 + 3(2i) + 1), o O(nlog2n), y posiblemente mejores tiempos de ejecucin no
comprobados. La existencia de una implementacin O(nlogn) en el peor caso del Shell sort
del tamao del vector y se dividen por 2 cada vez),
permanece como una pregunta por resolver.
[editar]Implementaciones
El Shell sort se usa comnmente en lenguajes de programacin; esto es una implementacin
del algoritmo en C/C++ para ordenar un vectorde enteros. La secuencia de incrementos
usada en este ejemplo de cdigo da un tiempo de ejecucin O(n2) en el peor caso.
Java
public static void shellSort(int[] a) {
for ( int increment = [Link] / 2;
increment > 0;
increment = (increment == 2 ? 1 : (int)
[Link](increment / 2.2))) {
for (int i = increment; i < [Link]; i++) {
for (int j = i; j >= increment && a[j - increment] >
a[j]; j -= increment) {
int temp = a[j];
a[j] = a[j - increment];
a[j - increment] = temp;
}
}
}
}
4). Quicksort
El ordenamiento rpido (quicksort en ingls) es un algoritmo basado en la tcnica
de divide y vencers, que permite, en promedio, ordenar n elementos en un tiempo
proporcional a n log n.
Descripcin del algoritmo
El algoritmo consta de los siguientes pasos:
Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
Resituar los dems 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
implementacin 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 ms de un elemento. Una vez terminado este proceso todos los elementos
estarn ordenados.
Como se puede suponer, la eficiencia del algoritmo depende de la posicin en la que termine
el pivote elegido.
En el mejor caso, el pivote termina en el centro de la lista, dividindola en dos
sublistas de igual tamao. En este caso, el orden de complejidad del algoritmo
es O(nlog n).
En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad
del algoritmo es entonces de O(n). El peor caso depender de la implementacin del
algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi
ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo
implementado toma como pivote siempre el primer elemento del array, y el array que le
pasamos est ordenado, siempre va a generar a su izquierda un array vaco, lo que es
ineficiente.
En el caso promedio, el orden es O(nlog n).
No es extrao, pues, que la mayora de optimizaciones que se aplican al algoritmo se
centren en la eleccin del pivote.
[editar]Demostracin
Podramos probar el orden de ejecucin en el mejor caso de la siguiente manera:
Vamos a suponer que el nmero total de elementos a ordenar es potencia de dos, es
decir, n = 2k. de aqu podemos ver que k = log2(n), donde k es el nmero de divisiones que
realizar el algoritmo.
En la primera fase del algoritmo habrn n comparaciones, en la segunda fase el algoritmo
crear dos sublistas aproximadamente de tamao n/2. El nmero total de comparaciones de
estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesar 4 sublistas ms,
por tanto el nmero total de comparaciones en esta fase es 4(n/4) = n.
En conclusin, el nmero total de comparaciones que hace el algoritmo es:
n + n + n + ..... + n = kn, donde k = log2(n), por tanto el tiempo de ejecucin del algoritmo en el
mejor caso es O(n.log2n)
[editar]Optimizacin
del algoritmo
Cabe destacar que de usarse en su versin recursiva las siguientes optimizaciones y sus
desventajas no se ven vistas en el tiempo de ejecucin del mismo mantenindose, as el
tiempo de ejecucin planteado en un principio.
[editar]Tcnicas
de eleccin del pivote
El algoritmo bsico del metodo 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.
Otra opcin puede ser recorrer la lista para saber de antemano qu elemento
ocupar la posicin central de la lista, para elegirlo como pivote. Esto puede hacerse
en O(n) y asegura que hasta en el peor de los casos, el algoritmo sea O(nlog n). No
obstante, el clculo adicional rebaja bastante la eficiencia del algoritmo en el caso
promedio.
La opcin a medio camino es tomar tres elementos de la lista - por ejemplo, el
primero, el segundo, y el ltimo - y compararlos, eligiendo el valor del medio como
pivote.
[editar]Tcnicas
de reposicionamiento
Una idea preliminar para ubicar el pivote en su posicin final sera contar la cantidad de
elementos menores que l, y colocarlo un lugar ms arriba, moviendo luego todos esos
elementos menores que l a su izquierda, para que pueda aplicarse la recursividad.
Existe, no obstante, un procedimiento mucho ms efectivo. Se utilizan dos ndices: i, al que
llamaremos ndice izquierdo, y j, al que llamaremos ndice derecho. El algoritmo es el
siguiente:
Recorrer la lista simultneamente con i y j: por la izquierda con i (desde el primer
elemento), y por la derecha con j (desde el ltimo elemento).
Cuando lista[i] sea mayor que el pivote y lista[j] sea menor, se intercambian los
elementos en esas posiciones.
Repetir esto hasta que se crucen los ndices.
El punto en que se cruzan los ndices es la posicin adecuada para colocar el pivote,
porque sabemos que a un lado los elementos son todos menores y al otro son todos
mayores (o habran sido intercambiados).
[editar]Transicin
a otro algoritmo
Como se coment antes, el algoritmo quicksort ofrece un orden de ejecucin O(n) para
ciertas permutaciones "crticas" de los elementos de la lista, que siempre surgen cuando se
elige el pivote a ciegas. La permutacin concreta depende del pivote elegido, pero suele
corresponder a secuencias ordenadas. Se tiene que la probabilidad de encontrarse con una
de estas secuencias es inversamente proporcional a su tamao.
Los ltimos pases de quicksort son numerosos y ordenan cantidades pequea de
elementos. Un porcentaje medianamente alto de ellos estarn dispuestos de una
manera similar al peor caso del algoritmo, volviendo a ste ineficiente. Una solucin a
este problema consiste en ordenar las secuencias pequeas usando otro algoritmo.
Habitualmente se aplica el algoritmo de insercin para secuencias de tamao menores
de 8-15 elementos.
Pese a que en secuencias largas de elementos la probabilidad de hallarse con una
configuracin de elementos "crtica" es muy baja, esto no evita que sigan apareciendo (a
veces, de manera intencionada). El algoritmo introsort es una extensin del algoritmo
quicksort que resuelve este problema utilizando heapsort en vez de quicksort cuando el
nmero de recursiones excede al esperado.
Parmetros:
Se debe llamar a la funcin Quicksort desde donde quiera ejecutarse
sta llamar a colocar pivote para encontrar el valor del mismo
Se ejecutar el algoritmo Quicksort de forma recursiva a ambos lados del
pivote
int colocar(int *v, int b, int t)
{
int i;
int pivote, valor_pivote;
int temp;
pivote = b;
valor_pivote = v[pivote];
for (i=b+1; i<=t; i++){
if (v[i] < valor_pivote){
pivote++;
temp=v[i];
v[i]=v[pivote];
v[pivote]=temp;
}
}
temp=v[b];
v[b]=v[pivote];
v[pivote]=temp;
return pivote;
}
void Quicksort(int* v, int b, int t)
{
int pivote;
if(b < t){
pivote=colocar(v, b, t);
Quicksort(v, b, pivote-1);
Quicksort(v, pivote+1, t);
}
}
Nota: Los tres parmetros de la llamada inicial a Quicksort sern array[0], 0,
numero_elementos -1, es decir, si es un array de 6 elementos array[0], 0, 5
[editar]Ejemplo
En el siguiente ejemplo se marcan el pivote y los ndices i y j con las letras p, i y j
respectivamente.
Comenzamos con la lista completa. El elemento pivote ser el 4:
5 - 3 - 7 - 6 - 2 - 1 - 4
Comparamos con el 5 por la izquierda y el 1 por la derecha.
5 - 3 - 7 - 6 - 2 - 1 - 4
i
j
p
5 es mayor que 4 y 1 es menor. Intercambiamos:
1 - 3 - 7 - 6 - 2 - 5 - 4
i
j
p
Avanzamos por la izquierda y la derecha:
1 - 3 - 7 - 6 - 2 - 5 - 4
i
j
p
3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ah.
1 - 3 - 7 - 6 - 2 - 5 - 4
i
j
p
7 es mayor que 4 y 2 es menor: intercambiamos.
1 - 3 - 2 - 6 - 7 - 5 - 4
i
j
p
Avanzamos por ambos lados:
1 - 3 - 2 - 6 - 7 - 5 - 4
iyj
En este momento termina el ciclo principal, porque los ndices se cruzaron. Ahora
intercambiamos lista[i] con lista[sup] (pasos 16-18):
1 - 3 - 2 - 4 - 7 - 5 - 6
p
Aplicamos recursivamente a la sublista de la izquierda (ndices 0 - 2). Tenemos lo siguiente:
1 - 3 - 2
1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha.
Como se intercambiaron los ndices termina el ciclo. Se intercambia lista[i] con lista[sup]:
1 - 2 - 3
El mismo procedimiento se aplicar a la otra sublista. Al finalizar y unir todas las sublistas
queda la lista inicial ordenada en forma ascendente.
1 - 2 - 3 - 4 - 5 - 6 - 7
[editar]Implementaciones
El algoritmo de ordenamiento rpido (Quicksort) en:
Pseudocdigo
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 aadir x a less
else aadir x a greater
return concadenar(quicksort(less), pivot, quicksort(greater))
Java
//Recibe un vector de enteros y el ndice del primer y ltimo
elemento vlido del mismo
void ordenarQuicksort(int[] vector, int primero, int ultimo){
int i=primero, j=ultimo;
int pivote=vector[(primero + ultimo) / 2];
int auxiliar;
do{
while(vector[i]<pivote) i++;
while(vector[j]>pivote) j--;
if (i<=j){
auxiliar=vector[j];
vector[j]=vector[i];
vector[i]=auxiliar;
i++;
j--;
}
} while (i<=j);
if(primero<j) ordenarQuicksort(vector,primero, j);
if(ultimo>i) ordenarQuicksort(vector,i, ultimo);
}
5).Ordenamiento por seleccin
El ordenamiento por seleccin (Selection Sort en ingls) es un algoritmo de
ordenamiento que requiere O(n2)operaciones para ordenar una lista de n elementos.
Su funcionamiento es el siguiente:
Buscar el mnimo elemento de la lista
Intercambiarlo con el primero
Buscar el mnimo en el resto de la lista
Intercambiarlo con el segundo
Y en general:
Buscar el mnimo elemento entre una posicin i y el final de la lista
Intercambiar el mnimo con el elemento de la posicin i
De esta manera se puede escribir el siguiente pseudocdigo para ordenar una lista
de n elementos indexados desde el 1:
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
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 ms complejas, la operacin intercambiar() sera ms
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 lnea comentada con (!) se sustituyera
por intercambiar(lista[i], lista[j]) tendramos una versin 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 insercin directa
es que no mejora su rendimiento cuando los datos ya estn ordenados o parcialmente
ordenados. As como, por ejemplo, en el caso de la ordenacin de burbuja se requerira una
nica pasada para detectar que el vector ya est ordenado y finalizar, en la ordenacin por
seleccin se realizaran el mismo nmero de pasadas independientemente de si los datos
estn ordenados o no.
[editar]Implementaciones
Java
void selecccion(int[] a)
{
for (int i = 0; i < [Link] - 1; i++)
{
int min = i;
for (int j = i + 1; j < [Link]; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
if (i != min)
{
int aux= a[i];
a[i] = a[min];
a[min] = aux;
}
}
}
6). Ordenamiento por mezcla
El algoritmo de ordenamiento por mezcla (merge sort en ingls) es un algoritmo de
ordenamiento externo estable basado en la tcnicadivide y vencers. Es
de complejidad O(n log n).
Descripcin
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 1, entonces ya est ordenada. En otro caso:
2. Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del
tamao.
3. Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
4. Mezclar las dos sublistas en una sola lista ordenada.
El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de
ejecucin:
1. Una lista pequea necesitar menos pasos para ordenarse que una lista grande.
2. Se necesitan menos pasos para construir una lista ordenada a partir de dos listas
tambin ordenadas, que a partir de dos listas desordenadas. Por ejemplo, slo ser
necesario entrelazar cada lista una vez que estn ordenadas.
A continuacin se describe el algoritmo en pseudocdigo (se advierte de que no se incluyen
casos especiales para vectores vacos, etc.; una implementacin en un lenguaje de
programacin real debera tener en cuenta estos detalles):
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
[editar]Implementaciones
Java
public class MergeSort{
private int A[];
public int[] OrdenaMerge(int[] L) {
int n = [Link];
if (n >
int
int
int
1){
m = (int) ([Link](n/2.0));
[] L1 = new int[m];
[] L2 = new int[n-m];
for (int i = 0; i < m; i++){
L1[i] = L[i];
}
for (int i = m; i < n; i++){
L2[i-m] = L[i];
}
L = merge(OrdenaMerge(L1), OrdenaMerge(L2));
}
return L;
}
public int[] eliminar(int [] l){
int [] L = new int[[Link]-1];
for(int i = 1; i < [Link]; i++){
L[i-1] = l[i];
}
return L;
}
public int[] merge(int[] L1, int[] L2) {
int[] L = new int[[Link]+[Link]];
int i = 0;
while (([Link] != 0) && ([Link] != 0)) {
if (L1[0] < L2[0]){
L[i++] = L1[0];
L1 = eliminar(L1);
if ([Link] == 0){
while ([Link] != 0) {
L[i++] = L2[0];
L2 = eliminar(L2);
}
}
}
else{
L[i++] = L2[0];
L2 = eliminar(L2);
if ([Link] == 0) {
while ([Link] != 0) {
L[i++] = L1[0];
L1 = eliminar(L1);
}
}
}
}
return L;
}
public void generarNumeros(){
Random ran = new Random();
int x;
for(int i = 0; i < [Link]; i++){
x = (int)([Link]()*10000);
A[i] = x;
}
}
public void imprimir(){
for(int i = 0; i < [Link]; i++){
[Link](A[i]);
}
}
public int[] getA(){
return A;
}
public void setA(int []A){
this.A = A;
}
}
