Como Usted Ordene
Archivos necesarios:
En este trial veremos algunos de los algoritmos más utilizados de ordenamiento, veremos ventajas, desventajas y tiempos de ejecución para poder tener bases sólidas al seleccionar alguno. Los algoritmos de ordenamiento son muy utilizados en los juegos para llevar una lista de las mejores puntuaciones o cuando queremos mostrar reportes ordenados de alguna manera.
El archivo que vamos a utilizar en esta practica es un archivo JAR que podemos correr con el comando
java -jar Tiempo.jar #
Donde # es el número de elementos que queremos que haya en el arreglo a ordenar. El programa crea un arreglo de # elementos aleatorios 100 veces y lo ordena, al final muestra datos del promedio de tiempo de ordenamiento así como el tiempo máximo de ordenamiento.
Hablando de Eficiencia
Primero vamos a ver un poco más acerca de la eficiencia de los algoritmos. El número de operaciones que se deben hacer para poder terminar de ejecutar un algoritmo es lo que conocemos como complejidad y para poderla estudiar la catalogamos en tres tipos:
- Peor Caso: Nos dice qué es lo peor que puede pasar, es la medida más útil. La complejidad en el peor de los casos se indica mediante la notación O, para un algoritmo que recorre un arreglo de n elementos tendríamos una complejidad O(n) porque sólo tiene que recorrer una vez el arreglo de n elementos, para recorrer una matriz tendríamos O(n²) .
- Caso Promedio: Nos dice el grado de complejidad del caso promedio, con lo que podemos darnos una idea de la experiencia para un usuario promedio. Es bastante útil pero no es muy fácil de sacar.
- Mejor Caso: No es muy útil porque regularmente el mejor caso es instantaneo.
Sabiendo esto vamos a analizar un poco más algunos algoritmos de ordenamiento. Para nuestro análisis vamos a ver cómo funciona el algoritmo a grandes rasgos, después vamos a ver cuáles son el peor caso y el caso promedio utilizando un poco de teoría y utilizando varias corridas del programa de este trial.
Cuatro de los algoritmos más utilizados son:
BubbleSort
La idea del BubbleSort es ir revisando cada casilla para ver si en la casilla anterior hay un elemento más grande y en caso de que así sea los cambiamos y seguimos adelante. La idea surgió de la manera en que las burbujas más grandes suben más rápido que las burbujas más pequeñas en un refresco. BubbleSort es muy utilizado porque a pesar de ser muy poco eficiente es muy sencillo de implementar y entender. Para los arreglos pequeños regularmente no se necesita un algoritmo muy poderoso y BubbleSort cumple los requerimientos de manera satisfactoria.
Peor Caso: En el peor de los casos como los elementos se mueven únicamente una sola casilla en cada recorrido tendríamos que recorrer todas las casillas para todos los elementos lo que nos da una complejidad de O(n²)
Caso Promedio: En el caso promedio BubbleSort tiene un tiempo de ejecución de:
- 5.56 milisegundos para 1,000 elementos
- 137.7 milisegundos para 5,000 elementos
- 564.2 milisegundos para 10,000 elementos
- 19,962.27 milisegundos para 50,000 elementos
InsertSort
La idea en InsertSort (también llamado InsertionSort) es seleccionar un valor cualquier dentro de un conjunto de elementos a ordenar y encontrar el lugar en el que debe insertarse dentro de un arreglo ordenado. Para implementarlo utilizando un solo arreglo utilizamos un ciclo que lea cada casilla y que coloque al elemento leido en la posición correcta entre los elementos ya ordenados. InsertSort es un algoritmo fácil de implementar, y tiene un buen desempeño, en especial en arreglos que se encuentran semi-ordenados. También tiene la ventaja de ser capaz de manejar la inserción ordenada, es decir, que cuando agregemos un nuevo elemento al arreglo lo ordene de manera mucho más rápida.
Peor Caso: En el peor de los casos InsertSort debe revisar cada casilla y por cada casilla revisar todas las casillas anteriores para poder ordenarla, por lo que tiene una complejidad de O(n²).
Caso Promedio: En el caso promedio InsertSort tiene un buen desempeño, particularmente en arreglos semi-ordenados. InsertSort tiene un orden de complejidad promedio de O(n²/4). En las corridas de ejecución tiene un tiempo promedio de:
- 3.79 milisegundos para 1,000 elementos
- 87.02 milisegundos para 5,000 elementos
- 358.59 milisegundos para 10,000 elementos
- 13372.22 milisegundos para 50,000 elementos
SelectSort
La idea en SelectSort (también llamado SelectionSort) es seleccionar el elemento más grande y pasarlo al final. Es el algoritmo de ordenamiento más natural e intuitivo por lo que es uno de los más sencillos de implementar pero su desempeño generalmente no es tan bueno como el de InsertSort para listas que estén semi-ordenadas.
Peor Caso: En el peor de los casos SelectSort debe recorrer el arreglo y encontrar el mayor elemento para cada una de las casillas por lo que tiene una complejidad de O(n²).
Caso Promedio: En el caso promedio SelectSort tiene un desempeño mejor que BubbleSort y un poco mejor que InsertSort para valores aleatorios pero para valores semi-ordenados InsertSort tiene un mucho mejor desempeño. En las corridas de ejecución tiene un tiempo promedio de:
- 1.88 milisegundos para 1,000 elementos
- 78.0 milisegundos para 5,000 elementos
- 197.85 milisegundos para 10,000 elementos
- 6545.46 milisegundos para 50,000 elementos
QuickSort
La idea en QuickSort es tomar un pivote y dividir un arreglo en dos, después colocar todos los valores menores que el pivote a la izquierda y todos los valores mayores a la derecha. Cada uno de estos sub-arreglos se ordenan de la misma manera, por lo que QuickSort es un algoritmo recursivo. QuickSort es uno de los algoritmos más utilizados ya que por lo general es el más rápido, lo que se nota especialmente en conjuntos muy grandes de datos. La principal desventaja es que QuickSort es uno de los algoritmos más difíciles de implementar.
Peor Caso: En el peor de los casos QuickSort debe ordenar todos los números a la izquierda y todos los números a la derecha del pivote, por lo que su eficiencia es de O(n²) pero este caso no es muy común.
Caso Promedio: En el caso promedio QuickSort es el más rápido de los algoritmos que vimos, tiene una eficiencia de O(n log2 n). Para las corridas de ejecución tiene un tiempo promedio de:
- 0.16 milisegundos para 1,000 elementos
- 1.39 milisegundos para 5,000 elementos
- 1.73 milisegundos para 10,000 elementos
- 13.88 milisegundos para 50,000 elementos (¡casi 1,500 veces mejor que el BubbleSort!)
Regresar