Método de Quicksort

**Admin (Viruz)** Dom Oct 07, 2012 3:13 am

Hola de nuevo a todos desafortunadamente no he tenido tiempo de ponerles programas o de actualizar el blog ya que es finales de semestre y estamos en entrega de proyectos y tareas. Me abro un espacio para traerles a ustedes un programa que hice hace algunos años, como ustedes ya conocen existen varios métodos de ordenamiento como:

Método de Burbuja
Método de Inserción
Método de Selección
QuickSort
HeapSort
BinSort
RadixSort
Arboles de Decisión

Hoy les traigo QuickSort hecho en Java.

Imágenes

[Tienes que estar registrado y conectado para ver este vínculo]

¿Como funciona el Programa?

Corre el programa ya sea en NetBeans o con el .jar.
Al iniciar el programa aparecerá nuestra ventana con su respectivo panel.
Nos aparecerá un cuadro de texto grande (JTextField) abajo de este un unas opciones con (JRadioButton) y nuestro Botón(JButton) para ordenar.
Introducimos los valores en nuestro cuadro de texto separando con un espacio todos los números a ordenara.
Ya introducidos los números seleccionamos si queremos el despliegue ascendente o descendente y después clic en "Ordenar".
Por último nos aparecerá el resultado en nuestra etiqueta de abajo(JLabel).

Nota: También cuenta con una forma de restricción si los caracteres que introducen no son validos (solo admite numéricos).

Código

Clase Main

01 /**
02  *
03  * @author Jesus Ivan
04  */
05 public class Main{
06     public static void main(String args[]) {
07        java.awt.EventQueue.invokeLater( new Runnable(){      
08            public void run() {
09                 new QuicksortGUI().setVisible(true);
10                 new QuicksortGUI().setLocationRelativeTo(null);
11             }
12       });
13     }
14 }

Clase ArregloQuickSort

01 /**
02  *
03  * @author Jesus Ivan
04  */
05 
06 /**
07  * Utelirías para ordenamiento de arreglos (estructuras de datos)
08  * (no soporta primitivos, sólo los wrappers: Integer, Long, Double, etc;
09  * en general cualquier objeto que implemente la interfaz java.lang.Comparable)
10  *
11  */
12 
13 public class ArregloQuickSort {
14     /**
15      * Implementación del método de ordenación quicksort, 
16      * en orden ascendente, forma recursiva
17      * @param a El arreglo a ordenar
18      */
19 
20  public static <E extends Comparable<? super E>> void quicksort(E a[], int ini, int fin) {
21         if (a == null)
22             throw new NullPointerException();
23         int izq = ini, 
24             der = fin, 
25             pos = ini;
26         boolean band = true;
27 
28  //Cada iteración representa una pasada de izq/der y viceversa
29 
30         while (band) { 
31             band = false;
32 
33             // Recorre el algoritmo de derecha a izquierda
34 
35             while (a[pos].compareTo(a[der]) <= 0 && pos != der) 
36     --der;
37                  if (pos != der) {
38                   intercambiar(a, pos, der);
39                   pos = der;
40                 
41     //Recorre el algoritmo de izquierda a derecha
42 
43                   while (a[pos].compareTo(a[izq]) >= 0 && pos != izq)
44                       ++izq;
45                    if (pos != izq) {
46                        band = true;
47                        intercambiar(a, pos, izq);
48                        pos = izq;
49                    }
50            }           
51         }
52 
53         if ( (pos-1) > ini)
54             quicksort(a, ini, pos-1); //Acomoda los elementos del conjunto izquierdo
55         if ( fin > (pos+1) )
56             quicksort(a, pos+1, fin); //Acomoda los elementos del conjunto derecho
57     }
58 
59   public static <E extends Comparable<? super E>> void reverseOrder(E a[]) {
60         E aux = null;
61 
62         for (int i = 0; i < a.length/2; i++) {
63             aux = a[i];          
64             a[i] = a[a.length - (i+1)];
65             a[a.length - (i+1)] = aux;
66         }
67     }
68     
69      /**
70      * Intercambia los elementos en las posiciones pos1 y pos2 del arreglo a[]
71      * a ?  El arreglo que contiene los objetos a intercambiar
72      * pos1 ? Posición 1
73      * pos2 ? Posición 2
74      */
75 
76     private static void intercambiar(Object a[], int pos1, int pos2) {
77         Object aux = a[pos1];
78         a[pos1] = a[pos2];
79         a[pos2] = aux;
80     }
81     
82         
83     public static <E extends Comparable<? super E>> void quicksort(E a[]) {
84         quicksort(a, 0, a.length-1);
85     }
86     
87     public static void main(String[] args) {
88         Integer a[] = {15, 67, 8, 16, 44, 27, 12, 35, 1};
89         //burbujaAscendente(a);
90         quicksort(a);
91         reverseOrder(a);
92         for (int b : a) {
93             System.out.println(b);
94     }
95   }    
96 }

