import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.util.Random;

public class Ordenamiento extends Applet implements Runnable {

  int numMax=27; //Número máximo de elmentos a ordenar
  int numAleat=20; //Cantidad de números aleatorios generados
                  //(al inicio siempre será 20).
  int y[] = new int[numMax];
  int x[] = new int[numMax];
  int x2[] = new int[numMax];
  int x3[] = new int[numMax];
  int x4[] = new int[numMax];
  int x5[] = new int[numMax];
  int x6[] = new int[numMax];
  int x7[] = new int[numMax];
  int x8[] = new int[numMax];

  Thread hilo, hilo2, hilo3, hilo4, hilo5, hilo6, hilo7, hilo8;
  Button button1 = new Button();
  Button button10 = new Button();
  Button button2 = new Button();
  Button button3 = new Button();
  Button button4 = new Button();
  Button button5 = new Button();
  Button button6 = new Button();
  Button button7 = new Button();
  Button button8 = new Button();
  Scrollbar barraDes = new Scrollbar();
  TextField cantidadAleatorios = new TextField();
  Label label2 = new Label();
  Label label1 = new Label();
  Label label3 = new Label();
  Label label4 = new Label();

  /**Inicializar el applet*/
  public void init() {
    try {
      jbInit();
    }
    catch(Exception e) {
      e.printStackTrace();
    }
  }

