package dataStructures;

import java.util.Random;

/**
 * <p>Titulo: A classe utilitária de alg. de ordenação</p>
 * <p>Descrição: Possui vários algoritmos de ordenação sobre vectores de
 *               Objectos comparáveis.</p>
 * @version 1.0
 */

public class Sort {

 // Esconder o construtor. Não se pode construir objectos desta classe!
  private Sort() {
  }

  private static void swap(Object[] v, int i, int j) {
    Object tmp = v[i];
    v[i] = v[j];
    v[j] = tmp;
  }
  /**
   * Ordena através do algoritmo insertSort, complexidade O(|v|^2)
   * @param v O vector de elementos a ordenar
   */
  public static void insert(Comparable[] v) {
    int    i,j;

    for (i=1;i<v.length;i++) {
      Comparable tmp = v[i];
      for(j=i;j>0 && v[j-1].compareTo(tmp) > 0;j--)
        v[j] = v[j-1];
      v[j] = tmp;
    }
  }

  /**
   * Ordena através do algoritmo selectionSort, complexidade O(|v|^2)
   * @param v O vector de elementos a ordenar
   */
  public static void selection(Comparable[] v) {
    for (int i=0;i<v.length-1;i++) {
      int least = i;
      for(int j=i+1;j<v.length;j++)
        if (v[j].compareTo(v[least])<0)
          least=j;
      swap(v,i,least);
    }
  }

  /**
   * Ordena através do algoritmo bubbleSort, complexidade O(|v|^2)
   * @param v O vector de elementos a ordenar
   */
  public static void bubble(Comparable[] v) {
    for (int i=v.length;i>0;i--)
      for(int j=1;j<i;j++)
        if (v[j].compareTo(v[j-1]) < 0)
          swap(v,j,j-1);
  }

  private static void quicksort(Comparable[] v, int begin, int end) {
    if (end>begin) {
      int lower = begin, higher = end;
        // Escolher o pivot arbitrariamente como o elemento do meio
      Comparable pivot = v[(begin+end)/2];
      while(lower<=higher) {
        while((lower<end) && (v[lower].compareTo(pivot)<0))
          ++lower;
        while((higher>begin) && (v[higher].compareTo(pivot)>0))
          --higher;
        if(lower<=higher)            // se os indices ainda nao se cruzaram...
          swap(v,lower++,higher--);  //  ... trocar os elementos
      }
      if(begin<higher)
        quicksort(v,begin,higher);
      if(lower<end)
        quicksort( v, lower, end );
    }
  }

  /**
   * Ordena através do algoritmo quickSort, complexidade O(|v|*log(|v|) no caso médio
   * @param v O vector de elementos a ordenar
   */
  public static void quick(Comparable[] v) {
    quicksort(v,0,v.length-1);
  }

  /**
   * Ordena através do algoritmo heapSort, complexidade O(|v|*log(|v|)
   * @param v O vector de elementos a ordenar
   */
  public static void heap(Comparable[] v) {
     VHeap h = new VHeap();

     for(int i=0;i<v.length;i++)
       h.insert(v[i]);     // constrói o amontoado

     for(int i=v.length-1;
            !h.isEmpty();
            h.remRoot(),i--)
       v[i] = (Comparable)h.root();   // coloca os maiores a partir do fim
  }

  /**
   * Ordena através do algoritmo countSort, complexidade O(|v|) mas
   *   assume um valor máximo no vector
   * @param v   O vector de elementos a ordenar
   * @param max O maior valor no vector
   */
  public static void count(int[] v, int max) {
    int[] result = new int[v.length+1];
    int[] count = new int[max];

    for(int i=0;i<v.length;i++)
      count[v[i]]++;           //count[i] has the number of elems == i

    for(int i=1;i<max;i++)
      count[i] += count[i-1];  //count[i] has the number of elems <= i

    for(int i=v.length-1;i>=0;i--) {
      result[count[v[i]]-1] = v[i];
      count[v[i]]--;
    }

    for(int i=0;i<v.length;i++)
      v[i] = result[i];
  }

  /**
   * Ordena através do algoritmo mergeSort, complexidade O(|v|*log(|v|)
   * @param v O vector de elementos a ordenar
   */
  public static void merge(Comparable[] v) {
    merge(v,0,v.length-1);
  }

  private static void merge(Comparable[] v, int begin, int end) {
    if (begin==end)
      return;

    int middle = (begin+end)/2;
    merge(v,begin,middle);
    merge(v,middle+1,end);
    mergeBoth(v,begin,middle,end);
  }

  private static void mergeBoth(Comparable[] v, int begin, int middle, int end) {
    Comparable[] tmp = new Comparable[end-begin+1];
    int j=0, i1=begin, i2=middle+1;

    for(;i1<=middle && i2<=end;j++)
      tmp[j] = (v[i1].compareTo(v[i2])<=0) ? v[i1++] : v[i2++];

    if (i1<=middle)
      for(;i1<=middle;j++,i1++)
        tmp[j] = v[i1];
    else
      for(;i2<=end;j++,i2++)
        tmp[j] = v[i2];

    System.arraycopy(tmp,0,v,begin,tmp.length);
  }

/* versão alternativa com = complexidade mas que consome mais memória

  public static void merge(Comparable[] v) {
    if (v.length<2)
      return;

    Comparable[] left = new Comparable[v.length/2],
                right = new Comparable[v.length - left.length];

    // arraycopy(origem[],init index,destino[],init index,copy-size)
    System.arraycopy(v,0,left,0,left.length);
    System.arraycopy(v,left.length,right,0,right.length);

    merge(left);
    merge(right);
    mergeBoth(left,right,v);
  }

  private static void mergeBoth(Comparable[] v1, Comparable[] v2,
                                Comparable[] result) {
    int i1, i2, j;

    for(i1=i2=j=0;i1<v1.length && i2<v2.length;j++)
      result[j] = (v1[i1].compareTo(v2[i2])<=0) ? v1[i1++] : v2[i2++];

    if (i1<v1.length)
      for(int i=i1;i<v1.length;i++,j++)
        result[j] = v1[i];
    else
      for(int i=i2;i<v2.length;i++,j++)
        result[j] = v2[i];
  }
*/

  //********************************************************************
  public static void main(String[] args) {
/*
    Integer[] v = new Integer[13];

    v[0] = new Integer(10);    v[1] = new Integer(2);
    v[2] = new Integer(5);    v[3] = new Integer(3);
    v[4] = new Integer(4);    v[5] = new Integer(1);
    v[6] = new Integer(14);    v[7] = new Integer(22);
    v[8] = new Integer(8);    v[9] = new Integer(10);
    v[10] = new Integer(81);    v[11] = new Integer(102);
    v[12] = new Integer(120);
*/

    int v[] = new int[] {1,8,3,7,2,3};
    for(int i=0;i<v.length;i++)
      System.out.print(v[i] + " ");
    System.out.println();

    Sort.count(v,8);

    for(int i=0;i<v.length;i++)
      System.out.print(v[i] + " ");

  }
}