1.

INTRODUCCIÓN
1

Quick Sort para toda la familia

Anchundia Esteban1; Jean Pierre Escobar2; Juan José Beltrán3
1
Universidad Tecnológica Israel-Departamento de Ciencias de la Ingeniería –Carrer3 de Sistemas, Quito, Ecuador

Resumen:El método Quick Sort es considerado el método de ordenamiento más rápido y gracias a
su rápida implementación y su reducido tiempo de ejecución. En este breve proyecto pretendemos
demostrar la efectividad del método dentro de una interfaz visual que sea fácil de usar y amigable
con el usuario. La implementación se realizó en la plataforma de desarrollo Netbeans (lenguaje
Java) para lograrlo se optó por aprovechar el “JFrame Form” provista en la IDE, haciendo posible
visualizar de manera demostrativa y dinámica como funciona dicho método, “pasada por pasada”
es decir, cada iteración realizada por el programa, para de este modo ejemplificar de una manera
sencilla algunas de las aplicaciones prácticas que le podría dar un usuario promedio.

Palabras clave:Tecnología, Ordenamiento, Quick Sort, Java, Iterativo, Jframe

Quicksort for the whole family

Abstract: The Quick Sort method is considered the fastest sorting method and thanks to its rapid
implementation and reduced execution time. In this short project we intend to demonstrate the
effectiveness of the method within a visual interface that is easy to use and user-friendly. The
implementation was carried out in the Netbeans development platform (Java language). To achieve this, it
was decided to take advantage of the "JFrame Form" provided in the IDE, making it possible to view in a
demonstrative and dynamic way how said method works, "pass by pass" that is to say , each iteration
carried out by the program, in order to exemplify in a simple way some of the practical applications that
an average user could give it.

Keywords:Technology, Sorting, Quick Sort, Java, Iterative, Jframe

Quicksort, o en español, el método de sorteo rápido es considerado como el algoritmo de ordenamiento
interno más eficiente hasta la fecha esto debido a la baja complejidad del código, la basta implementación
posible que se le puede dar y la rapidez con la que ordena diferentes datos, se basa en una técnica de
comparación por pivotes, en donde todos los valores que cumplan con características preestablecidas por
usuario son ubicados en base a las mismas, haciendo uso constante de la recursividad. La mayoría de
aplicaciones que se le dan a este código son a nivel interno, en donde el pivote cae en el dato central del
conjunto de datos.
Este método fue una técnica desarrollada por C. Antony R. Hoare en 1960. El algoritmo original es
recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son
en general más lentos que los iterativos y consumen más recursos).  

1
Estudiante de Ingeniería en Sistemas de Información, estebin-sa@hotmail.com
2. Estudiante de Ingeniería en Sistemas de Información, jean05_pierre96@hotmail.com
3. Estudiante de Ingeniería en Sistemas de Información, juanjbeltran94@gmail.com
Las interfaces gráficas de usuario (GUI) ofrecen al usuario ventanas, cuadros de diálogo, barras de
herramientas, botones, listas desplegables y muchos otros elementos con los que ya estamos muy
acostumbrados a tratar.
Las aplicaciones son conducidas por eventos y se desarrollan haciendo uso de las clases que para ello nos
ofrece la API de Java.

La API de Java proporciona una biblioteca de clases para el desarrollo de Interfaces gráficas de usuario
(en realidad son dos). La biblioteca proporciona un conjunto de herramientas para la construcción de
interfaces gráficas que tienen una apariencia y se comportan de forma semejante en todas las plataformas
en las que se ejecuten. La estructura básica de la biblioteca gira en torno a componentes y contenedores.
Los contenedores contienen componentes y son componentes a su vez, de forma que los eventos pueden
tratarse tanto en contenedores como en componentes. La API está constituida por clases, interfaces y
derivaciones. AWT y Swing.

Los Controles utilizados en este proyecto fueron:

JFrame: Clase utilizada en Swing (biblioteca gráfica) para generar ventanas sobre las cuales añadir
distintos objetos con los que podrá interactuar o no el usuario. A diferencia de JPanel, JFrame posee
algunas nociones típicas de una ventana como minimizar, cerrar, maximizar y poder moverla.
JButton: es una implementación de un botón pulsador. Este componente tiene una etiqueta y genera un
evento cuando se presiona. También puede tener una imagen.
JTextArea: es un área de varias líneas que muestra texto sin formato. Está destinado a ser un
componente ligero que proporcione compatibilidad de origen con java. awt. TextArea donde
razonablemente pueda hacerlo.

En nuestro caso usaremos la plataforma de desarrollo Apache NetBeans en la versión 12.1, es un proyecto
Apache de alto nivel que abordan las necesidades de los desarrolladores, usuarios y empresas como base
para sus productos; en particular, para permitirles desarrollar estos productos de manera rápida, eficiente
y sencilla aprovechando las fortalezas de la plataforma Java y otros estándares relevantes de la industria
informática.