  /**Inicialización de componentes*/
  private void jbInit() throws Exception {

    button1.setEnabled(false);
    button1.setFont(new java.awt.Font("Dialog", 1, 11));
    button1.setLabel("Burbuja");
    button1.setBounds(new Rectangle(35, 140, 100, 22));
    button1.addActionListener(new java.awt.event.ActionListener() {
      public void actionPerformed(ActionEvent e) {
        button1_actionPerformed(e);
      }
    });
    button2.setEnabled(false);
    button2.setFont(new java.awt.Font("Dialog", 1, 11));
    button2.setLabel("Quiksort");
    button2.setBounds(new Rectangle(175, 140, 100, 22));
    button2.addActionListener(new java.awt.event.ActionListener() {
      public void actionPerformed(ActionEvent e) {
        button2_actionPerformed(e);
      }
    });
    button3.setEnabled(false);
    button3.setFont(new java.awt.Font("Dialog", 1, 11));
    button3.setLabel("Shellsort");
    button3.setBounds(new Rectangle(315, 140, 100, 22));
    button3.addActionListener(new java.awt.event.ActionListener() {
      public void actionPerformed(ActionEvent e) {
        button3_actionPerformed(e);
      }
    });
    button4.setEnabled(false);
    button4.setFont(new java.awt.Font("Dialog", 1, 11));
    button4.setLabel("Bucketsort");
    button4.setBounds(new Rectangle(455, 140, 100, 22));
    button4.addActionListener(new java.awt.event.ActionListener() {
      public void actionPerformed(ActionEvent e) {
        button4_actionPerformed(e);
      }
    });
    button5.setEnabled(false);
    button5.setFont(new java.awt.Font("Dialog", 1, 11));
    button5.setLabel("Insertionsort");
    button5.setBounds(new Rectangle(595, 140, 100, 22));
    button5.addActionListener(new java.awt.event.ActionListener() {
      public void actionPerformed(ActionEvent e) {
        button5_actionPerformed(e);
      }
    });
    button6.setEnabled(false);
    button6.setFont(new java.awt.Font("Dialog", 1, 11));
    button6.setLabel("Selectionsort");
    button6.setBounds(new Rectangle(735, 140, 100, 22));
    button6.addActionListener(new java.awt.event.ActionListener() {
      public void actionPerformed(ActionEvent e) {
        button6_actionPerformed(e);
      }
    });
    button7.setBounds(new Rectangle(35, 305, 100, 22));
    button7.setLabel("Mergesort");
    button7.setFont(new java.awt.Font("Dialog", 1, 11));
    button7.setEnabled(false);
    button7.addActionListener(new java.awt.event.ActionListener() {
      public void actionPerformed(ActionEvent e) {
        button7_actionPerformed(e);
      }
    });
    button8.setEnabled(false);
    button8.setFont(new java.awt.Font("Dialog", 1, 11));
    button8.setLabel("Radixsort");
    button8.setBounds(new Rectangle(735, 305, 100, 22));
    button8.addActionListener(new java.awt.event.ActionListener() {
      public void actionPerformed(ActionEvent e) {
        button8_actionPerformed(e);
      }
    });
    button10.setFont(new java.awt.Font("Dialog", 1, 11));
    button10.setForeground(Color.blue);
    button10.setLabel("Generar Números");
    button10.setBounds(new Rectangle(374, 253, 140, 22));
    button10.addActionListener(new java.awt.event.ActionListener() {
      public void actionPerformed(ActionEvent e) {
        button10_actionPerformed(e);
      }
    });
    barraDes.setBackground(Color.blue);
    barraDes.setEnabled(true);
    barraDes.setForeground(Color.white);
    barraDes.setMaximum(27);
    barraDes.setVisibleAmount(0);
    barraDes.setOrientation(0);
    barraDes.setPageIncrement(1);
    barraDes.setUnitIncrement(1);
    barraDes.setValue(19);
    barraDes.setBounds(new Rectangle(382, 223, 124, 21));

    cantidadAleatorios.setBackground(Color.white);
    cantidadAleatorios.setEditable(false);
    cantidadAleatorios.setEnabled(true);
    cantidadAleatorios.setFont(new java.awt.Font("Dialog", 1, 12));
    cantidadAleatorios.setForeground(Color.blue);
    cantidadAleatorios.setText("20");
    cantidadAleatorios.setBounds(new Rectangle(436, 201, 21, 21));

    label1.setEnabled(true);
    label1.setForeground(Color.blue);
    label1.setText("1");
    label1.setBounds(new Rectangle(371, 224, 14, 15));
    label2.setEnabled(true);
    label2.setForeground(Color.blue);
    label2.setText("27");
    label2.setBounds(new Rectangle(511, 225, 18, 13));
    label3.setFont(new java.awt.Font("SansSerif", 0, 11));
    label3.setForeground(Color.blue);
    label3.setText("Para generar la cantidad indicada de numeros aleatorios, es necesario");
    label3.setBounds(new Rectangle(275, 285, 346, 18));
    label4.setFont(new java.awt.Font("SansSerif", 0, 11));
    label4.setForeground(Color.blue);
    label4.setText("que no se esté ejecutando ningún método de ordenamiento.");
    label4.setBounds(new Rectangle(303, 300, 294, 16));
    this.setFont(new java.awt.Font("Dialog", 0, 10));
    this.setLayout(null);

    this.add(button1, null);
    this.add(button2, null);
    this.add(button3, null);
    this.add(button4, null);
    this.add(button5, null);
    this.add(button6, null);
    this.add(button7, null);
    this.add(button8, null);
    this.add(button10, null);
    this.add(label2, null);
    this.add(label1, null);
    this.add(label4, null);
    this.add(label3, null);
    this.add(barraDes, null);
    this.add(cantidadAleatorios, null);
  }

  public void activa(){
    cantidadAleatorios.setEnabled(true);
    label1.setEnabled(true);
    label2.setEnabled(true);
    barraDes.setEnabled(true);
    button10.setEnabled(true);
  }

  public void activa2(){
    button1.setEnabled(true);
    button2.setEnabled(true);
    button3.setEnabled(true);
    button4.setEnabled(true);
    button5.setEnabled(true);
    button6.setEnabled(true);
    button7.setEnabled(true);
    button8.setEnabled(true);
  }


  public void desactiva(){
    cantidadAleatorios.setEnabled(false);
    label1.setEnabled(false);
    label2.setEnabled(false);
    barraDes.setEnabled(false);
    button10.setEnabled(false);
  }

  /**Eventos de Scrollbar:*/
  public boolean handleEvent( Event evt ) {
      if( evt.target.equals(barraDes) ) {
          cantidadAleatorios.setText( Integer.toString( ((Scrollbar)
                                                    evt.target).getValue()+1));
          numAleat=((Scrollbar)evt.target).getValue()+1;
          return true;
      }
      return super.handleEvent( evt );
  }

  void button1_actionPerformed(ActionEvent e) {
    button1.setEnabled(false);
    desactiva();
    for(int v=0; v<y.length; v++)  x[v] = y[v];
    start(1);
  }

