AlvaroMalenoalferez
Algoritmo de ordenacion mediante barrido Pivotante
Suponiendo que en una recta los numeros se ordenan de menor a mayor, y, que por tanto
se podria considerar ordenado todo aquel conjunto numerico tal que, dispuesto sobre
la recta, cada termino sea menor que el siguiente, se pueden postular varias conjeturas:
La primera es que, una vez el termino mayor este situado en ultimo lugar, se habra reducido la entropia.
La segunda es que, cuanto mas cerca esten los terminos de mayor valor del final de la recta, mas cerca del orden se hallara esta.
La tercera es que, un termino situado en su lugar correspondiente no sera necesario volverlo a ordenar.
Asi, a medida que nos movamos desde el cualquier termino de la sucesion hasta el primero, situando los menores a este
a la izquierda y, los mayores a el a la derecha de la recta, mas cerca estaremos de lograr el orden.
El siguiente algoritmo comienza por realizar un barrido rapido seleccionando como pivote el termino situado en
el ultimo lugar del conjunto numerico. Si por casualidad, este fuese el ultimo de la recta(el de mayor valor)
iniciaria una serie de barridos recursivos seleccionando como pivote cada vez el termino anterior, situando
a su izquierda a los de menor valor y, a su derecha aquellos cuyo valor es superior. Una vez realizada una primera
reorganizacion de los terminos, pasa a comprobarse su ordenacion para seleccionar como nuevo pivote aquel numero que
se encuentre fuera de lugar para situar a sus menores a la izquierda y a sus mayores a la derecha.
El barrido se repite hasta que la sucesion se encuentre finalmente ordenada.
Autor: ElMirloBlanco
public class QuickBarrido{
//Este metodo busca un termino situado en un lugar cuyo orden es incorrecto y retorna la posicion tras la cual deberia de encontrarse.
//Si cada termino es menor al siguiente se entiende que la lista ya esta ordenada.
public int EstaOrdenada(int[] lista) {
for(int i = 0; i < lista.length ; i++) {
if(i != lista.length - 1 && lista[i] > lista[i + 1]) {
return i + 1;
}
}return -1;
}
//Esta funcion recursiva separa a derecha e izquierda los terminos de mayor y menor valor al pivote.
//En caso de no existir cambio alguno en la ordenacion, se entiende que el termino mayor esta situado
//a la derecha del todo y que sera necesaria una reestruturacion de la lista empleando como pivote el termino anterior.
//El metodo favorece que el numero de mayor valor acabe lo mas a la derecha de la recta posible.
public int[] Ordenador(int [] lista, int pivote) {
int [] listaOrd = new int [lista.length];
int correccion = 0;
int contador = 0;
//Se recorre la lista
for(int i = 0; i < lista.length; i++) {
//Si el termino es menor al pivote se situa en una nueva lista lo mas a la izquierda posible
if(lista[i] <= lista[pivote]) {
listaOrd[i - contador] = lista[i];
//Si por el contrario es mayor, se le asigna una posicion en la lista anterior o igual a la examinada que
//permita reuperarlo mas adelante sin variar el orden en el que ya esta siutado
}else {
lista[0 + contador] = lista[i];
contador += 1;
}
}
//Si se ha encontrado un numero mayor al pivote se entiende que se ha de variar el orden, agrupando todos los mayores a el a su derecha.
if(contador > 0) {
for(int i = listaOrd.length - contador; i < listaOrd.length; i++) {
listaOrd[i] = lista[correccion];
correccion += 1;
}
//En caso de ausencia de numeros mayores, se entiende que el pivote es el de mayor valor y esta situado a la derecha de sus menores.
//Se pasa a la llamada reursiva empleando como pivote el termino anterior.
//Al haber situado a la derecha de los pivotes anteriores a todos aquellos terminos mayores la probabilidad de que el pivote siguiente
//sea el mayor a todos los situados a la izquierda aumenta
}else{
//El ciclo pasa a considerar si cada numero esta situado a la derecha de todos aquellos que son menores a else {
//Mediante barridos sucesivos la lista estara ordenada
while(pivote != 0) {
listaOrd = Ordenador(listaOrd, pivote - 1);
pivote = pivote - 1;
}
}
return listaOrd; }//Fin del metodo Ordenador
//Para evitar el clasico error recursivo que copa la memoria(stack overflow) se separan los
//procesos, evitando que la funcion recursiva se llame demasiadas veces antes de estar ordenada
public int [] LlamaAlOrden(int [] lista) {
//Para eso, se selecciona como primer pivote el ultimo numero de la lista sin ordenar
int pivote = lista.length - 1;
//Despues se establece un ciclo en el que se llama al metodo ordenador sucesivas veces empleando como pivote
//el termino que esta mal situado y que encontramos mediante la funcion que revisa el orden numero por numero.
do{
lista = Ordenador(lista, pivote);
pivote = EstaOrdenada(lista);
}while(pivote != -1);
return lista; }//Cuando cada termino es menor al siguiente la lista esta ordenada
}