Nota

El proceso de instalación no lo describimos pues no es el objetivo primario de este trabajo siendo este
bastante sencillo e intuitivo. El paquete de instalación lo podemos obtener de la siguiente dirección web:
https://netbeans.apache.org/download/in
dex.html

Con esto ya tenemos lo necesario instalado y listo para comenzar.

2. METODOLOGÍA
Se realiza un estudio experimental en base al ciclo en V del desarrollo de aplicaciones que consiste en
asociar cada fase del desarrollo con la fase de validación que corresponde hasta la última fase de
implementación, pasando por las cuatro fases que son de Estudio, Diseño, Codificación y Pruebas.

La idea central del algoritmo se basa en lo siguiente:

1. Se toma un elemento X de una posición cualquiera del arreglo.

2. Se busca ubicar a X en la posición correcta del arreglo, de tal forma que todos los elementos que se
encuentren a su izquierda sean menores o iguales a X y todos los que
se encuentren a su derecha sean mayores o iguales a X. 

3. Se repiten los pasos anteriores, pero ahora para los conjuntos de datos que se encuentran a la izquierda
y a la derecha de la posición de X en el arreglo. 

4. El proceso termina cuando todos los elementos se encuentran en su posición correcta en el arreglo.

3. RESULTADOS Y DISCUSIÓN

3.1. Creación del proyecto en NetBeans

Se decidió usar la plataforma Apache NetBeans en su versión 12.1 por sus potentes herramientas,
facilidad de uso y versatilidad para el desarrollo de aplicaciones, en este caso se implementará un JFrame
que viene integrado dentro del programa a manera de formulario para uso por parte del usuario. Dicho
esto, cabe recalcar que el proceso de instalación es muy sencillo y que la aplicación prácticamente está
lista para usarse al momento.

Para demostrar la efectividad del método de ordenamiento que elegimos, optamos por crear una interfaz
visual en la que el usuario ingrese valores y pueda visualizarlos dentro de una JTextAreay de igual
manera el resultado se imprima en otro de estos controles. El primer paso sería abrir Netbeans, crear un
nuevo proyecto y dentro de este añadir un JFrame.

3.2. Diseño de la interface Gráfica

Luego de eso sigue el diseño de la interfaz visual, para lo cual vamos a necesitar varios componentes del
pallete que nos ofrece NetBeans. Necesitaremos un campo de texto para que el usuario ingrese los
números al arreglo para su posterior ordenamiento

TresJButton, uno (Agregar) que añada lo que el usuario colocó en el campo a la lista del primer
JTextArea y otro (Limpiar) que borredel mismo control la lista de elementos para poder volver a usarla
interface. Un tercero (Ordenar) que ejecuta el código de Quick Sort.
Dos JTextArea para visualizar la lista de datos ingresada por el usuario y otra para visualizar el resultado
del ordenamiento del arreglo.
Por último se agregan etiquetas para enunciar dentro de la interface qué es lo que hace nuestro programa.

Con todos estos componentes, nuestra interfaz visual tendrá una apariencia similar a esta.

3.3. Codificando Botones

Para codificar el botón de (Agregar) y colocar los números introducidos por teclado, primero se usó un
evento de click (jButton1ActionPerformed) en ambos botones independientemente y se colocó el
siguiente código:

 Botón Agregar

privatevoid
jButton1ActionPerformed(java.awt.event.
ActionEventevt) {
if(!txtNum.getText().equals("")){

lista.add(Integer.parseInt(txtNum.getTe
xt().toString()));

txtNum.setText("");

txtNum.requestFocus();

visualizar();

}else{

JOptionPane.showMessageDialog(null,
"Inserta valores a lista");

}
 }

 Botón Limpiar

