Práctica 4: Ordenamientos

Descripción

Esta actividad puede ser elaborada de manera individual o en parejas.

Escribe una clase llamada mx.itesm.cem.ordenamientos.Exercises. 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.

Métodos a implementar

1. 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.

2. 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.

3. 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 (x₀ ≤ x₁ ≤ x₂ ≤ ... ≤ x_n-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.

4. 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.

Pruebas unitarias

Prueba tu código usando la siguiente clase de JUnit:

package mx.itesm.cem.ordenamientos;

import static org.junit.Assert.assertEquals;
import java.util.Arrays;
import java.util.List;
import org.junit.Test;

public class ExercisesTest {

    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,
                Exercises.selectionSort(stringListEmpty));
        assertEquals(doubleListSorted,
                Exercises.selectionSort(doubleList));
        assertEquals(doubleListSorted,
                Exercises.selectionSort(doubleListSorted));
        assertEquals(stringListSorted,
                Exercises.selectionSort(stringList));
        assertEquals(stringListSorted,
                Exercises.selectionSort(stringListSorted));
        assertEquals(integerListSorted,
                Exercises.selectionSort(integerList));
        assertEquals(integerListSorted,
                Exercises.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, Exercises.bucketSort(a));
        assertEquals(aSorted,
                Exercises.bucketSort(aSorted));
        assertEquals(integerListEmpty,
                Exercises.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, Exercises.bogoSort(a));
        assertEquals(aSorted, Exercises.bogoSort(aSorted));
        assertEquals(doubleListSorted,
                Exercises.bogoSort(doubleList));
        assertEquals(doubleListSorted,
                Exercises.bogoSort(doubleListSorted));
        assertEquals(stringListEmpty,
                Exercises.bogoSort(stringListEmpty));
        assertEquals(doubleListEmpty,
                Exercises.bogoSort(doubleListEmpty));
    }

    @Test
    public void testQuickSort() {
        assertEquals(stringListEmpty,
                Exercises.quickSort(stringListEmpty));
        assertEquals(doubleListSorted,
                Exercises.quickSort(doubleList));
        assertEquals(doubleListSorted,
                Exercises.quickSort(doubleListSorted));
        assertEquals(stringListSorted,
                Exercises.quickSort(stringList));
        assertEquals(stringListSorted,
                Exercises.quickSort(stringListSorted));
        assertEquals(integerListSorted,
                Exercises.quickSort(integerList));
        assertEquals(integerListSorted,
                Exercises.quickSort(integerListSorted));
    }
}

¿Qué se debe entregar?

Tu archivo fuente de Java debe comenzar con un comentario que contenga el título de la práctica, la fecha y los datos personales de los autores (matrícula y nombre). Por ejemplo:

/*----------------------------------------------------------
 * Práctica 4: Ordenamientos
 * Fecha: 08-Mar-2018
 * Autores:
 *           A01166611 Pepper Pots
 *           A01160611 Anthony Stark
 *----------------------------------------------------------*/

Si la práctica fue desarrollada en pareja, basta que solo uno de los miembros la entregue.

La fecha límite es el jueves 8 de marzo.

Evaluación

Esta actividad será evaluada usando los siguientes criterios:

-10	No se incluyó en comentario los datos de los autores.
10-100	Dependiendo del número de métodos correctamente implementados.
10	El programa no compila.
1	El programa es un plagio total o parcial.