Método de Quicksort

Ir abajo

Método de Quicksort

Mensaje  Admin (Viruz) el 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]

[Tienes que estar registrado y conectado para ver este vínculo]
¿Como funciona el Programa?

  1. Corre el programa ya sea en NetBeans o con el .jar.
  2. Al iniciar el programa aparecerá nuestra ventana con su respectivo panel.
  3. Nos aparecerá un cuadro de texto grande (JTextField) abajo de este un unas opciones con (JRadioButton) y nuestro Botón(JButton) para ordenar.
  4. Introducimos los valores en nuestro cuadro de texto separando con un espacio todos los números a ordenara.
  5. Ya introducidos los números seleccionamos si queremos el despliegue ascendente o descendente y después clic en "Ordenar".
  6. 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
[Tienes que estar registrado y conectado para ver este vínculo]

Descarga el Código
[Tienes que estar registrado y conectado para ver este vínculo]
Autor: Viruz study
Enlace: [Tienes que estar registrado y conectado para ver este vínculo]

_________________
[Tienes que estar registrado y conectado para ver esa imagen]
avatar
Admin (Viruz)
Admin

Mensajes : 148
Fecha de inscripción : 23/09/2012
Edad : 30
Localización : Desktop

http://viruz.foroactivo.mx

Volver arriba Ir abajo

Volver arriba


 
Permisos de este foro:
No puedes responder a temas en este foro.