  void button2_actionPerformed(ActionEvent e) {
    button2.setEnabled(false);
    desactiva();
    for(int v=0; v<y.length; v++)  x2[v] = y[v];
    start(2);
  }

  void button3_actionPerformed(ActionEvent e) {
    button3.setEnabled(false);
    desactiva();
    for(int v=0; v<y.length; v++)  x3[v] = y[v];
    start(3);
  }

  void button4_actionPerformed(ActionEvent e) {
    button4.setEnabled(false);
    desactiva();
    for(int v=0; v<y.length; v++)  x4[v] = y[v];
    start(4);
  }

  void button5_actionPerformed(ActionEvent e) {
    button5.setEnabled(false);
    desactiva();
    for(int v=0; v<y.length; v++)  x5[v] = y[v];
    start(5);
  }

  void button6_actionPerformed(ActionEvent e) {
    button6.setEnabled(false);
    desactiva();
    for(int v=0; v<y.length; v++)  x6[v] = y[v];
    start(6);
  }

  void button7_actionPerformed(ActionEvent e) {
    button7.setEnabled(false);
    desactiva();
    for(int v=0; v<y.length; v++)  x7[v] = y[v];
    start(7);
  }
  void button8_actionPerformed(ActionEvent e) {
    button8.setEnabled(false);
    desactiva();
    for(int v=0; v<y.length; v++)  x8[v] = y[v];
    start(8);
  }

  void button10_actionPerformed(ActionEvent e) {

    generaAleat();
    for(int v=0; v<y.length; v++){
      x[v] = y[v];
      x2[v] = y[v];
      x3[v] = y[v];
      x4[v] = y[v];
      x5[v] = y[v];
      x6[v] = y[v];
      x7[v] = y[v];
      x8[v] = y[v];
    }
    repaint();
    activa2();
  }

  /**Ejecución del hilo*/
  public void start(int i){
    if(i==1){
      hilo = new Thread(this);
      hilo.start();
    }
    else if(i==2){
      hilo2 = new Thread(this);
      hilo2.start();
    }
    else if(i==3){
      hilo3 = new Thread(this);
      hilo3.start();
    }
    else if(i==4){
      hilo4 = new Thread(this);
      hilo4.start();
    }
    else if(i==5){
      hilo5 = new Thread(this);
      hilo5.start();
    }
    else if(i==6){
      hilo6 = new Thread(this);
      hilo6.start();
    }
    else if(i==7){
      hilo7 = new Thread(this);
      hilo7.start();
    }
    else if(i==8){
      hilo8 = new Thread(this);
      hilo8.start();
    }
  }

  public void stop(int i){
    if(i==1)
      hilo = null;
    else if(i==2)
      hilo2 = null;
    else if(i==3)
      hilo3 = null;
    else if(i==4)
      hilo4 = null;
    else if(i==5)
      hilo5 = null;
    else if(i==6)
      hilo6 = null;
    else if(i==7)
      hilo7 = null;
    else if(i==8)
      hilo8 = null;
  }

  void pausa(){
    repaint();
    try { Thread.sleep(100); }
    catch (InterruptedException e) {}
  }

  public void run(){
    Thread hiloActual = Thread.currentThread();

    if (hiloActual == hilo) {
      Burbuja();
      stop(1);
      button1.setEnabled(true);
    }
    if (hiloActual == hilo2) {
      quiksort(x2, 0, numAleat-1);
      stop(2);
      button2.setEnabled(true);
    }
    if (hiloActual == hilo3) {
      shellsort();
      stop(3);
      button3.setEnabled(true);
    }
    if (hiloActual == hilo4) {
      bucksort();
      stop(4);
      button4.setEnabled(true);
    }
    if (hiloActual == hilo5) {
      insertionsort();
      stop(5);
      button5.setEnabled(true);
    }
    if (hiloActual == hilo6) {
      selectionsort();
      stop(6);
      button6.setEnabled(true);
    }
    if (hiloActual == hilo7) {
      mergesort();
      stop(7);
      button7.setEnabled(true);
    }
    if (hiloActual == hilo8) {
      radixsort();
      stop(8);
      button8.setEnabled(true);
    }
    if(hilo==null && hilo2==null&& hilo3==null&& hilo4==null&& hilo5==null&&
    hilo6==null && hilo7==null && hilo8==null)
      activa();
  }

