//package Sort;
import java.util.ArrayList;
/**
 * Title:        Sort
 * Description:  Implementazione degli algoritmi di ordinamento
 *              HeapSort, MergeSort, QuickSort, ShellSort
 * Copyright:    Copyright (c) 2000
 * Company:      Università degli Studi di Verona
 * @author Roberto Posenato
 * @version 1.0
 */

public class Sort {
  /*
  * HeapSort(Object a[]) esegue un ordinamento sul vettore a.
  * Si assume che a abbia un range in 1..lenght-1 e che gli elementi
  * di a siano oggetti che implementino l'interfaccia Comparable()
  */
  public static void HeapSort(Comparable a[]) {
    int i;
    int fine = a.length;
    Comparable temp = null;

    //heapify tutti i sottoalberi, tranne i figli della root
    //in quanto lo faccio nel ciclo d'ordinamento
    for (i=fine/2; i>1; i--)
      reheapify(a,i,fine);

    //a partire dalla root, si rimuove la radice, la si pone in fondo all'array,
    //si pone l'ultimo elemento al posto della radice e si esegue un reheapify.
    for (i=fine; i>1; i--) {
      reheapify(a,1,i);
      temp = a[0]; a[0] = a[i-1]; a[i-1] = temp;
    }
  }

  private static void reheapify(Comparable itemArray[], int currentIndex, int lastIndex) {
    int childIndex = currentIndex * 2;
    boolean notFinished = (childIndex <= lastIndex);
    Comparable itemToPlace = itemArray[currentIndex-1];

    //sposta figlio più grande rispettoa itemToPlace di un livello nell'albero
    while (notFinished) {
      if (childIndex < lastIndex) //se ci sono DUE figli, devo prendere max
        if ( ( itemArray[childIndex] ).compareTo(itemArray[childIndex-1]) > 0 )
          childIndex++; //figlio dx è maggiore
          //se elemento a childIndex è maggiore di itemToPlace
          //spostalo in currentIndex e muovi currentIndex in giù
      if ( ( itemArray[childIndex-1] ).compareTo(itemToPlace) > 0 ) {
        itemArray[currentIndex-1] = itemArray[childIndex-1];
        currentIndex = childIndex;
        childIndex = 2 * currentIndex;
        notFinished = (childIndex <= lastIndex);
      } else {
        notFinished = false;
      }
    } //ciclo while
    itemArray[currentIndex-1] = itemToPlace;
    return;
  }

  /** shellSort()
   * Ordina l'array data secondo l'algoritmo a passo calante (shellSort)
   * @param Un array di Comparable
   * @return l'array ordinato
   * @author Roberto Posenato
   * @version 1.0
  */
  public static void shellSort(Comparable data[]) {
    int i, j, k, delta, deltaCnt, increments[] = new int[20];
    Comparable tmp;
    // crea il numero corretto di incrementi delta
    for ( delta=1, i=0; delta < data.length && i < increments.length; i++) {
      increments[i] = delta;
      delta = 3* delta +1;
    }
    // itera per il numero di diversi delta
    for ( i--; i>=0; i--) {
      delta = increments[i];
      // itera per il numero di sottoarray delta-ordinati
      for ( deltaCnt=delta; deltaCnt<2*delta; deltaCnt++)  {
        // ordinamento per inserimento nel sottoarray indicizzato con passo
        //delta
        for ( j= deltaCnt; j < data.length; ) {
          tmp = data[j];
          k = j;
          while ((k-delta)>=0 && tmp.compareTo(data[k-delta]) < 0) {
            data[k] = data[k-delta];
            k -= delta;
          }
          data[k] = tmp;
          j += delta;
        }
      }
    }
  }



