Software Guru Conference & Expo 2014

Métodos de Ordenamiento.

Bueno pues aquí les dejo una tarea que me dejaron ami para alguien que le sirva luego adjunto la información de cada método. Si tengo algunas cosas mal con gusto digamenlas porfavor se los agradecería y si hay algo que puedo mejorar aun.

import java.applet.Applet;
import java.awt.Button;
import java.awt.Color;
import java.awt.Event;
import java.awt.Graphics;
import java.awt.Label;
import java.awt.Rectangle;
import java.awt.Scrollbar;
import java.awt.TextField;
import java.awt.event.ActionEvent;
import java.util.Random;

/**
 * @author Ferreyra
 *
 */

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();
private int l;
private int i1;
private int k;
private int num;

  /**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;

    setK(0);
        int c=0;
        setL(0);
    int varin=10;
    setNum(0);
        int nume=0;
        setI1(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;
    }
  }

public void setL(int l) {
        this.l = l;
}

public int getL() {
        return l;
}

public void setI1(int i1) {
        this.i1 = i1;
}

public int getI1() {
        return i1;
}

public void setK(int k) {
        this.k = k;
}

public int getK() {
        return k;
}

public void setNum(int num) {
        this.num = num;
}

public int getNum() {
        return num;
}

}

Saludos.

Comentarios

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.
Imagen de Israel-69

Muy buen Ejemplo

Como mejora, estaría genial ver los tiempos y poder tener una comparación cuantitativa de los ordenamientos, todo lo demás esta muy realizado para ser una prueba de concepto. pregunta sabes que algoritmos utiliza Java para sus ordenamientos ??

Saludos.

Imagen de OscarRyz

@Israel, según la

@Israel, según la documentación es un "mergesort modificado"

Imagen de Israel-69

mergesort modificado

Muchas gracias Oscar por la información!!, muy útil para cuando se necesiten ordenamientos; bastante más rápido que quick, que fue de los últimos que utilice jj, ya hace tiempo.