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.
Usando el lenguaje de programación Java versión 7, escribe los métodos que se describen a continuación. Coloca todos los métodos en una clase pública llamada Sorts dentro de un paquete llamado tc1018.util. En la parte superior del archivo coloca en comentarios los datos personales de los autores de la tarea. Por ejemplo:
/*-------------------------------------------------------------------- * Actividad de programación: Ordenamientos * Fecha: 03-Mar-2013 * Autores: * 1166611 Pepper Pots * 1160611 Anthony Stark *--------------------------------------------------------------------*/
Prueba tu código usando la siguiente clase de JUnit.
package tc1018.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 testMergeSort() { List<Integer> a = Arrays.asList(3, 4, 6, 6, 7, 8, 10); List<Integer> b = Arrays.asList(1, 2, 3, 4, 5, 6, 6, 10, 15); List<Integer> abSorted = Arrays.asList(1, 2, 3, 3, 4, 4, 5, 6, 6, 6, 6, 7, 8, 10, 10, 15); assertEquals(abSorted, Sorts.mergeSort(a, b)); assertEquals(doubleListSorted, Sorts.mergeSort(doubleListEmpty, doubleListSorted)); assertEquals(stringListSorted, Sorts.mergeSort(stringListSorted, stringListEmpty)); assertEquals(integerListSorted, Sorts.mergeSort(integerListEmpty, integerListSorted)); assertEquals(integerListEmpty, Sorts.mergeSort(integerListEmpty, integerListEmpty)); } @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)); } }
public static <T extends Comparable<? super 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. La función 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 <T extends Comparable<? super T>> List<T> mergeSort(List<T> list1, List<T> list2)
Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento por mezcla sobre list1 y list2. Las listas list1 y list2 deben llegar ya ordenadas de forma ascendente. La función no debe modificar a list1 ni a list2.
Descripción del algoritmo: Empieza con una lista resultante vacía y copias de list1 y list2. En cada iteración determina quien tiene al inicio el elemento x más pequeño de entre las copias de list1 y list2 (recuerda que tanto list1 y list2 están ordenadas de forma ascendente, por lo que los elementos más pequeños siempre estarán al mero inicio de cada una de estas listas). Remueve a x de la lista que lo contiene y añádelo al final de la lista resultante. Las iteraciones terminan cuando alguna de las copias de list1 o list2 queda vacía. En ese momento hay que copiar a la lista resultante todos los elementos que quedaron en la lista que aún no está 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. La función 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<? super T>> List<T> bogoSort(List<T> list)
Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento bogo sobre list. La función 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 incremental. 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<? super T>> List<T> quickSort(List<T> list)
Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento rápido sobre list. La función 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 la función 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 esta misma función 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.
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: Domingo, 3 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. |