Clase QuickSortGUI

01 /**
02  *
03  * @author Jesus Ivan
04  */
05 import java.awt.Color;
06 import java.awt.event.ActionEvent;
07 import java.util.ArrayList;
08 import java.util.List;
09 import java.util.Scanner;
10 import javax.swing.*;
11 
12 public class QuicksortGUI extends JFrame {  
13     // Declaracion de Variables
14     private JRadioButton ascRadioChoice;
15     private ButtonGroup buttonGroup1;
16     private JTextField cadenaTextField;
17     private JRadioButton descRadioChoice;
18     private JButton jButton1;
19     private JLabel jLabel1;
20     private JLabel jLabel2;
21     private JLabel jLabel3;
22     private JLabel resultLabel;
23     private JLabel resultadoLabel;
24     
25     /** Creates new form QuicksortGUI */
26     public QuicksortGUI() {
27         initComponents();
28         //Le damos un Tipo de Letra y Color al Label de Resultado.
29         resultLabel.setFont(new java.awt.Font("SansSerif", 1, 14));
30         resultLabel.setForeground(Color.RED);
31         setLocationRelativeTo(null);      
32     }
33     /** This method is called from within the constructor to
34      * initialize the form.
35      * initComponents es Declarado ya que la Interfaz(GUI) se Realizo en un 
36      * JPanel Form y se tiene que Mandar a llamar.
37      */
38     @SuppressWarnings("unchecked")
39     // <editor-fold defaultstate="collapsed" desc="Generated Code">//GEN-BEGIN:initComponents
40     private void initComponents() {
41 
42         buttonGroup1 = new javax.swing.ButtonGroup();
43         jLabel1 = new javax.swing.JLabel();
44         cadenaTextField = new javax.swing.JTextField();
45         jLabel2 = new javax.swing.JLabel();
46         ascRadioChoice = new javax.swing.JRadioButton();
47         descRadioChoice = new javax.swing.JRadioButton();
48         jButton1 = new javax.swing.JButton();
49         resultadoLabel = new javax.swing.JLabel();
50         jLabel3 = new javax.swing.JLabel();
51         resultLabel = new javax.swing.JLabel();
52 
53         setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);
54         setTitle("Viruz Blog: QuickSort");
55 
56         jLabel1.setFont(new java.awt.Font("SansSerif", 1, 15));
57         jLabel1.setForeground(new java.awt.Color(1, 1, 1));
58         jLabel1.setText("INTRODUZCA UNA CADENA DE NÚMEROS QUE DESEE ORDENAR, SEPARADA POR ESPACIOS:");
59 
60  
61 
62         jLabel2.setText("ORDEN:");
63 
64         buttonGroup1.add(ascRadioChoice);
65         ascRadioChoice.setSelected(true);
66         ascRadioChoice.setText("ascendente");
67 
68         buttonGroup1.add(descRadioChoice);
69         descRadioChoice.setText("descendente");
70 
71         jButton1.setText("Ordenar");
72         jButton1.addActionListener(new java.awt.event.ActionListener() {
73             public void actionPerformed(java.awt.event.ActionEvent evt) {
74                 jButton1ActionPerformed(evt);
75             }
76         });
77 
78         jLabel3.setText("RESULTADO:");
79 
80         javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane());
81         getContentPane().setLayout(layout);
82         layout.setHorizontalGroup(
83             layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
84             .addGroup(layout.createSequentialGroup()
85                 .addContainerGap()
86                 .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
87                     .addGroup(layout.createSequentialGroup()
88                         .addComponent(jLabel2)
89                         .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
90                         .addComponent(ascRadioChoice)
91                         .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
92                         .addComponent(descRadioChoice)
93                         .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED, 471, Short.MAX_VALUE)
94                         .addComponent(jButton1)
95                         .addContainerGap())
96                     .addGroup(layout.createSequentialGroup()
97                         .addComponent(jLabel3)
98                         .addContainerGap(737, Short.MAX_VALUE))
99                     .addGroup(layout.createSequentialGroup()
100                         .addComponent(resultadoLabel, javax.swing.GroupLayout.DEFAULT_SIZE, 27, Short.MAX_VALUE)
101                         .addGap(792, 792, 792))
102                     .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, layout.createSequentialGroup()
103                         .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING)
104                             .addComponent(jLabel1, javax.swing.GroupLayout.Alignment.LEADING, javax.swing.GroupLayout.DEFAULT_SIZE, 807, Short.MAX_VALUE)
105                             .addComponent(cadenaTextField, javax.swing.GroupLayout.DEFAULT_SIZE, 807, Short.MAX_VALUE))
106                         .addContainerGap())
107                     .addGroup(layout.createSequentialGroup()
108                         .addComponent(resultLabel, javax.swing.GroupLayout.DEFAULT_SIZE, 807, Short.MAX_VALUE)
109                         .addContainerGap())))
110         );
111         layout.setVerticalGroup(
112             layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
113             .addGroup(layout.createSequentialGroup()
114                 .addContainerGap()
115                 .addComponent(jLabel1)
116                 .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
117                 .addComponent(cadenaTextField, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)
118                 .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
119                 .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
120                     .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE)
121                         .addComponent(jLabel2)
122                         .addComponent(ascRadioChoice)
123                         .addComponent(descRadioChoice))
124                     .addComponent(jButton1))
125                 .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.UNRELATED)
126                 .addComponent(jLabel3)
127                 .addGap(18, 18, 18)
128                 .addComponent(resultadoLabel)
129                 .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
130                 .addComponent(resultLabel, javax.swing.GroupLayout.DEFAULT_SIZE, 27, Short.MAX_VALUE)
131                 .addContainerGap())
132         );
133 
134         pack();
135     }// </editor-fold>//GEN-END:initComponents
136 
137 
138     private void jButton1ActionPerformed(ActionEvent evt) {//GEN-FIRST:event_jButton1ActionPerformed
139         /** Al Oprimir el Boton Toma lo que estan en el TextFied Manda A LLamar 
140          * al metodo quicksort le pasa los datos y si se selecciona de forma 
141          * descendente cambiara si no lo dejara en forma ascendente.
142          */
143         try {
144             //Declaramos la clase Integer[] parseNumber();
145             Integer[] arreglo = parseNumbers(cadenaTextField.getText());
146             
147             ArregloQuickSort.quicksort(arreglo);
148 
149             if (descRadioChoice.isSelected()) {
150                 ArregloQuickSort.reverseOrder(arreglo);
151             }
152             //StringBuilder.-Representa una cadena de caracteres modificable.
153             StringBuilder resultado = new StringBuilder();
154 
155             for (Integer i : arreglo) {
156                 //apppend().-añade cualquier dato a una lista
157                 //se añade a resultado lo que vale en la posicion i y un espacio.
158                 resultado.append(i).append(" ");
159             }
160             //toString.-devuelve el valor numérico como una cadena
161             resultLabel.setText(resultado.toString());
162         } catch (RuntimeException e) {
163             resultLabel.setText("La cadena introducida no es válida, los enteros " +
164                     "deben estar separados por espacios");
165         }
166 }//GEN-LAST:event_jButton1ActionPerformed
167 
168 
169     private Integer[] parseNumbers(String numbers) {
170         List<Integer> lista = new ArrayList<Integer>();
171         Scanner scanner = new Scanner(numbers);
172 
173         while (scanner.hasNext()) {
174             lista.add(scanner.nextInt());
175         }
176 
177         return lista.toArray(new Integer[]{});
178     }
179 }

Vídeo

Descarga el Código
Método QuickSort

Autor: Viruz study

Enlace: Método de Ordenamiento QuickSort