  /**
   * insertionSort(Comparable a[])
   * Ordina l'array data secondo l'algoritmo per inserzione.
   * @param Un array di Comparable
   * @return l'array ordinato
   * @author Roberto Posenato
   * @version 1.0
   */
  public static void insertionSort(Comparable data[]) {
    Comparable tmp;
    int i, j;
    for (i =1; i < data.length; i++) {
       tmp = data[i];
       for (j = i; j>0 && tmp.compareTo(data[j-1])<0; j--)
          data[j] = data[j-1];
       data[j] = tmp;
    }
  }

  /**
   * MergeSort(Comparable a[]) esegue un ordinamento sul vettore a.
   * Si assume che a abbia un range in 0..lenght-1 e che gli elementi
   * di a siano oggetti che implementino l'interfaccia Comparable()
   * Questa implementazione utilizza un array ausiliario per memorizzare le sequenze
   */
  public static void MergeSort(Comparable a[]) {
    int half = a.length/2+1;
    Object[] leftA  = new Object[half],
             rightA = new Object[half];
    mergeSort(a, 0, a.length-1, leftA, rightA);
  }

  private static void mergeSort(Comparable a[], int lo, int hi,
                                Object[] leftA, Object[] rightA) {
    if (lo >= hi)
      return;

    int middle = (lo + hi) / 2;

    //Partition the list into two lists and sort them recursively
    mergeSort(a, lo,       middle, leftA, rightA);
    mergeSort(a, middle+1, hi,     leftA, rightA);

    //Merge the two sorted lists
    int left = 0,
      right = 0,
      sizeL = middle - lo + 1,
      sizeR = hi - middle;

    System.arraycopy(a, lo,      leftA, 0, sizeL);
    System.arraycopy(a, middle+1,rightA,0, sizeR);

    while ( (left < sizeL) && (right < sizeR) )
        a[lo++] = ( ((Comparable)leftA[left]).compareTo(rightA[right]) <= 0 )
                  ? (Comparable)leftA[left++] : (Comparable)rightA[right++];
    while (left < sizeL)
        a[lo++] = (Comparable)leftA[left++];
    while (right < sizeR)
        a[lo++] = (Comparable)rightA[right++];
  }

  /**
   * A in-place merge sort demonstration algorithm
   * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
   *
   * @author Jason Harrison@cs.ubc.ca
   * @version 	1.1, 12 Jan 1998
  */
  private static void inPlaceMergeSort(Comparable a[], int lo, int hi) {

    if (lo >= hi)
      return;

    int mid = (lo + hi) / 2;

    //Partition the list into two lists and sort them recursively
    inPlaceMergeSort(a, lo, mid);
    inPlaceMergeSort(a, mid + 1, hi);

    //Merge the two sorted lists
    int end_lo = mid;
    int start_hi = mid + 1;
    int k;
    Object T = null;
    while ((lo <= end_lo) && (start_hi <= hi)) {
      if (a[lo].compareTo(a[start_hi]) < 0) {
        lo++;
      } else {
        /*
         *  a[lo] >= a[start_hi]
         *  The next element comes from the second list,
         *  move the a[start_hi] element into the next
         *  position and shuffle all the other elements up.
         */
        T = a[start_hi];
        for (k = start_hi - 1; k >= lo; k--)
          a[k+1] = a[k];
        a[lo] = (Comparable) T;
        lo++;
        end_lo++;
        start_hi++;
      }
    }
  }

  public static void InPlaceMergeSort(Comparable a[]) {
    inPlaceMergeSort(a, 0, a.length-1);
  }

  /**
   * QuickSort(Comparable a[]) esegue un ordinamento sul vettore a.
   * Si assume che a abbia un range in 0..lenght-1 e che gli elementi
   * di a siano oggetti che implementino l'interfaccia Comparable()
   */
  public static void QuickSort(Comparable a[]) {
    quickSort(a, 0, a.length-1);
  }

  private static void quickSort(Comparable a[], int lower, int upper) {
    if (lower<upper) {
      int pivotIndex = prudentPartition(a, lower, upper);
      quickSort(a, lower, pivotIndex);
      quickSort(a, pivotIndex+1, upper);
    }
  }

