El problema de la ordenación de un conjunto de datos según un cierto criterio es uno de los más utilizados dentro del proceso de datos, y está ampliamente estudiado en la bibliografía.
Los métodos de ordenación externos se ocupan de estudiar la problemática especifica que comporta el hecho de tener los datos a ordenar almacenados en memoria auxiliar, como es el caso de los ficheros, sobre todo en el caso de ficheros secuenciales. (Isabel Gallego Férnandez y Manuel Medina Linas).
Existen tipos de ordenamiento entre ellos tenemos:
Ordenamiento Burbuja
Consiste en comparar pares de elementos adyacentes e intercambiarlos en el caso de que no estén bien situados según el criterio de ordenación utilizado. Para cada pasada del algoritmo conseguimos que el elemento menor, si la ordenación es creciente, suba como una burbuja hasta su lugar definitivo, pasando de esta forma a engrosar en un elemento el subconjunto ordenado. El método prosigue hasta que el subconjunto desordenado no consta de ningún elemento. (Isabel Gallego Férnandez y Manuel Medina LLinás).
Ordenamiento Inserción
Consiste en dividir el conjunto de datos a ordenar en dos subconjuntos que corresponden, respectivamente, al subconjunto de datos ya ordenados y el subconjunto que contiene los datos pendientes de ordenar. Cada paso del algoritmo consiste en incrementar en un elemento el subconjunto ordenado y decrementar el desordenado, hasta que todos los elementos pertenezcan al subconjunto ordenado y el subconjunto desordenado esté vacío (Isabel Gallego Férnandez y Manuel Medina Llinás).
Ordenamiento Selección
Consiste también en dividir el conjunto de datos a ordenar en dos subconjuntos, el ordenado y el que todavía está desordenado. En cada pasada, el algoritmo selecciona el elemento que cumple el criterio de ordenación(creciente o decreciente) del subconjunto desordenado y lo coloca en el subconjunto ordenado. El algoritmo prosigue hasta que el subconjunto desordenado no consta de ningún elemento.(Isabel Gallego Férnandez y Manuel Medina Llinás).
Ordenamiento QuickSort
Es también un método de ordenación basado en el intercambio, pero en este caso los intercambios no se realizan entre elementos adyacentes, sino distanciados lo más posible.El método Quicksort está basado en la idea de partir el vector en dos particiones delimitadas por un elemento "central" tales que, al final del tratamiento de una partición, la partición izquierda contenga solo elementos menores Al "central" y la derecha mayores al "central". El método consiste en realizar particiones de las particiones hasta que consten de un solo elemento (Isabel Gallego Férnandez y Manuel Medina Llinás).
Ordenamiento Shell
Consiste en ordenar el vector mediante la ordenación de subvectores. Cada subvector se construye mediante aquellos elementos que distan entre sí una constante, empezando por los mas distantes hasta llegar al vector compuesto por los elementos que distan una posición, es decir, todo el vector. Por esta razón, al método se Shell se le denomina también método de inserción con incrementos decrecientes. (Isabel Gallego Férnandez y Manuel Medina Llinás).
CLASE ORDENAMIENTOS
package practica1;
import java.util.Random;
public class ordenamiento {
int max = 100;
int vector[] = new int[max];
public void generar(int tamanio) {
for (int i = 0; i < tamanio; i++) {
Random rd = new Random();
vector[i] = rd.nextInt(20);
}
}
public void mostrar(int tamanio) {
for (int i = 0; i < tamanio; i++) {
System.out.println("Vector [" + i + "] = " + vector[i]);
}
}
public void Intercambiar(int vector[], int i, int j) {
int aux;
aux = vector[j];
vector[j] = vector[i];
vector[i] = aux;
}
public void ordenamientoBurbuja(int tamanio) {
for (int i = 0; i < tamanio; i++) {
for (int j = 0; j < 10; j++) {
Intercambiar(vector, i, j);
}
}
}
public void ordenamientoInsercion(int tamanio) {
int aux, i, j;
for (i = 0; i < tamanio; i++) {
j = i;
aux = vector[i];
while (j > 0 && aux < vector[j - 1]) {
vector[j] = vector[j - 1];
j--;
}
vector[j] = aux;
System.out.println(vector[j]);
for (int k = 0; k < tamanio; k++) {
System.out.print(" "+vector[k]);
}
System.out.println(" i "+i);
}
}
public void ordenamientoShell(int tamanio) {
int j, l, aux;
int k;
k = ( tamanio / 2);
while (k > 0) {
for (int i = k; i < tamanio; i++) {
j = i - k;
while (j >= 0) {
l = j + k;
if (vector[j] <= vector[i]) {
j--;
} else {
aux = vector[j];
vector[j] = vector[i];
vector[i] = aux;
}
}
}
k = k / 2;
}
}
public void ordenamientoQuicksort(int vector[], int primero, int ultimo) {
int aux;
int i = primero;
int j = ultimo;
int pivote = vector[(primero + ultimo) / 2];
while (i <= j) {
while (vector[i] < pivote) {
i++;
}
while (vector[j] > pivote) {
j--;
}
if (i <= j) {
aux = vector[i];
vector[i] = vector[j];
vector[j] = aux;
i++;
j--;
}
}
if (primero < j) {
ordenamientoQuicksort(vector, primero, j);
}
if (i < ultimo) {
ordenamientoQuicksort(vector, i, ultimo);
}
}
public void ordenamientoSeleccion(int tamanio) {
int i, j, posicion, menor;
for (i = 0; i < tamanio; i++) {
menor = vector[i];
posicion = i;
for (j = i + 1; j < tamanio; j++) {
if (vector[j] < menor) {
menor = vector[j];
posicion = j;
}
}
if (posicion != i) {
Intercambiar(vector, i, posicion);
}
}
}
}
CLASE MAIN
package practica1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Vector;
/**
*
* @author luz
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Ingrese el tamanio del vector : ");
String tamanioo = br.readLine();
int tamanio = Integer.parseInt(tamanioo);
ordenamiento o = new ordenamiento();
o.generar(tamanio);
o.mostrar(tamanio);
System.out.println("-----Ordenamiento de burbuja----- ");
o.ordenamientoBurbuja(tamanio);
o.mostrar(tamanio);
System.out.println("-----Ordenamiento de insercion-----");
o.ordenamientoInsercion(tamanio);
o.mostrar(tamanio);
System.out.println("-----ordenamiento de shell-----");
o.ordenamientoShell(tamanio);
o.mostrar(tamanio);
System.out.println("-----ordenamiento de quicksort-----");
o.ordenamientoQuicksort(o.vector, 0, tamanio-1);
o.mostrar(tamanio);
System.out.println("-----ordenamiento de seleccion-----");
o.ordenamientoSeleccion(tamanio);
o.mostrar(tamanio);
}
}
