Algoritmos de Ordenamiento en Java
Uno de los primeros problemas que se presentan es las estructuras de datos es el ordenamiento de datos, pero afortunada mente ya existen algoritmos que realizan esta tarea.
Recorrido en InOrden No recurisivo
Esto fue algo que realmente me saco canas, no fue facil desarrollar el algoritmo realmente este algoritmo no lo hice yo, tuve otras implementaciones que realmente si se recorrian el arbol pero quedaban en ciclos infinitos, no sabia como terminar el ciclo, bueno en fin el algoritmo no encontre en internet estaba hecho en C lo traduje a java, sin embargo dejo el Pseudocodigo.
Ejemplos:
Árbol binario:Del cual se desprenden dos sub-arboles
Árbol binario de búsqueda: Cuando se ubica en un nodo todo los nodos de la derecha son mayores y todos los que estén a la izquierda son menores del nodo al que este ubicado.
Arbol Binario Balanceados: Se tiene que cumplir que el arbol debe ser binario y que la altura de los dos sub-arboles no debe ser mayor a uno.
Recorridos:
Burbuja.
Simple
Realmente consiste en comparar todos los elementos de una lista contra todos, si se cumple que uno es mayor o menor a otro, entonces los intercambia de
posición.
if(this.tamaño != 0 && this.lista != null){
long time1 = System.nanoTime();
for(int i=0; i< this.tamaño; i++){
for(int i2=0; i2<this.tamaño-1; i2++){
//Si en el que estoy es mayor al siguiente mio
if(this.lista[i2]>this.lista[i2+1]){
//Guardo el dato en una variable temporal
int voy = this.lista[i2];
//Coloco el que esta adelante mio en mi posiscion
this.lista[i2] = this.lista[i2+1];
//yo me voy para la posision a la que estaba él
this.lista[i2+1] = voy;
}
}
}
System.out.println(System.nanoTime()-time1);
}
Mejorada
En este algoritmo los elementos que se encuentran a la izquierda del que se esta comparando ya se encuentran ordenados por tal motivo ya no se van a comprar mas mientras se recorre el vector.
for(int i=0; i<this.lista.length;i++){
for(int i2=0;i2<this.lista.length;i2++){
//Si la primera iteracion en el que me paro es menor al de la segunra iteracion
if(this.lista[i]<this.lista[i2]){
//Alamaceno l de la segunda iteracion
int voy = this.lista[i2];
//la ubicacion en el de la segunda iteracion lo intercambio con la posision que estoy observado
this.lista[i2]= this.lista[i];
//intercambio
this.lista[i]= voy;
}
}
}
Insercion
Realmente lo que hace este algoritmo es comenzar a comparar desde el segundo elemento y lo comparon el anterior si es menor intercambio posisiones, luego paso al tercer elemento y los comparo con los que esta a su izquierda. Si el anterior del que estoy comparando es menor intercambio posisiones y asi sucesivamente hasta llegar al primer elemento, cuando llegue al primer elemento paso al 4 y hago lo mismo comparo los elementos a la izquierda.
Realmente son dos paso
Uno es ir aumentado la posicion de los que estoy comparando.
Dos cada vez que aumente la posicion compara el elemento de la posicion en la que estoy con la que esta a su izquierda.
int voy_en=0;
int valortemporal;
for(int i=0;i<this.lista.length;i++){
voy_en = i;
//Pongo un limite y me devuelvo comparando
for(int i2=voy_en;i2>0;i2--){
//Reviso si mi anterior es menor que yo
if(this.lista[voy_en]<this.lista[voy_en-1]){
//Intercambio me paso una casilla antes
valortemporal = this.lista[voy_en-1];
this.lista[voy_en-1] = this.lista[voy_en];
this.lista[voy_en] = valortemporal;
voy_en--;
}
}
}
Seleccion
Se basa en buscar el mínimo elemento de la lista e intercambiarlo con el primero, después busca el siguiente mínimo en el resto de la lista y lo intercambia con el segundo, y así sucesivamente.
//variable que me alamcenara la posicion el numero menor de rango que estoy recorriendo
int pos_numeromenor=0;
//la variable me almacenara el numero temporal mente para intercambiar las posiciones
int numero_temporal=0;
//Recoro el vector de izquierda a derecha
//Se recorre desde 0 hasta el penultimo por que se supone que el ultimo elemento ya esta ordenado
//por que seria el mayor
for(int i=0; i<lista.length-1;i++){
pos_numeromenor=i;
//Recorro el vector desde una posision mas a la que ya compare
//Coloco un delimitador para que no me repiza los que ya compare
for(int i2=i+1; i2<this.lista.length-1; i2++){
//Si el numero que estoy comparando es menor al numero de la posicion menor
//cambio el indice del numero menor si no lo dejo igual
pos_numeromenor = (this.lista[i2]<this.lista[pos_numeromenor]) ? i2:pos_numeromenor;
}
//si el indice del numero menos es diferente al indice del primer elemento del rango que
//estoy recorriendo intercambio las posiciones del numero que estoy recorriendo
//con el numero menor
if(pos_numeromenor!=i){
numero_temporal = this.lista[pos_numeromenor];
this.lista[pos_numeromenor]=this.lista[i];
this.lista[i]=numero_temporal;
}
}
Shell
El Shell es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:
1. El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
2. El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.
Shell propone que se haga sobre el array una serie de ordenaciones basadas en la inserción directa, pero dividiendo el array original en varios sub-arrays tales que cada elemento esté separado k elementos del anterior (a esta separación a
menudo se le llama salto o gap).
- Se debe empezar con k=n/2, siendo n el número de elementos de array, y utilizando siempre la división entera.
- Después iremos variando k haciéndolo más pequeño mediante sucesivas divisiones por 2, hasta llegar a k=1.
//Vasriable que tiene el numero de espacion entre numeros a comparae
int nsaltoscomp = this.lista.length/2;
//ALmacena el numero que estoy comparando
int valorcomparado = 0;
//Almacena el indice del numero con el que voy a comparar el valor del numero
int posnumero = 0;
while(nsaltoscomp>=1){
for(int i=nsaltoscomp; i<this.lista.length;i++){
valorcomparado = this.lista[i];
posnumero=i-nsaltoscomp;
while(posnumero>=0 && this.lista[posnumero]>valorcomparado){
//Coloco el numero mayor en la posiscion del menor comparado
this.lista[posnumero+nsaltoscomp] =this.lista[posnumero];
posnumero-=nsaltoscomp;
}
//Si intercambie posiciones anteriormente es para dejar de valorcomaprado en su nueva posicion
this.lista[posnumero+nsaltoscomp]=valorcomparado;
}
nsaltoscomp/=2;
}
Arbol Binario
- Esta compuesto por nodos
- Cada nodo puede tener maximo dos hijos, uno al aldo izquierdo y otro al lado derecho.
- El nodo del lado izquierdo debe ser menor o igual al nodo padre
- El nodo del lado derecho debe ser mayor o igual al nodo padre
Los arboles binarios tiene los siguiente atributos.
- Padre: Es el nodo anterior en el que se esta iterando, es decir si se esta en el nodo con valor 9 su padre seria el 10, si se esta en el nodo con valor 5 su padre seria nulo
- Hijo Derecho: Es el nodo enlazado mayor al que se esta iterando.
- Hijos Izquierdo: Es el nodo enlazado menor en que se esta iterando.
- Llave:Valor numerico en el cual se organiza el arbol, en el caso de la imagen son los numeros que aparecen.
- Valor:Puede ser la misma llave, o un Objecto que contega el nodo.
- Profundidad: Es el numero máximo de niveles del árbol, es decir en el caso de la imagen seria una árbol de 4 niveles ya que hay 4 nodos desde el raiz hasta el ultimo que es 9. Este atributo sera utilizando para el numero maximo-1 de iteraciones que se utilizara para recorrer el arbol.
Para implementarlo en java utilice dos clases una clase nodo y otra clase llamada arbol, la clase nodo solo trendra como atributos el nodo hijo derecho e izquierdo, nodo papa y el valor, ya en la clase Arbol es la que se encargara de hacer la logica de ordenar los datos.
package Ordenamiento;
public class Arbol {
private Nodo raiz;
private int[] listaordenada;
private int indice;
public Arbol(){
}
public Nodo getRaiz() {
return raiz;
}
public void setRaiz(Nodo raiz) {
this.raiz = raiz;
}
public void addNodo(int valor){
Nodo nodotmp = new Nodo(valor);
this.addNodoRecursivo(nodotmp, this.raiz);
}
private void addNodoRecursivo(Nodo elnodo, Nodo padre){
//Verificamos si es el primer nodo que se va a gregar
if(padre != null){
//Reviso si va para la izquierda o derecha
if(padre.getValor() >= elnodo.getValor()){
//Si no es nulo tengo que volver a hacer las validaciones por eso se veulve recursivo
if(padre.getHijoIzq() != null){
addNodoRecursivo(elnodo,padre.getHijoIzq() );
}else{
//como es nulo quiere decir que no tiene hijos ahora el nodo va ser su hijo
padre.setHijoIzq(elnodo);
}
}else{
if(padre.getHijoDer() != null){
addNodoRecursivo(elnodo, padre.getHijoDer());
}else
padre.setHijoDer(elnodo);
}
}else{
this.raiz = elnodo;
}
}
public void setLista(int[] lista){
///agrega la lista al arbol
this.listaordenada = new int[lista.length];
for(int i=0; i<lista.length;i++){
this.addNodo(lista[i]);
}
}
private void recorreEnOrdern(Nodo inicio){
if(inicio != null){
recorreEnOrdern(inicio.getHijoIzq());
this.listaordenada[indice]=inicio.getValor();
//System.out.println(inicio.getValor());
this.indice++;
recorreEnOrdern(inicio.getHijoDer());
}
}
public int[] getLista(){
this.recorreEnOrdern(this.raiz);
return this.listaordenada;
}
}
package Ordenamiento;
public class Nodo {
private Nodo hijoIzq;
private Nodo hijoDer;
private Nodo padre;
private int valor;
public Nodo(int valor){
this.valor=valor;
}
public Nodo getHijoIzq() {
return hijoIzq;
}
public void setHijoIzq(Nodo hijoIzq) {
this.hijoIzq = hijoIzq;
}
public Nodo getHijoDer() {
return hijoDer;
}
public void setHijoDer(Nodo hijoDer) {
this.hijoDer = hijoDer;
}
public Nodo getPadre() {
return padre;
}
public void setPadre(Nodo padre) {
this.padre = padre;
}
public int getValor() {
return valor;
}
}
Esto fue algo que realmente me saco canas, no fue facil desarrollar el algoritmo realmente este algoritmo no lo hice yo, tuve otras implementaciones que realmente si se recorrian el arbol pero quedaban en ciclos infinitos, no sabia como terminar el ciclo, bueno en fin el algoritmo no encontre en internet estaba hecho en C lo traduje a java, sin embargo dejo el Pseudocodigo.
Nodo elnodo = this.raiz;
//Pila para guardar los padres
PilaLista p = new PilaLista();
//Variable utilizada para cuado se encuentren todos los izquierdos
//y se devuelva y llegue a la raiz pasar a revisar los derechos y realizar nuevemente los pasos
Boolean derecha=true;
while(elnodo != null){
while(elnodo != null){
p.put(elnodo);
elnodo = elnodo.getHijoIzq();
}
elnodo = (Nodo)p.pop();
derecha = true;
while(elnodo != null && derecha){
System.out.println(elnodo.getValor());
if (elnodo.getHijoDer() != null) {
elnodo = elnodo.getHijoDer();
derecha= false;
}else{
//Si esta vacia quiere decir que ya recorrimos todo los nodos
//Se podira quitar este if implmentando en la lista para que cuando no hallan mas
//elementos en la pila devuelva un null y asi evitarlo
if(p.vacia()){
elnodo = null;
}else{
elnodo = (Nodo)p.pop();
}
}
}
}
Ejemplos:
- En las carpetas de un sistema operativo, cada directorio
- En el manejo de menú del un software
Tipos de nodos:
- Nodo raiz: Es el primero
- Nodo hermano
- Nodo hijo:Son nodos que se desprenden otros
- Nodo padre:Es el nodo del cual se desprender otros
- Nodo hojas: De ellos no se desprende otro nodo, son los elementos finales
Altura de un árbol: Depende de la cantidad de nodo que tengan, los últimos nodos equivalen a atura 0
Caminos: Secuencia de un Nodo a otro
Árbol binario de búsqueda: Cuando se ubica en un nodo todo los nodos de la derecha son mayores y todos los que estén a la izquierda son menores del nodo al que este ubicado.
Arbol Binario Balanceados: Se tiene que cumplir que el arbol debe ser binario y que la altura de los dos sub-arboles no debe ser mayor a uno.
Recorridos:
- In-Orden: recorre primero el nodo luego el sub-arbol izquierdo y por ultimo el sub-arbol derecho
- Pre-orden: Recorre primero el sub-arbol izquierdo luego el nodo raiz y por ultimo el sub-arbol izquierdo
- Post-orden: recorre el sub-arbol izquierdo luego el sub-arbol derecho y por ultimo el nodo raiz.
Algoritmo de búsqueda binaria
Se tiene una condición, que el array este ordenado.
Paso1: Toma la cantidad(tamaño) elementos que hay y se divide sobre dos
Paso 2: Cogo el elemento de del indice de la divicion anterior y comparo si ese elemento es menos a elemento que estoy buscando
Paso 3: Si se cumple cojo lo elementos que esta después del elemento que se obtiene con la divicion del primer paso