  private static java.util.Random rnd = new java.util.Random();

/*
 * randomPartition(Comparable a[], int lower, int upper) permuta i valori di
 * memoria compresi tra 'lower' e 'upper' rispetto ad un valore detto pivot,
 * in modo tale che tutti gli elementi minori di pivot si trovino alla sua sx
 * mentre tutti gli altri alla sua dx.
 * L ascelta del pivot è casuale tra gli elementi dell'array.
 * Restituisce l'indirizzo di pivot.
 */
  private static int randomPartition(Comparable a[], int lower, int upper) {
    //scelgo l'elemento pivot in modo casuale, scambiando il primo elemento con
    //uno a caso
    int i = lower + rnd.nextInt(upper-lower+1);
    Comparable pivot = a[i];
    a[i] = a[lower];
    a[lower] = pivot;

    //inizio procedura di partizionamento
    Comparable temp = null;

    while (true) {
      while (a[upper].compareTo(pivot)>0)
        upper--;
      while (a[lower].compareTo(pivot)<0)
        lower++;

      if (lower<upper) {
        temp = a[lower];
        a[lower++] = a[upper];
        a[upper--] = temp;
      } else
        return upper;
    }
  }

/*
 * prudentPartition(Comparable a[], int lower, int upper) permuta i valori di
 * memoria compresi tra 'lower' e 'upper' rispetto ad un valore detto pivot,
 * in modo tale che tutti gli elementi minori di pivot si trovino alla sua sx
 * mentre tutti gli altri alla sua dx.
 * Il pivot è l'elemento che sta incentro all'array. In questo modo si sfrutta
 * un eventuale ordinamento parziale dell'array.
 * Restituisce l'indirizzo di pivot.
 */
  private static int prudentPartition(Comparable a[], int lower, int upper) {
    //scelgo come pivot l'elemento che sta nel mezzo tra lower e upper.
    //e lo sposto al primo posto dell'array
    int half = (lower+upper)/2;
    Comparable pivot = a[half];
    a[half] = a[lower];
    a[lower] = pivot;

    //inizio procedura di partizionamento
    Comparable temp = null;

    while (true) {
      while (a[upper].compareTo(pivot)>0)
        upper--;
      while (a[lower].compareTo(pivot)<0)
        lower++;

      if (lower<upper) {
        temp = a[lower];
        a[lower++] = a[upper];
        a[upper--] = temp;
      } else
        return upper;
    }
  }


// =========================================================== FINE LEZIONE


