Durante esta actividad, los alumnos serán capaces de:
Esta actividad promueve las siguientes habilidades, valores y actitudes: análisis y síntesis, capacidad de resolver problemas, creatividad, y uso eficiente de la informática y las telecomunicaciones.
Esta actividad puede ser elaborada de manera individual o en parejas.
Escribe una clase llamada edd.util.Sorts. En esta clase deberás colocar únicamente operaciones de utilería (métodos estáticos) para resolver los problemas que se describen a continuación.
En la parte superior del archivo Sorts.java coloca en comentarios los datos personales de los autores de la tarea. Por ejemplo:
/*-------------------------------------------------------------------- * Práctica 5: Ordenamientos * Fecha: 11-Mar-2014 * Autores: * 1166611 Pepper Pots * 1160611 Anthony Stark *--------------------------------------------------------------------*/
Estos son los métodos que debes implementar:
public static <T extends Comparable<T>> List<T> selectionSort(List<T> list)
Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento por selección directa sobre list. El método no debe modificar a list.
Descripción del algoritmo: Empieza con una lista resultante vacía y una copia de list. En cada iteración encuentra y remueve el elemento más pequeño de la copia de list, y coloca dicho elemento al final de la lista resultante. Las iteraciones terminan cuando la copia de list queda totalmente vacía. No olvides regresar la lista resultante.
public static List<Integer> bucketSort(List<Integer> list)
Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento por casilleros sobre list. Los elementos contenidos en list deben ser números enteros del 0 al 99. El método no debe modificar a list.
Descripción del algoritmo: Empieza con diez listas vacías numeradas de la 0 a la 9. Recorre todos los elementos de list, colocando cada elemento en la lista que le corresponda: los elementos del 0 al 9 van en la lista 0, los elementos del 10 al 19 van en la lista 1, los elementos del 20 al 29 van en la lista 2, y así sucesivamente. Posteriormente ordena individualmente cada una de las listas de la 0 a la 9 (utiliza el método Collections.sort() ya provisto en Java). Finalmente regresa el resultado de concatenar en orden todas las listas numeradas.
public static <T extends Comparable<T>> List<T> bogoSort(List<T> list)
Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento bogo sobre list. El método no debe modificar a list.
Descripción del algoritmo: Empieza con una copia x de list. Si todos los elementos de x se encuentran en su posición correcta (x0 ≤ x1 ≤ x2 ≤ ... ≤ xn-1) entonces ya terminaste. De lo contrario, en cada iteración revuelve al azar todos sus elementos de la copia. Repite esto hasta que en una de esas, por una feliz coincidencia, todos los elementos queden ordenados de manera ascendente. No olvides regresar la lista resultante.
Nota 1: Como te has de imaginar, este algoritmo es extremadamente ineficiente, y en teoría podría nunca terminar, sobre todo con listas de más de unos cuantos elementos.
Nota 2: Para revolver una lista al azar utiliza el método Collections.shuffle() ya provisto en Java.
public static <T extends Comparable<T>> List<T> quickSort(List<T> list)
Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento rápido sobre list. El método no debe modificar a list.
Descripción del algoritmo: Este algoritmo es de naturaleza recursiva. El caso base considera que si list es una lista vacía entonces por definición ya está ordenada, por lo que el método devuelve una lista vacía. En cualquier otro caso se toma el primer elemento de list como “pivote” y se crean dos nuevas listas: una que contenga todos los elementos de list que sean menores que el pivote, y otra lista que contenga todos los elementos de list que sean mayores o iguales al pivote (pero excluyendo al pivote en sí). Se ordenan ambas listas usando este mismo método de manera recursiva. La función finalmente devuelve una lista con los elementos resultantes del ordenamiento recursivo de la primera lista, el pivote, y los elementos resultantes del ordenamiento recursivo de la segunda lista, exactamente en ese orden.
Prueba tu código usando la siguiente clase de JUnit.
package edd.util; import static org.junit.Assert.assertEquals; import java.util.Arrays; import java.util.List; import org.junit.Test; public class TestSorts { private static final List<String> stringListEmpty = Arrays.asList(); private static final List<Integer> integerListEmpty = Arrays.asList(); private static final List<Double> doubleListEmpty = Arrays.asList(); private static final List<Double> doubleList = Arrays.asList( 0.3115440775732701, 0.26535561491023296, 0.5482633610326869, 0.1261965127933492, 0.5281938098544279, 0.2498792562954667, 0.7161109655440545, 0.8709930814574389); private static final List<Double> doubleListSorted = Arrays.asList( 0.1261965127933492, 0.2498792562954667, 0.26535561491023296, 0.3115440775732701, 0.5281938098544279, 0.5482633610326869, 0.7161109655440545, 0.8709930814574389); private static final List<String> stringList = Arrays.asList("Fili", "Kili", "Oin", "Gloin", "Thorin", "Dwalin", "Balin", "Bifur", "Bofur", "Bombur", "Dori", "Nori", "Ori"); private static final List<String> stringListSorted = Arrays.asList("Balin", "Bifur", "Bofur", "Bombur", "Dori", "Dwalin", "Fili", "Gloin", "Kili", "Nori", "Oin", "Ori", "Thorin"); private static final List<Integer> integerList = Arrays.asList(780, 560, 726, 524, 794, 454, 628, 335, 786, 992, 559, 798, 427, 382, 900, 391, 981, 432, 963, 727, 863, 861, 38, 567, 29, 805, 711, 926, 902, 97, 469, 644, 687, 605, 503, 530, 145, 161, 425, 417, 410, 963, 729, 899, 57, 366, 600, 721, 536, 125, 491, 192, 961, 749, 785, 271, 660, 646, 73, 894, 74, 574, 993, 239, 384, 347, 390, 695, 469, 965, 685, 865, 605, 518, 572, 380, 895, 625, 410, 804, 681, 190, 351, 889, 155, 389, 289, 984, 950, 694, 953, 222, 372, 752, 367, 771, 386, 645, 614, 93, 386, 21, 444, 123, 332, 236, 227, 57, 896, 321, 428, 978, 726, 598, 516, 539, 316, 461, 288, 930, 806, 480, 197, 111, 206, 86, 875, 254, 936, 156, 566, 719, 244, 662, 133, 860, 654, 445, 479, 755, 37, 57, 208, 383, 502, 794, 538, 742, 760, 355, 52, 530, 128, 359, 298, 847, 794, 660, 721, 84, 498, 225, 296, 60, 511, 427, 905, 118, 542, 572, 708, 334, 377, 648, 983, 327, 127, 578, 756, 113, 936, 737, 950, 982, 905, 317, 372, 745, 83, 169, 134, 552, 850, 198, 707, 680, 977, 599, 276, 714); private static final List<Integer> integerListSorted = Arrays.asList(21, 29, 37, 38, 52, 57, 57, 57, 60, 73, 74, 83, 84, 86, 93, 97, 111, 113, 118, 123, 125, 127, 128, 133, 134, 145, 155, 156, 161, 169, 190, 192, 197, 198, 206, 208, 222, 225, 227, 236, 239, 244, 254, 271, 276, 288, 289, 296, 298, 316, 317, 321, 327, 332, 334, 335, 347, 351, 355, 359, 366, 367, 372, 372, 377, 380, 382, 383, 384, 386, 386, 389, 390, 391, 410, 410, 417, 425, 427, 427, 428, 432, 444, 445, 454, 461, 469, 469, 479, 480, 491, 498, 502, 503, 511, 516, 518, 524, 530, 530, 536, 538, 539, 542, 552, 559, 560, 566, 567, 572, 572, 574, 578, 598, 599, 600, 605, 605, 614, 625, 628, 644, 645, 646, 648, 654, 660, 660, 662, 680, 681, 685, 687, 694, 695, 707, 708, 711, 714, 719, 721, 721, 726, 726, 727, 729, 737, 742, 745, 749, 752, 755, 756, 760, 771, 780, 785, 786, 794, 794, 794, 798, 804, 805, 806, 847, 850, 860, 861, 863, 865, 875, 889, 894, 895, 896, 899, 900, 902, 905, 905, 926, 930, 936, 936, 950, 950, 953, 961, 963, 963, 965, 977, 978, 981, 982, 983, 984, 992, 993); @Test public void testSelectionSort() { assertEquals(stringListEmpty, Sorts.selectionSort(stringListEmpty)); assertEquals(doubleListSorted, Sorts.selectionSort(doubleList)); assertEquals(doubleListSorted, Sorts.selectionSort(doubleListSorted)); assertEquals(stringListSorted, Sorts.selectionSort(stringList)); assertEquals(stringListSorted, Sorts.selectionSort(stringListSorted)); assertEquals(integerListSorted, Sorts.selectionSort(integerList)); assertEquals(integerListSorted, Sorts.selectionSort(integerListSorted)); } @Test public void testBucketSort() { List<Integer> a = Arrays.asList(84, 44, 30, 74, 57, 62, 28, 3, 8, 17, 29, 90, 42, 83, 24, 65, 6, 14, 48, 25); List<Integer> aSorted = Arrays.asList(3, 6, 8, 14, 17, 24, 25, 28, 29, 30, 42, 44, 48, 57, 62, 65, 74, 83, 84, 90); assertEquals(aSorted, Sorts.bucketSort(a)); assertEquals(aSorted, Sorts.bucketSort(aSorted)); assertEquals(integerListEmpty, Sorts.bucketSort(integerListEmpty)); } @Test public void testBogoSort() { List<Integer> a = Arrays.asList(57, 62, 17, 3, 8, 17, 29, 90); List<Integer> aSorted = Arrays.asList(3, 8, 17, 17, 29, 57, 62, 90); assertEquals(aSorted, Sorts.bogoSort(a)); assertEquals(aSorted, Sorts.bogoSort(aSorted)); assertEquals(doubleListSorted, Sorts.bogoSort(doubleList)); assertEquals(doubleListSorted, Sorts.bogoSort(doubleListSorted)); assertEquals(stringListEmpty, Sorts.bogoSort(stringListEmpty)); assertEquals(doubleListEmpty, Sorts.bogoSort(doubleListEmpty)); } @Test public void testQuickSort() { assertEquals(stringListEmpty, Sorts.quickSort(stringListEmpty)); assertEquals(doubleListSorted, Sorts.quickSort(doubleList)); assertEquals(doubleListSorted, Sorts.quickSort(doubleListSorted)); assertEquals(stringListSorted, Sorts.quickSort(stringList)); assertEquals(stringListSorted, Sorts.quickSort(stringListSorted)); assertEquals(integerListSorted, Sorts.quickSort(integerList)); assertEquals(integerListSorted, Sorts.quickSort(integerListSorted)); } }
Sube el archivo Sorts.java usando el Sistema de Entrega de Tareas Automatizado. No se aceptan tareas por ningún otro medio.
Fecha límite: Martes, 11 de marzo.
Esta actividad será evaluada usando los siguientes criterios:
| 100 | La actividad cumple con todos los requerimientos. |
|---|---|
| -10 | No se incluyó en comentario los datos de los autores. |
| 10 | El programa fuente no compila. |
| 50-90 | El programa produce algunos errores al momento de correrlo. |
| DA | La solución es un plagio. |