  /**Dibuja las lineas a ordenar (la primera vez que se visualiza el applet).*/
  public void paint(Graphics g){
      int p=0;

      g.setColor(Color.white);
      g.fillRect(35,15,100,115);
      g.fillRect(175,15,100,115);
      g.fillRect(315,15,100,115);
      g.fillRect(455,15,100,115);
      g.fillRect(595,15,100,115);
      g.fillRect(735,15,100,115);
      g.fillRect(35,180,100,115);
      g.fillRect(735,180,100,115);
      g.setColor(Color.black);
      for(int i=0; i<numAleat; i++){
        g.drawLine(45+p,120,45+p,120-x[i]);
        g.drawLine(185+p,120,185+p,120-x2[i]);
        g.drawLine(325+p,120,325+p,120-x3[i]);
        g.drawLine(465+p,120,465+p,120-x4[i]);
        g.drawLine(605+p,120,605+p,120-x5[i]);
        g.drawLine(745+p,120,745+p,120-x6[i]);
        g.drawLine(45+p,285,45+p,285-x7[i]);
        g.drawLine(745+p,285,745+p,285-x8[i]);
        p+=3;
      }
  }

  /**Actualiza (mediante la llamada repaint)las lineas que se ordenan.
   * Este método evita el parpadeo (flickering).*/
  public void update(Graphics e){
    int p=0;

    e.setColor(Color.white);
    e.fillRect(35,15,100,115);
    e.fillRect(175,15,100,115);
    e.fillRect(315,15,100,115);
    e.fillRect(455,15,100,115);
    e.fillRect(595,15,100,115);
    e.fillRect(735,15,100,115);
    e.fillRect(35,180,100,115);
    e.fillRect(735,180,100,115);
    e.setColor(Color.black);
    for(int i=0; i<numAleat; i++){
      e.drawLine(45+p,120,45+p,120-x[i]);
      e.drawLine(185+p,120,185+p,120-x2[i]);
      e.drawLine(325+p,120,325+p,120-x3[i]);
      e.drawLine(465+p,120,465+p,120-x4[i]);
      e.drawLine(605+p,120,605+p,120-x5[i]);
      e.drawLine(745+p,120,745+p,120-x6[i]);
      e.drawLine(45+p,285,45+p,285-x7[i]);
      e.drawLine(745+p,285,745+p,285-x8[i]);
      p+=3;
    }
  }

  void Burbuja(){
    int b, j, t, n;
    n = numAleat-1;
    do{
      b = 0;
      for(j=0; j<n; j++){
         if(x[j] > x[j+1]){
           t = x[j];
           x[j] = x[j+1];
           x[j+1] = t;
           pausa(); //************************
           b++;
         }
      }
      n--;
    }
    while(b > 0);
  }

  public void quiksort(int x2[],int lo,int ho){
    int t, l=lo, h=ho, mid;

    if(ho>lo){
      mid=x2[(lo+ho)/2];
      while(l<h){
        while((l<ho)&&(x2[l]<mid))  ++l;
        while((h>lo)&&(x2[h]>mid))  --h;
        if(l<=h){
          t    = x2[l];
          x2[l] = x2[h];
          x2[h] = t;
          pausa(); //************************
          ++l;
          --h;
        }
      }
      if(lo<h) quiksort(x2,lo,h);
      if(l<ho) quiksort(x2,l,ho);
    }
  }

  public void shellsort(){
    int n = numAleat; //numero de elementos a ordenar
    int i, j; // Indices para manipular el arreglo
    int tamPasada; // Tamanno de los "subarreglos" ordenados en cada pasada
    int temporal; // Almacenamiento temporal para los intercambios

    // Calcular tamanno optimo de la primera pasada
    for( tamPasada = 1; tamPasada <= (n / 9); tamPasada = (3 * tamPasada + 1))
      ;   // Instruccion nula

    // Ordenar en cada pasada subarreglos de tamPasada tamanno, hasta llegar a
    // tamanno 1
    for( ; tamPasada > 0; tamPasada /= 3){
       for(i = tamPasada; i < n; i += tamPasada){
          temporal = x3[ i ]; j = i;   // Preparar variables por si hay
                                          // intercambio

          // Hacer espacio dentro del "subarreglo" actual si se encontro un
          // elemento menor
          while( j >= tamPasada && x3[ j - tamPasada ] > temporal ){
             x3[ j ] = x3[ j - tamPasada ];
             j -= tamPasada;
          };
          x3[ j ] = temporal;   // Insertar elemento menor en su lugar
          pausa(); //************************
       }; // for i
    }; // for tamPasada
  }