 /**
   * CountingSort(short[] a) è una algoritmo di ordinamento per indirizzo.
   * L'idea fondamentale dell'algoritmo è determinare, per ciascun elemento a[i],
   * quanti sono gli elementi minori. Questa informazione viene poi utilizzata
   * per determinare la posizione esatta in cui spostare l'elemento a[i]
   * all'interno dell'array.
   * L'algoritmo necessita di un array di supporto di dimensione pari al massimo
   * range dei valori presenti nell'array da ordinare. Di conseguenza potrebbe
   * essere impraticabile assumere il range completo degli int (2^32), soprattutto
   * se si devono ordinare solo alcune migliaia di elementi.
   * Per questa implementazione, si assume che il vettore d'input sia di short int
   * positivi e comunque, prima di allocare l'array, si esegue una ricerca del max
   * al fine di limitare lo spazio utilizzato allo stretto necessario.
   */
  public static short[] CountingSort(short a[]) //a = vettore di int short positivi
    throws IllegalArgumentException {
    int i = 0,
        max = 0;
    //verifico che l'array 'a' soddisfi le condizioni
    for (i=0; i < a.length; i++) {
      if (a[i] < 0)
        throw new IllegalArgumentException("Il vettore a contiene un elemento negativo");
      if (max < a[i])
        max = a[i];
    }

    short[] temp = new short[max+1];//se si usasse Vector si potrebbe evitare
                                    //tutto questo, anche se ad un costo
                                    //computazionale maggiore
    //determino per ogni i, numero elementi uguali a i
    for (i=0; i < a.length; i++)
      temp[a[i]] += 1;

    //determino per ogni i, numero elementi minori o uguali a i
    for (i=1; i <= max; i++)
      temp[i] += temp[i-1];

    //uso un array ausiliario per ordinare a
    short[] out = new short[a.length];

    for (i = a.length -1; i >= 0; i--) {
    //for (i = 0; (i < a.length); i++) {
      out[temp[a[i]] - 1] = a[i];
      temp[a[i]] -= 1;
    }
    return out;
  }

/**
   * BucketSort(int[] a) è una algoritmo di ordinamento per indirizzo.
   *
   * Per questa implementazione, si assume che il vettore d'input sia di int
   * positivi e comunque, prima di allocare l'array, si esegue una ricerca del max
   * al fine di limitare lo spazio utilizzato allo stretto necessario.
   */
  public static void BucketSort(int[] a) //a = vettore di int positivi
    throws IllegalArgumentException {
    int i = 0, k = 0,
        nBucket = 10;
    float max = 0;
    //verifico che l'array a soddisfi le condizioni
    for (i = 0; i < a.length; i++) {
      if (a[i] < 0)
        throw new IllegalArgumentException("Il vettore a contiene un elemento negativo");
      if (max < a[i])
        max = a[i];
    }

    max = nBucket / (max + 1); //determino dimensione range per bucket

    OrderedList[] lista = new OrderedList[nBucket]; //memorizzo su 10 bucket
    for (i = 0; i < nBucket; i++)
      lista[i] = new OrderedList(a.length / nBucket);

    for (i = 0; i < a.length; i++)
      lista[ (int)(a[i] * max) ].add(a[i]);

    int j = 0;
    for (i = 0; i < nBucket; i++) {
      for (k = 0; k < lista[i].length(); k++)
        a[j++] = lista[i].get(k);
    }
  }


  /**
   * estraiByte(int i, byte p) restituisce il p-esimo byte (senza segno) della variabile i
   * Il parametro p ha range 1..4
   * In java per rappresentare un byte senza segno devo utilizzare almeno uno short!!!

   */
  private static short estraiByte(int i, int posizione) {
    return (short) ((i >>> ( (posizione-1) * 8 ) ) & 0xFF);
  }


  /**
   * countingSortByte(int[] a, int p) ordina un vettore di interi relativamente
   * al byte p-esimo di ogni elemento. Questa procedura è da utilizzare in coppia
   * con il radixSort()
   */
  private static int[] countingSortByte(int[] a, int p)
    throws IllegalArgumentException {
    int i;
    short elemento, max = 0;

    for (i = 0; i < a.length; i++) {
      if (a[i] < 0)
        throw new IllegalArgumentException("Vettore a con elementi negativi!");
      elemento = estraiByte(a[i], p); // considero il p-esimo byte
      if (max < elemento)  // cerco il massimo elemento
        max = elemento;
    }// endfor

    int[] c = new int[max + 1];

    for (i = 0; i < a.length; i++) {//per ogni elemento, conto le occorrenze
      elemento = estraiByte(a[i], p);
      c[elemento]++;
    }

    for (i = 1; i < c.length; i++) //determino la posizione dove memorizzare gli elementi
      c[i] += c[i - 1];

    int[] out = new int[a.length];

    for (i = a.length - 1; i >= 0; i--) {
      elemento = estraiByte(a[i], p);
      out[c[elemento] - 1] = a[i];
      c[elemento]--;
    }//endfor

    return out;
  }// countingSortByte


  /**
   * radixSort(int[] a) ordina un array di interi utilizzando il metodo radix sort.
   */
  public static int[] RadixSort(int[] a) {
    for (int i = 1; i <= 4; i++) {  // int = 4 bytes
      a = countingSortByte(a, i);
    }
    return a;
  }// radixSort




}//fine classe