INTRODUCCIÓN (COMPLEJIDAD)
El ordenamiento de burbuja es uno de los más simples algoritmos de ordenamiento, pero NO ES EL MÁS EFICIENTE.FUNCIONAMIENTO
Este algoritmo coloca los elementos en orden creciente, sucesivamente comparando los elementos adyacentes, intercambiándose entre ellos si el orden está de forma incorrecta. Para llevar a cabo el ordenamiento de burbuja, se lleva a cabo una operación básica, cambiando el elemento más grande, por el más pequeño que lo sigue. Se pueden imaginar los elementos en la lista, colocados en una columnaPSEUDOCÓDIGO (ALGORITMO)
procedure bubblesort(a1, …, an : números reales con n >= 2)
for i := 1 to n – 1
for j := 1 to n – i
if aj > aj+1 then intercambiar
aj
and aj+1
{a1, …, an está en orden creciente}
EJEMPLO
Los pasos de este algoritmo están ilustrados en la figura de arriba. Empezando por comparar los dos primeros elementos 3 y 2. Porque 3 > 2, intercambiando 3 y 2, produciendo la lista 2, 3, 4, 1, 5. Porque 3 < 4, continua comparando 4 y 1. Porque 4 > 1, intercambiando 1 y 4, produciéndola lista 2, 3, 1, 4, 5. Porque 4 < 5, el primer paso está completo. El primer paso garantiza que el elemento más grande, 5, está en la correcta posición.
El segundo paso empieza comparando2 y 3. Porque estos están en correcto orden, 3 y 1 son comparados. Porque 3 > 1, estos números son intercambiados, produciendo 2, 1, 3, 4, 5. Porque 3 < 4, estos números están en orden correcto. No es necesario hacer más comparaciones en este paso, porque 5 está en la correcta posición. El segundo paso garantiza que los dos elementos más grandes, 4 y 5, están en la posición correcta.
ALGORITMO DE ORDENAMIENTO RAPIDO O QUICKSORT
Este algoritmo esta basado en la tecnica divide y vencerás (consiste en dividir el problema en pequeños subproblemas mas sencillos para luego estos ser resueltos con un calculo mas sencillo) asi crearemos arreglos mas pequeños para ordenar estos.
Los pasos que realiza este algoritmo son:
- Selecciona un valor del arreglo como pivote es decir un numero por el cual todos los elementos van a ser comparados.
- 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.
- luego se organizan los subarreglos que quedaron a mano derecha y izquierda.
Ejemplo:
Tenemos un arreglo que esta definido con los valores {22,40,4,10,12,35} los pasos en quicksort para arreglarlo son los siguientes:
- se toma como pivote el numero 22 recuerden puede ser cualquier numero.
- la búsqueda de izquierda a derecha encuentra el valor 40 que es mayor a pivote y la búsqueda de derecha a izquierda encuentra el valor 35 no lo toma porque es mayor a el numero pivote (recuerden que la búsqueda de derecha a izquierda busca los menores) entonces continua y encuentra a 12 que es menor que el pivote y se intercambian el resultado seria {21,12,4,10,40,35}
- si seguimos la búsqueda la primera encuentra el valor 40, y la segunda el valor 10,pero ya se han cruzado,así que paramos. Para terminar la división, se coloca el pivote en su lugar el numero encontrado por la segunda busqueda, el 10 quedando: {10,12,4,22,40,35}
- ahora tenemos dividido el arreglo en dos arreglos mas pequeños que son {10,12,4} y el {40,35}, y en ellos se repetirá el mismo proceso.
PSEUDOCODIGO
Principal
variables A: arreglo[1..100] entero
variables i,j,central:entero
variables primero, ultimo: entero
para i = 1 hasta 100
leer(A[i])
Fin para
primero = 1
ultimo = 100
qsort(A[],100)
Fin
Funcion qsort(primero, ultimo:entero)
i = primero
j = ultimo
central = A[(primero,ultimo) div 2]
repetir
mientras A[i]
j = j - 1
fin mientras
si i < = j
aux = A[i]
A[j] = A[i]
A[i] = aux
i = i + 1
j = j - 1
fin si
hasta que i > j
si primero < j
partir(primero,j)
fin si
si i < ultimo
partir(i, ultimo)
fin si
fin funcion qsort
IMPLEMENTACION EN JAVA
public 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);
}
ALGORITMO DE ORDENAMIENTO SHELLSORT
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.
El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.
La sucesión propuesta por Shell:
Peor Caso = O( n^2).
Caso Medio = O(n^2 ).
Con la sucesión
: 2^k-1
Peor Caso = O( n^1.5)
Caso Medio = O( n^1.5 )
Con la sucesión :(4^k+1+3 2^k+1)
Peor Caso = O(n^1.333)
Caso Medio=O(n^1.166)
El mejor caso sería O(n logn).
Método:
public static void shellSort( int a[ ])
{
for( int gap = a.length / 2; gap > 0; gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) ){
for( int i = gap; i < a.length; i++ ){
int tmp = a[ i ];
int j;
for(j = i; j >= gap && tmp < a[ j - gap ] ; j -= gap ){
a[ j ] = a[ j - gap ];
}
Ejemplo JAVA:
public class ShellSort {
public static void main(String args[]){
int arrayEntrada[]={321, 123, 213, 234, 1, 4, 5, 6}; Este es el array de elementos que vamos a ordenar
shellSort(arrayEntrada); llamada al metodo shellSort
for (int i=0;i < arrayEntrada.length;i++){ Este bucle imprime el contenido del array
System.out.print(arrayEntrada[i]+" ");
}fin del for
}fin del main
public static void shellSort( int a[ ]){
for( int gap = a.length / 2; gap > 0; gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) ){
for( int i = gap; i < a.length; i++ ){
int tmp = a[ i ];
int j;
for(j = i; j >= gap && tmp < a[ j - gap ] ; j -= gap ){
a[ j ] = a[ j - gap ];
}
a[ j ] = tmp;
}
}
}
}class ShellSort
ORDENAMIENTO RADIX
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 número 235 se escribe 2 en la posición de centenas, un 3 en la posición de decenas y un 5 en la posición de unidades.
Reglas para ordenar.
- Empezar en el dígito más significativo y avanzar por los dígitos menos significativos mientras coinciden los dígitos correspondientes en los dos números.
- El número con el dígito más 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 sí coinciden todos los dígitos de ambos números, son iguales).
Archivo original.
25 57 48 37 12 92 86 33
Asignamos colas basadas en el dígito menos significativo.
1
2 12 92
3 33
4
5 25
6 86
7 57 37
8 48
9
10
Después de la primera pasada:
12 92 33 25 86 57 37 48
Colas basadas en el dígito más significativo.Parte delantera Parte posterior
1 12
2 25
3 33 37
4 48
5 57
6
7
8 86
9 92
10
Archivo ordenado: 12 25 33 37 48 57 86 92
A S O R T I N G E X A M P L E
A E O L M I N G E A X T P R S
A E A E G I N M L O
A A E E G
A A
A A
E E G
E E
I N M L O
L M N O
L M
N O
S T P R X
S R P T
P R S
R S
#include
#include
Estado de la lista
i
| Node[i].info | Node[i].nextInicialización K = 1 K = 2 K = 3 | |||
0
|
65
|
1
|
3
|
1
|
2
|
1
|
789
|
2
|
-1
|
-1
|
-1
|
2
|
123
|
3
|
0
|
3
|
3
|
3
|
457
|
-1
|
1
|
0
|
1
|
rear = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
2 0 3 1
front = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
2 0 3 1
k = 1
p = 0 p = 1 p = 2 p = 3
first = 1 first = 2 first = 3 first = -1
y = 65 y = 789 y = 123 y = 457
exp = 1 exp = 1 exp = 1 exp = 1
j = 5 j = 9 j = 3 j = 7
q = -1 q = -1 q = -1 q = -1
si q == -1 si q == -1 si q == -1 si q == -1
front[5] = 0 front[9] = 1 front[3] = 2 front[7] = 3
rear[5] = 0 rear[9] = 1 rear[3] = 2 rear[7] = 3
j = 3
first = 2
while ( j <= 9)
i = 5
si i <= 9
p = 5
node[2].next = 0
j = 5
i = 7
si i <= 9
p = 7
node[0].next = 3
j = 5
i = 9
si i <= 9
p = 9
node[2].next = 1
j = 9
fin del while
p = 9
node[1].next = -1
Características.
- Debido a que el ciclo for (k = 1; k <= m; k++) externo se recorre m veces (una para cada dígito) y el ciclo interior n veces (una para cada elemento en el archivo) el ordenamiento es de aproximadamente (m*n).
- Si las llaves son complejas (es decir, si casi cada número que puede ser una llave lo es en realidad) m se aproxima a log n, por lo que (m*n) se aproxima a (n log n).
- Si la cantidad de dígitos es grande, en ocasiones es más eficiente ordenar el archivo aplicando primero el ordenamiento de raíz a los dígitos más significativos y después utilizando inserción directa sobre el archivo ordenado.
Ventajas.
- El ordenamiento es razonablemente eficiente si el número de dígitos en las llaves no es demasiado grande.
- Si las máquinas tienen la ventaja de ordenar los dígitos (sobre todo si están en binario) lo ejecutarían con mucho mayor rapidez de lo que ejecutan una comparación de dos llaves completas.
ORDENAMIENTO QUICKSORT
El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición, en el mundo de habla hispana.
Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.
La idea central de este algoritmo consiste en los siguiente:
Se toma un elemento x de una posición cualquiera del arreglo.
Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.
Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.
Ejemplo:
A: 15,67,08,16,44,27,12,35
Se selecciona A[i] x=15
Primera pasada (DER-IZQ)
A[8] >= x 35 >= 15 No hay intercambio
A[7] >= x 12 >= 15 Si hay intercambio
A: 12,67,08,16,44,27,15,35
(IZQ-DER)
A[2] < = X 67 < = 15 Si hay intercambio
A:12,15,08,16,44,27,67,35
2da. Pasada (DER-IZQ)
A[6] >= x 27 >= 15 No hay intercambio
A[5] >= x 44 >= 15 No hay intercambio
A[4] >= x 16 >= 15 No hay intercambio
A[3] >= x 08 >= 15 Si hay intercambio
A: 12,08,15,16,44,27,67,35
Como el recorrido de izquierda a derecha debería iniciarse en la misma posición
donde se encuentra el elemento x, el proceso se termina ya que el elemento x, se
encuentra en la posición correcta.
A: 12, 08, 15, 16, 44, 27, 67, 35
1er 2do Conjunto
Conjunto
16, 44, 27, 67, 35
x16
(DER-IZQ)
A[8]>=x No hay intercambio
A[7]>=x No hay intercambio
A[6]>=x No hay intercambio
A[5]>=x No hay intercambio
A: 12, 08, 15, 16, 44, 27, 67, 35
xß44
(DER-IZQ)
A[8]>= x Si hay intercambio
A: 12, 08, 15, 16, 35, 27, 67, 44
(IZQ-DER)
A[6] < = x No hay intercambio
A[7] < = x Si hay intercambio
12, 08, 15, 16, 35, 27, 44, 67
12, 08, 15, 16, 35, 27, 44, 67
35, 27, 44, 67
xß35
(DER-IZQ)
A[8] >= x No hay intercambio
A[7] >= x No hay intercambio
A[6] >= x Si hay intercambio
12, 08, 15, 16, 27, 35, 44, 67
12,08
xß12
(DER-IZQ)
A[2]>=x Si hay intercambio
EL VECTOR ORDENADO:
08,12,15,16,27,35,44,67
Análisis
Diversos estudios realizados sobre el comportamiento del mismo demuestran que si se escoge en cada pasada el elemento que ocupa la posición central del conjunto de datos a analizar, el número de pasadas necesarias para ordenar es del orden de Log n. Respecto al número de comparaciones, si el tamaño del arreglo es una potencia de 2, en la primera pasada realizará (n-1) comparaciones, en la 2ª pasada realizará (n-1)/2 comparaciones, pero en 2 conjuntos diferentes, en la tercera pasada realizará (n-1)/4 comparaciones pero en 4 conjuntos diferentes y así sucesivamente.
Por lo tanto: C = (n-1) + 2(n -1)/2 + 4(n - 1)/4 + ....... + (n - 1)(n - 1)/(n - 1)
Lo cual es lo mismo que: C= (n - 1) + (n- 1) + ....... + (n - 1)
ORDENAMIENTO SHELLSORT
El método Shell (en honor a su descubridor) mejor del método de inserción simple ordenando subarrreglos del arreglo original en forma separada. Para crear estos nuevos subarreglos, se toman elementos saltados del areglo original en relación a incrementos predeterminados.
Por ejemplo suponiendo un arreglo X, y tomando un incremento (salto) igual a 5, se generarían los siguientes subarreglos:
Subarreglo 1: | X[0] X[5] X[10] ... |
Subarreglo 2: | X[1] X[6] X[11] ... |
Subarreglo 3: | X[2] X[7] X[12] ... |
Subarreglo 4: | X[3] X[8] X[13] ... |
etc. |
Con un salto igual a 3 se obtendrían:
Subarreglo 1: | X[0] X[3] X[6] ... |
Subarreglo 2: | X[1] X[4] X[7] ... |
Subarreglo 3: | X[2] X[5] X[8] ... |
Subarreglo 4: | X[3] X[6] X[9] ... |
etc. |
Lo habitual es tomar un valor de incremento, y ordenar mediante inserción los subarreglos obtenidos. Luego se toma otro valor de incremento, y se ordenan ahora los asubarreglos generados a partir de este incremento. Y así sucesivamente para diferentes valores de incremento o salto.
Supongamos que tenemos el siguienmte arreglo:
25 | 57 | 48 | 37 | 12 | 92 | 86 | 33 |
y que se elige la secuencia de incrementos (5,3,1), los archivos a ordenar para esta secuencia serían:
con incremento = 5:
(x[0], x[5]) |
(x[1], x[6]) |
(x[2], x[7]) |
(x[3]) |
(x[4]) |
con incremento = 3:
(x[0], x[3], x[6]) |
(x[1], x[4], x[7]) |
(x[2], x[5]) |
con incremento = 1:
(x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7]) |
A continuación se muestra el resultado del ordenamiento Shell sobre este arreglo. Las líneas indican los subarreglos que se procesan por separado.
arreglo original | o | 25 | 57 | 48 | 37 | 12 | 92 | 86 | 33 |
paso 1 salto = 5 | o | 25 | 57 | 48 | 37 | 12 | 92 | 86 | 33 |
paso 2 salto = 3 | 25 | 57 | 33 | 37 | 12 | 92 | 86 | 48 | |
paso 3 salto = 1 | 25 | 12 | 33 | 37 | 48 | 92 | 86 | 57 | |
Arreglo ordenado | 25 | 12 | 33 | 37 | 48 | 57 | 86 | 92 | |
Habitualmente lo que se hace es generar un arreglo que contenga los incrementos. Suponiendo que se tiene un arreglo con los incrementos, a continuación se muestra un ejemplo del método Shell en el siguiente fragmento de código en C:
.
.
.
int X[n]; /* será el número de elementos del arreglo */
int i,j,K /* K será el elemento que se inserte para mantener el orden */
int incre[numinc]; /* incre contiene la secuencia de incrementos,
y numinc es el número total de incrementos */
int salto, numi;
.
.
.
for (numi=0;numi<numinc;numi++)
{
salto = incre[numi]; /* salto es el incremento actual */
for (j=salto;j<n;j++)
{
K=X[j];
for(i=j-salto;i>=0&&K<X[i];i-=salto)
{
X[i+salto]=X[i];
X[i]=K;
}
}
}
No hay comentarios:
Publicar un comentario