insert
sort
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) o cuando ya no se encuentran
elementos (todos los elementos fueron desplazados y este es el más pequeño). En
este punto se inserta el elemento k+1 debiendo desplazarse
los demás elementos.
Este método de ordenamiento es muy similar al Bubble Sort, con la diferencia que éste es más eficiente ya que reduce las comparaciones entre los elementos. Un elemento es comparado con cada elemento anterior, hasta que se encuentra un elemento más pequeño. Es decir, si un elemento contiene un valor menor que todos los elementos anteriores, compara ese elemento con todos los elementos anteriores antes de continuar con la siguiente comparación. Aunque éste algoritmo es más eficiente que el Bubble Sort, es ineficiente comparado con otros algoritmos de ordenamiento. Pero indudablemente Insertion Sort es una buena elección de método de ordenamiento para listas pequeñas de 30 elementos o menos.
referencias:
CODIGO, Facilito. Ordenamiento Por Inserción (insertion
Sort) En Java . [LINEA]. Youtube. 27 marzo 2012. [Citado en 29 de Septiembre de
2015]. Disponible en internet:
<https://www.youtube.com/watch?v=o4iuk9vhqys>
------------------- leido el 29 septiembre de 2015
LISTAS DOBLES
(INSERTSORT)
INTRODUCCIÓN
Las listas doblemente enlazadas pueden ser utilizadas cuando son necesarias varias operaciones de inserción o eliminación de elementos.
Las listas doblemente enlazadas pueden ser utilizadas cuando son necesarias varias operaciones de inserción o eliminación de elementos.
DEFINICIÓN
En cambio, en relación a la listas enlazada simple el enlace entre los elementos se hace gracias a dos punteros (uno que apunta hacia el elemento anterior y otro que apunta hacia el elemento siguiente).
El puntero anterior del primer elemento debe apuntar hacia NULL (el inicio de la lista).
El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).
Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos: comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento; comenzando por el final, el puntero anterior permite el desplazamiento hacia el elemento anterior.
OPERACIONES
BÁSICAS CON LISTAS DOBLEMENTE ENLAZADAS
Añadir o insertar elementos.
Buscar o localizar elementos.
Borrar elementos.
Moverse a través de la lista, siguiente y anterior.
CÓDIGO
LISTAS DOBLES (INSERTSORT)
public void insertSort(){
node q, aux;//declaramos los nodos
if(this.head.getNext()!=null){//verificar si los nodos
estan ahii
node p = this.head.getNext();//p = en la parte sigiente
de la cabeza
while (p!=null){// verificamos si cumple la condicion
if(p.getVal()<p.getBack().getVal()){// si parte valor
es menor ala parte anterior
entoncesqueda normal
aux = p;//auxiliar queda igual a p
q = p.getBack();//q queda igual parte siguiente de p
q.setNext(p);
if(p!= null){// para que no siga recorriendo
p.setBack(q);
}
aux.setBack(null); busca la posicion y la elimina
aux.setNext(null);
//q es mayor que
AUX y difernte de nulo
while(q.getVal()>aux.getVal() &&
q.getBack()!=null){
q = q.getBack();
}
// q debe ser menor igual al auxiliar para cuando se
encuentre el mismo numero no se caiga el programa
aux.setNext(q.getNext());
aux.setBack(q);
q.getNext().setBack(aux);
}else{
q.setBack(aux);
this.head = aux;
}
}else{
p=p.getNext();
}
}
}