  public void bucksort(){
    int bindex; //Variable que llevara el control del indice del arreglo
    int i; //Variable que llevara el control del indice del arreglo
    int max=numAleat; //Variable para leer el numero de elementos del vector
                      //a ordenar
    int buck[] = new int [256]; //Arreglo de elementos no mayor de 256
    for (bindex=0;bindex<max;bindex++) //Ciclo para llenar el arreglo
      buck[bindex]=0;                  //auxiliar Buck con ceros
                                       //del mismo tamaño que nuestro vector
    for (i=0;i<max;i++) //Ciclo que hace a buck
      buck[x4[i]]++;
    i=0;
    bindex=0; //reinicia los indices a cero
    while(i<max){ //mientras que no enuentre el final del arreglo realiza
                  //lo siguiente
      while(buck[bindex]==0)
        bindex++;  //
      x4[i]=bindex;
      pausa(); //************************
      buck[bindex]--;
      i++;
    } // Termina el While
  }

  public void insertionsort(){
    for(int i=1; i<numAleat; i++){
       int v=x5[i];
       int j=i;
       while(j>0 && x5[j-1]>v){
          x5[j]=x5[j-1];
          x5[j-1]=v;
          pausa();
          j--;
          v=x5[j];
      }
    }
  }

  public void selectionsort(){
    int a, b, menor;

    for(a=0; a<numAleat-1; a++){
      menor=x6[a];
      for( b=a+1; b<numAleat; b++){
        if(menor>x6[b]){
              menor=x6[b];
              x6[b]=x6[a];
              x6[a]=menor;
              pausa(); //************************
          }
        }
      }
  }

  public void mergesort(){
    int n = numAleat;
    int[] aux = new int[n];
    int i, j, k, l1, l2, u1, u2, size = 1;

    while (size < n) {
      l1 = 0;
      k = 0;
      while ( (l1 + size) < n) {
        l2 = l1 + size;
        u1 = l2 - 1;
        u2 = (l2 + size - 1 < n) ? l2 + size - 1 : n - 1;
        for (i = l1, j = l2; (i <= u1) && (j <= u2); k++)
          if (x7[i] <= x7[j])
            aux[k] = x7[i++];
          else
            aux[k] = x7[j++];
        for (; i <= u1; k++)
          aux[k] = x7[i++];
        for (; j <= u2; k++)
          aux[k] = x7[j++];
        l1 = u2 + 1;
      } //while
      for (i = l1; k < n; i++)
        aux[k++] = x7[i];
      for (i = 0; i < n; i++)
        x7[i] = aux[i];
        pausa(); //************************
      size = size * 2;
    } //while
  }

  public void radixsort(){
    for(int i=0; i<numAleat; i++)
      x8[i]=0;

    int k=0, c=0, l=0;
    int varin=10;
    int num=0, nume=0, i1=0;

    for(int count=0; count<10; count++)
      for(int i=0; i<numAleat; i++)
        if ( y[i]%varin==count){
          x8[c]=y[i];
          c++;
        }
    for(int pasada=1; pasada<numAleat; pasada++)
      for(int j=0; j<numAleat -1 ;j++)
        if ( (x8[j]-x8[j]%varin)/10>(x8[j+1]-x8[j+1]%varin)/10){
          nume = x8[j];
          x8[j] = x8[j+1];
          x8[j+1] = nume;
          pausa(); //************************
        }
  }

  //Constructor de la clase, recibe la cantidad de aleatorios a generar
  public void generaAleat(){

    Random generador=new Random();

    for(int i=0;i<numAleat;i++){
      y[i]=generador.nextInt()%100;
    if(y[i]<0)
      y[i]*=-1;
    }
  }

}