como crear una lista doble con insert sort y shaker sort

Las listas doblemente enlazadas son estructuras de datos semejantes a las listas enlazadas simples.

La asignación de memoria es hecha al momento de la ejecución.

las listas doblemente enlazadas a diferencia de la listas simples, contienen dos punteros. uno que apunta la nodo siguiente y el otro apunta al nodo anterior

¿que es 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.

este algoritmo consiste en ir escogiendo cada número  y compararlo con el anterior de derecha a izquierda, si el número  de la derecha es mayor que el de la izquierda entonces los números cambiaran de lugar hasta que  el arreglo se encuentre completamente ordenado.

imagen tomada de wikipedia

 

código de ordenamiento insert sort arreglos:

este código se realizo en netBeans 8.2

package ejemplometododeinsercion;

import java.util.Scanner;

import javax.swing.JOptionPane;

public class EjemploMetodoDeInsercion {

  

    public static void main(String[] args) {

       

        Scanner entrada = new Scanner(System.in);

        int arreglo[];

        int nElementos, pos, aux;

        nElementos = Integer.parseInt(JOptionPane.showInputDialog("INGRESE EL NUMERO DE ELEMENTOS: "));

        arreglo = new int[nElementos];

        System.out.print("DIGITE EL ARREGLO: \n");

        for (int i = 0; i < nElementos; i++) {

            System.out.print((i + 1) + ".DIGITE UN NUMERO: ");

            arreglo[i] = entrada.nextInt();

        }

        //ORDENAMIENTO POR INSERCION

        for (int i = 0; i < nElementos; i++) {

            pos = i;

            aux = arreglo[i];

            while ((pos > 0) && (arreglo[pos - 1] > aux)) {

                arreglo[pos] = arreglo[pos - 1];

                pos--;

            }

            //ACTUALIZAR EL NUMERO 

            arreglo[pos] = aux;

        }

        System.out.print("\nORDEN ASCENDENTE: ");

        for (int i = 0; i < nElementos; i++) {

            System.out.print(arreglo[i] + " , ");

        }

        System.out.print("");

        System.out.print("\nORDEN DESENDENTE: ");

        for (int i = (nElementos - 1); i >= 0; i--) {

            System.out.print(arreglo[i] + " , ");

        }

        System.out.print("");

    }

}

código de ordenamiento por insert sort para listas dobles

 public void InserSort(){
       nodo p = this.cab.getSig();  // nodo p se ubica un posición después de la cabeza
       nodo m = p.getSig();         //nodo m se ubica una posición después de nodo p
   
       while(p != null){   //si la lista no esta vacía que entre a ordenar
       
          while(p.getAnt().getId > p.getId()  && p.getAnt() != null){   //p en posición anterior en mayor a ID y si p en su posición anterior es diferente de null p sera igual a la posición anterior
           
                p = this.exchange(p.getAnt(), p);  // se llama al método exchange para mover los nodos
             }  //el proceso se repite hasta que p ya no tenga datos los cuales intercambiar
          }
          p = m;  // p y m sseran iguales cuando se haya terminado todo el intercambio de datos
          if(p != null)
       
     
    }