public class Ordinamenti_Applicati_Alle_Liste {
  
  /* ******************************************************
       metodi di ordinamento applicati alle Liste semplici
     ****************************************************** */
  /* *** INSERTION SORT (ovvero "ordininiamo le carte") ****
     La "carta" da inserire è la i-esima (dalla 2nda in poi),
     il "mazzo" ordinato è quello scandito da j.
     Filosofia di ordinamento:
     "per ogni carta i-esima da inserire, si cerca la
      sua giusta posizione all'interno del mazzo confrontandola
      con le carte già ordinate: finchè la carta i-esima è >= alla
      carta j-esima del mazzo si continua a scorrere; altrimenti
      si inserisce la carta tra la j-esima e la precedente."
     <<Cicli nella stessa direzione>>
     Ciclo esterno [i]: dal 2° nodo -> n
     Ciclo interno [j]: dal 1° nodo -> i - 1 (Dati[i] >= Dati[j])
  */
  public void insertionSort(DLList l) {
    Nodo i, j, previ, prevj, tmp;
    
    for (i = l.getHead().getNext(), previ = l.getHead();
         i != null; previ = i, i = i.getNext()) {
  
      for (j = l.getHead(), prevj = null;
           j != i && (i.getInfo() >= j.getInfo());
           prevj = j, j = j.getNext());
      
        if (i.getInfo() < j.getInfo()) {
          //taglia e incolla
          tmp = i;
          previ.setNext(i.getNext());
          if (prevj == null) {
            tmp.setNext(l.getHead());
            l.setHead(tmp);
          }
          else {
            prevj.setNext(tmp);
            tmp.setNext(j);
          }
        }
    }
  }
    
  /* *** SELECTION SORT (ovvero "seleziona il minore")
     Filosofia di ordinamento:
     "prendi ogni elemento i-esimo come potenziale minore
      della lista, se ne trovi uno più piccolo rimpiazzalo"
     <<Cicli nella stessa direzione>>
     Ciclo esterno [i]: Dal 1° nodo al penultimo (n-1)
     Ciclo interno [j]: Dal nodo i-esimo+1 all'ultimo.  
  */
  public void selectionSort(DLList l) {
    Nodo i, j, least;
    for (i = l.getHead(); i.getNext() != null; i = i.getNext()) {
      for (j = i.getNext(), least = i; j != null; j = j.getNext())
        if (j.getInfo() < least.getInfo())
          least = j;
      if (least != i) swap(i, least);
    }
  }
  
  /* *** BUBBLE SORT (ovvero "porta a galla il minore")
     In questo caso, si dovrebbe chiamare
     "porta a fondo il maggiore".
     <<Cicli in direzione contraria>>
     Ciclo esterno [i]: Dall'ultimo nodo al 2°
     Ciclo interno [j]: Dal 1° nodo all'i-esimo-1
  */
  
  public void bubbleSort(DLList l){
    for(int i = l.getSize(); i > 1; i--){
      int cnt = 1;
      for(Nodo j = l.getHead(); cnt < i; cnt++, j = j.getNext())
        if(j.getInfo() > j.getNext().getInfo())
          swap(j, j.getNext());
    }
  }
  
  //swap per Selection e Bubble
  private void swap(Nodo a, Nodo b) {
    int tmp = a.getInfo();
    a.setInfo(b.getInfo());
    b.setInfo(tmp);
  }
  
}

//Mini lista adatta all'esercizio
class DLList {
  protected Nodo head;
  protected int size;
  public DLList() {
    head = null;
    size = 0;
  }
  public Nodo getHead() {
    return head;
  }
  public void setHead(Nodo n) {
    head = n;
  }
    
  public boolean IsEmpty() {
    return (head == null);
  }
  
  public int getSize() {
    return size;
  }
  
  public void insertHead(int val) {
    head = new Nodo(val, head);
    size++;
  }
  public void print() {
    for (Nodo aux = head; aux != null; aux = aux.getNext())
      System.out.print(aux.getInfo() + "\t");
    System.out.println();
  }
}

class Nodo {
  private int info;
  private Nodo next;
  //costruttori
  public Nodo(int val) {this(val, null);}
  public Nodo(int val, Nodo n) {
    info = val;
    next = n;
  }
  //metodi pubblici
  public void setInfo(int val) {info = val;}
  public int getInfo() {return info;}
  
  public void setNext(Nodo n) {next = n;}
  public Nodo getNext() {return next;}  
}