Ordenamiento de Burbuja
La Ordenación de burbuja funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.
Ejemplo
// Ordenamiento de los valores de un arreglo en orden ascendente.
import java.awt.*;
import javax.swing.*;
public class Burbuja extends JApplet {
// inicializar subprograma
public void init()
{
JTextArea areaSalida = new JTextArea();
Container contenedor = getContentPane();
contenedor.add( areaSalida );
int arreglo[] = { 90, 16, 1, 8, 100, 1, 819, 60, 5, 37 };
String salida = "Elementos de datos en su orden original\n";
// anexar los valores originales al String salida
for ( int contador = 0; contador < arreglo.length; contador++ )
salida += " " + arreglo[ contador ];
ordenamBurbuja( arreglo ); // ordenar arreglo
salida += "\n\nElementos de datos en orden ascendente\n";
// anexar los valores ordenados del arreglo al String salida
for ( int contador = 0; contador < arreglo.length; contador++ )
salida += " " + arreglo[ contador ];
areaSalida.setText( salida );
} // fin del método init
// ordenar elementos del arreglo con el método burbuja
public void ordenamBurbuja( int arreglo2[] )
{
// ciclo para controlar número de pasadas
for ( int pasada = 1; pasada < arreglo2.length; pasada++ ) {
// ciclo para controlar número de comparaciones
for ( int elemento = 0; elemento < arreglo2.length - 1; elemento++ ) {
// comparar elementos uno a uno e intercambiarlos si
// el primer elemento es mayor que el segundo
if ( arreglo2[ elemento ] > arreglo2[ elemento + 1 ] )
intercambiar( arreglo2, elemento, elemento + 1 );
} // fin del ciclo para controlar las comparaciones
} // fin del ciclo para controlar las pasadas
} // fin del método ordenamBurbuja
// intercambiar dos elementos de un arreglo
public void intercambiar( int arreglo3[], int primero, int segundo )
{
int almacen; // área temporal de almacenamiento para intercambiar
almacen = arreglo3[ primero ];
arreglo3[ primero ] = arreglo3[ segundo ];
arreglo3[ segundo ] = almacen;
}
} // fin de la clase Burbuja
import javax.swing.*;
public class Burbuja extends JApplet {
// inicializar subprograma
public void init()
{
JTextArea areaSalida = new JTextArea();
Container contenedor = getContentPane();
contenedor.add( areaSalida );
int arreglo[] = { 90, 16, 1, 8, 100, 1, 819, 60, 5, 37 };
String salida = "Elementos de datos en su orden original\n";
// anexar los valores originales al String salida
for ( int contador = 0; contador < arreglo.length; contador++ )
salida += " " + arreglo[ contador ];
ordenamBurbuja( arreglo ); // ordenar arreglo
salida += "\n\nElementos de datos en orden ascendente\n";
// anexar los valores ordenados del arreglo al String salida
for ( int contador = 0; contador < arreglo.length; contador++ )
salida += " " + arreglo[ contador ];
areaSalida.setText( salida );
} // fin del método init
// ordenar elementos del arreglo con el método burbuja
public void ordenamBurbuja( int arreglo2[] )
{
// ciclo para controlar número de pasadas
for ( int pasada = 1; pasada < arreglo2.length; pasada++ ) {
// ciclo para controlar número de comparaciones
for ( int elemento = 0; elemento < arreglo2.length - 1; elemento++ ) {
// comparar elementos uno a uno e intercambiarlos si
// el primer elemento es mayor que el segundo
if ( arreglo2[ elemento ] > arreglo2[ elemento + 1 ] )
intercambiar( arreglo2, elemento, elemento + 1 );
} // fin del ciclo para controlar las comparaciones
} // fin del ciclo para controlar las pasadas
} // fin del método ordenamBurbuja
// intercambiar dos elementos de un arreglo
public void intercambiar( int arreglo3[], int primero, int segundo )
{
int almacen; // área temporal de almacenamiento para intercambiar
almacen = arreglo3[ primero ];
arreglo3[ primero ] = arreglo3[ segundo ];
arreglo3[ segundo ] = almacen;
}
} // fin de la clase Burbuja
Ordenamieto Burbuja Bidireccional
El ordenamiento de burbuja bidireccional es un algoritmo de ordenamiento que surge como una mejora del algoritmo ordenamiento de burbuja.
La manera de trabajar de este algoritmo es ir ordenando al mismo tiempo por los dos extremos del vector. De manera que tras la primera iteración, tanto el menor como el mayor elemento estarán en sus posiciones finales. De esta manera se reduce el número de comparaciones.
La manera de trabajar de este algoritmo es ir ordenando al mismo tiempo por los dos extremos del vector. De manera que tras la primera iteración, tanto el menor como el mayor elemento estarán en sus posiciones finales. De esta manera se reduce el número de comparaciones.
Ejemplo
public class Burbuja2 {
public static int izquierda,derecha,ultimo;
public static int izquierda,derecha,ultimo;
//variables para ordenamiento
public static int arreglo[] = {10,23,6,4,223,2,112,3,6,34};
public static int arreglo[] = {10,23,6,4,223,2,112,3,6,34};
// inicializamos el arreglo
public static void main(String[] args) {
izquierda = 1;
derecha = arreglo.length;
ultimo = arreglo.length-1;
do{
for(int i=arreglo.length-1;i>0;i--){
//Burbuja hacia la izquierda
//Los valores menores van a la izquierda
if(arreglo[i-1] > arreglo[i]){
int aux = arreglo[i];
public static void main(String[] args) {
izquierda = 1;
derecha = arreglo.length;
ultimo = arreglo.length-1;
do{
for(int i=arreglo.length-1;i>0;i--){
//Burbuja hacia la izquierda
//Los valores menores van a la izquierda
if(arreglo[i-1] > arreglo[i]){
int aux = arreglo[i];
// variable auxiliar para poder hacer intercambio de posicion
arreglo[i] = arreglo[i-1];
arreglo[i-1] = aux;
ultimo = i;
}
}
izquierda = ultimo+1;
for(int j=1;j<arreglo.length;j++){
if(arreglo[j-1] > arreglo[j]){
int aux = arreglo[j];
arreglo[j] = arreglo[j-1];
arreglo[j-1] = aux;
ultimo = j;
}
}
derecha = ultimo-1;
}while(derecha >= izquierda);
for(int i=0;i<arreglo.length;i++){
System.out.println(arreglo[i]);
}
}
}
arreglo[i] = arreglo[i-1];
arreglo[i-1] = aux;
ultimo = i;
}
}
izquierda = ultimo+1;
for(int j=1;j<arreglo.length;j++){
if(arreglo[j-1] > arreglo[j]){
int aux = arreglo[j];
arreglo[j] = arreglo[j-1];
arreglo[j-1] = aux;
ultimo = j;
}
}
derecha = ultimo-1;
}while(derecha >= izquierda);
for(int i=0;i<arreglo.length;i++){
System.out.println(arreglo[i]);
}
}
}
Ordenamiento por Inserción
El ordenamiento por inserción 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.
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.
Pseudocódigo
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 Ejemplo public static void insertSort (int[] v) {
int aux;
int j;
for (int i=1; i<v.length; i++) {
j=i;
aux = v[i];
for (j=i-1; j>=0 && v[j]>aux; j--)
v[j+1] = v[j];
v[j+1] = aux;
}
} Ordenamiento por Casilleros El ordenamiento por casilleros es un algoritmo de ordenamiento que distribuye todos los elementos a ordenar entre un número finito de casilleros. Cada casillero sólo puede contener los elementos que cumplan unas determinadas condiciones. Las condiciones deben ser excluyentes entre sí, para evitar que un elemento pueda ser clasificado en dos casilleros distintos. Después cada uno de esos casilleros se ordena individualmente con otro algoritmo de ordenación (que podría ser distinto según el casillero), o se aplica recursivamente este algoritmo para obtener casilleros con menos elementos.
El algoritmo contiene los siguientes pasos:
- Crear una colección de casilleros vacíos
- Colocar cada elemento a ordenar en un único casillero
- Ordenar individualmente cada casillero
- Devolver los elementos de cada casillero concatenados por orden
Pseudocódigo función bucket-sort(elementos, n) casilleros ← colección de n listas para i = 1 hasta longitud(elementos) hacer c ← buscar el casillero adecuado insertar elementos[i] en casillero[c] fin para para i = 1 hasta n hacer ordenar(casilleros[i]) fin para devolver la concatenación de casilleros[1],..., casilleros[n]
Aquí elementos es la lista de datos a ordenar y n el número de casilleros que queremos usar. Para buscar el casillero adecuado para un elemento se puede utilizar la técnica que más convenga. Ordenamiento Shell El ordenamiento Shell es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. 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.
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.