Private void
jButton2ActionPerformed(java.awt.event.
ActionEventevt) {

lista.clear();

txtNum.setText("");

txaNum.setText("");

items=0;

 Botón Ordenar

privatevoid
jButton3ActionPerformed(java.awt.event.
ActionEventevt) {

// TODO
addyourhandlingcodehere:

if(!txaNum.getText().equals("")){

items=0;

txaPasadas.setText("");

txaPasadas.append("Pasos de
Ordenación\n\n");

QuickSort();

JOptionPane.showMessageDialog(null,alea
torioNum(100,1));

}else{

JOptionPane.showMessageDialog(null,
"Inserte valores");

Nota: Se colocó también un panel de aviso con el texto “Inserte valores” que saldrá a pantalla cuando el
campo de texto se encuentre vacío.

Para este punto el usuario puede añadir datos propios al arreglo para ordenar con el aplicativo.

3.4. Implementación de Funciones

Se procede ya a diseñar las siguientes funciones

 Visualización: Se procede ya a realizar una función de visualización en el área de campo de texto

con el siguiente código

public void visualizar(){

        txaNum.setText("");

        String list="";

        for(int i=0;i<lista.size();i++)
{

            list+=lista.get(i)+"\n";

        }

        txaNum.setText(list);

    }

 Transformar: utilizamos para que en el campo de visualización del ordenamiento sólo se efectúe
números y se colocó el siguiente código.

public int[] transformar(){

        Object numeros[]=new
Object[lista.size()];

        numeros=lista.toArray();

        int n[]=new int[lista.size()];

        for(int i=0;i<lista.size();i++)
{

            n[i]=Integer.parseInt(numer
os[i].toString());

        }

        return n;

    }

Nota: Es necesario el uso de las librerías “java.util.ArrayList” y “javax.swing.JOptionPane” para el uso

de arreglos y algunas funciones que colocamos dentro del programa.

 PrintList: función para imprimir las pasadas y el ordenamiento principal con el siguiente código:

public void PrintList(){

         items++;

        String r=items+"-> ";

        for(int f=0;f<lt.length;f++){

            r=r+lt[f]+" ";

        }

        txaPasadas.append(r+"\n");

    }

En esta función colocamos un ciclo de repetición que vaya recorriendo los elementos de la lista para que
se pueda visualizar los cambios en la posición de todos los elementos con cada pasada.

 OrdenarQuick

En esta función colocaremos nuestra versión del algoritmo de Quicksort para lo que necesitaremos
declara, tanto un arreglo como 2 variables de tipo int que funcionaran como punteros al momento de
recorrer al arreglo tanto del lado izquierdo como del lado derecho del elemento pivote.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote
elegido.

En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño.
En nuestro caso, y debido a la baja complejidad del algoritmo colocamos como orden
pivote=vector[(p+u)/2].

En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es
entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente
ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si
por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el
array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es
ineficiente.

En el caso promedio, el orden es O(n·log n), esta vez debido que no implementamos un codigo para
números masivos decidimos optar por un orden simple que coloque al dato pivote en el centro del arreglo,
para ello colocamos el siguiente código:

public void OrdenarQuick(int[] vector,

int p, int u){

        int i=p,j=u;

        int pivote=vector[(p+u)/2];

        int aux;
         do{

            while(vector[i]<pivote)i++;

            while(vector[j]>pivote)j--;

            if(i<=j){

                aux=vector[j];

                vector[j]=vector[i];

                vector[i]=aux;

                i++;

                j--;

            }

            

        }while(i<=j);

      PrintList();

      if(p<j)OrdenarQuick(vector,p,j); 

      if(u>i)OrdenarQuick(vector,i,u); 

    }

Los rasgos más importantes destacar en este código es el recorrido que toma el algoritmo al recorrer
constantemente después de declarar como pivote al dato más cercano del centro, se puede observar en la
línea de declaración del dato pivote que se coloca justamente en la mitad de la lista. Es importante
también resaltar el llamado que se hace a la función Sprint List que hicimos previamente.

Una vez revisados todos los posibles errores de identacion lo único que queda es compilar y correr el
programa.
 4. CONCLUSIONES

Se debe tomar en cuenta los nombres de los componentes default que nos arroja el JFrame, en nuestro
caso optamos por cambiar de nombre algunas variables tanto como para área de texto como para campos
de texto para evitar errores de identacion.

El conocimiento en base a las todas las características que maneja una plataforma de programación en
java, como lo es NetBeans, puede significar un aumento en la velocidad de creación de un programa ya
que el desarrollo visual en JFrame es sumamente intuitivo con el usuario y facilita mucho la
implementación de un código a diferentes acciones o eventos.

El uso o implementación de pensamiento matemático lógico es crucial para hacer la resolución de

problemas o el planteamiento de algoritmos mucho más eficiente.

Existen varios métodos de ordenación con diferentes puntos de vista en cuanto a eficiencia y propósitos
generales, el propósito del Quicksort con caracteres de tipo integer funciona perfectamente lo cual nos da
la pauta para poder implementarla también con cadenas de caracteres.
Prestar mucha atención a los errores de identacion al momento de establecer parámetros para bucles o
cambiar las posiciones de llamado a funciones dentro del algoritmo, ya que en varias ocasiones pueden
llegar a alterar el resultado al momento de visualizar las pasadas o incluso el arreglo ordenado.
 
El JFrame nos permite también mover los componentes visuales de manera más estética y eficiente, se
debe tener en cuenta la imagen con la que se va a presentar al programa para que el usuario no tenga
problemas identificando sus partes al momento de correrlo.

Considerar las especificaciones del algoritmo de Quicksort para que el programa logre mostrar cada una
de las pasadas antes del que el arreglo este completo ya que una llamada o un ciclo de repetición mal
limitado puede causar el área de texto refleje únicamente el número de pasadas conteniendo el arreglo
ordenado sin mostrar el proceso y los cambios efectuados

REFERENCIAS