Capítulo 3: Algoritmos de Ordenación

La ordenación es el proceso de reorganizar una secuencia de objetos para ponerlos en un orden lógico. Por ejemplo, tu factura de tarjeta de crédito presenta las transacciones en orden por fecha, y pones tus libros en orden en tu estantería alfabéticamente por autor y título. La ordenación es una operación fundamental en la ciencia de la computación, y juega un papel crucial en muchas aplicaciones. Hay una variedad de algoritmos de ordenación clásicos que encarnan diferentes enfoques a este problema.

En este capítulo, consideramos varios métodos de ordenación clásicos y una estructura de datos importante conocida como la cola de prioridad. Comenzamos con una discusión de varios métodos de ordenación elementales, incluyendo la ordenación por selección, la ordenación por inserción y la ordenación de Shell. Estos métodos se utilizan apropiadamente en muchas aplicaciones, pero para problemas grandes, recurrimos a la ordenación por fusión y la ordenación rápida, dos algoritmos de ordenación recursivos que se pueden utilizar para ordenar un gran número de elementos. Concluimos con una discusión de las colas de prioridad y su uso en la ordenación y otras aplicaciones.

Ordenaciones Elementales

Los algoritmos de ordenación más simples realizan las siguientes operaciones:

Ordenación por selección: Encuentra el elemento más pequeño e intercámbialo con la primera entrada, luego encuentra el segundo elemento más pequeño e intercámbialo con la segunda entrada, etc.
Ordenación por inserción: Toma cada elemento a su vez e insértalo en la posición apropiada entre los ya considerados (manteniéndolos ordenados).

Estas operaciones reflejan cómo los humanos típicamente realizan tareas de ordenación y son efectivas para tamaños de problemas pequeños. Sin embargo, no escalan bien y se vuelven poco prácticas para ordenar matrices grandes.

Ordenación por Selección

La ordenación por selección es un algoritmo de ordenación simple que funciona de la siguiente manera: Primero, encuentra el elemento más pequeño de la matriz e intercámbialo con la primera entrada (él mismo si la primera entrada ya es el más pequeño). Luego, encuentra el siguiente elemento más pequeño e intercámbialo con la segunda entrada. Continúa de esta manera hasta que toda la matriz esté ordenada.

El bucle interno de la selecAquí está la traducción al español del archivo Markdown, con los comentarios traducidos y el código sin traducir:

El algoritmo de selección se usa para encontrar el elemento mínimo en el subarreglo no ordenado a[i..N-1]. El índice del elemento mínimo se almacena en min. Luego, a[i] se intercambia con a[min], lo que coloca el elemento mínimo en su posición final. A medida que el índice i viaja de izquierda a derecha, los elementos a su izquierda están en orden ascendente en el arreglo y no se volverán a tocar.

Aquí hay una implementación del algoritmo de selección en Java:

public static void selectionSort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int min = i;
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        exch(a, i, min);
    }
}

El algoritmo de selección usa aproximadamente ~N^2/2 comparaciones y N intercambios para ordenar un arreglo de longitud N. El tiempo de ejecución no es sensible a la entrada: tarda aproximadamente lo mismo en ejecutarse el algoritmo de selección para un arreglo que ya está ordenado o para un arreglo con todas las claves iguales que para un arreglo con un orden aleatorio.

Ordenamiento por inserción

El ordenamiento por inserción es otro algoritmo de ordenamiento simple que funciona construyendo el arreglo final ordenado un elemento a la vez. Es mucho menos eficiente en arreglos grandes que algoritmos más avanzados como quicksort, heapsort o mergesort, pero tiene algunas ventajas:

Es eficiente para conjuntos de datos pequeños.
Es más eficiente en la práctica que el algoritmo de selección.
Es estable; es decir, no cambia el orden relativo de los elementos con claves iguales.
Es in-place; es decir, solo requiere una cantidad constante O(1) de espacio de memoria adicional.
Es en línea; es decir, puede ordenar una lista a medida que la recibe.

Aquí hay una implementación del ordenamiento por inserción en Java:

public static void insertionSort(Comparable[] a) {
    int N = a.length;
    for (int i = 1; i < N; i++) {
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            exch(a, j, j-1);
        }
    }
}

El bucle interno del ordenamiento por inserción mueve los elementos más grandes una posición a la derecha, dejando espacio para insertar el elemento actual.Aquí está la traducción al español del archivo Markdown, con los comentarios traducidos, pero sin traducir el código:

El tiempo de ejecución de la ordenación por inserción depende del orden inicial de los elementos en la entrada. Por ejemplo, si la matriz es grande y sus entradas ya están ordenadas (o casi ordenadas), entonces la ordenación por inserción es mucho, mucho más rápida que si las entradas están ordenadas aleatoriamente o en orden inverso.

Ordenación de Shell (Shellsort)

La ordenación de Shell es una extensión simple de la ordenación por inserción que gana velocidad al permitir intercambios de entradas de matriz que están muy separadas, para producir matrices parcialmente ordenadas que se pueden ordenar eficientemente, eventualmente por ordenación por inserción.

La idea es reorganizar la matriz para darle la propiedad de que tomar cada h-ésima entrada (comenzando en cualquier lugar) produce una subsecuencia ordenada. Dicha matriz se dice que está h-ordenada. Dicho de otra manera, una matriz h-ordenada es h subsecuencias ordenadas independientes, entrelazadas. Al h-ordenar para algunos valores grandes de h, podemos mover elementos en la matriz a largas distancias y así facilitar el h-ordenamiento para valores más pequeños de h. Usando tal procedimiento para cualquier secuencia de valores de h que termine en 1 producirá una matriz ordenada: eso es la ordenación de Shell.

Aquí hay una implementación de la ordenación de Shell en Java:

public class MaxPQ<Key extends Comparable<Key>> {
    // Declaración de variables
    
    // Inicializar la cola de prioridad máxima
    public MaxPQ(int capacity) {
        // Implementación
    }
   
    // Verificar si la cola de prioridad está vacía
    public boolean isEmpty() {
        // Implementación
    }
   
    // Insertar un elemento en la cola de prioridad
    public void insert(Key key) {
        // Implementación
    }
   
    // Eliminar y devolver el elemento máximo de la cola de prioridad
    public Key delMax() {
        // Implementación
    }
   
    // Hacer que el elemento en la posición k suba en la cola de prioridad
    private void swim(int k) {
        // Implementación
    }
   
    // Hacer que el elemento en la posición k baje en la cola de prioridad
    private void sink(int k) {
        // Implementación
    }
   
    // Comparar dos elementos en la cola de prioridad
    private boolean less(int i, int j) {
        // Implementación
    }
}
```Aquí está la traducción al español del archivo Markdown, con los comentarios traducidos al español y el código sin traducir:
 
n menos(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
 
    private void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}

Este código implementa un montículo binario orientado a máximo utilizando un arreglo pq para almacenar el árbol binario completo ordenado por montículo. Las operaciones insert() y delMax() mantienen el invariante del montículo utilizando los métodos auxiliares swim() y sink() para restaurar el orden del montículo intercambiando claves con un padre más grande que un hijo o un hijo más grande que su padre, respectivamente.

Cronómetro

Un tipo de datos abstracto más útil es una abstracción simple y efectiva para un cronómetro, que se muestra en la página opuesta. Para usarlo, cree un objeto Cronómetro cuando desee iniciar el temporizador, luego use el método elapsedTime() para obtener el tiempo transcurrido en segundos desde que se creó el objeto. La implementación utiliza System.currentTimeMillis() de Java para obtener la hora actual en milisegundos desde la medianoche del 1 de enero de 1970.

La variable de instancia start registra el momento en que se creó el cronómetro, y elapsedTime() usa start para calcular el tiempo transcurrido. El cliente mostrado es típico: realiza algún cálculo y usa un Cronómetro para medir cuánto tiempo tarda el cálculo. El tipo de datos Cronómetro es una abstracción efectiva porque separa el concepto de un cronómetro (la interfaz) de la implementación (usando System.currentTimeMillis() de Java). Esta separación de interfaz e implementación es una característica fundamental de los tipos de datos abstractos que veremos en cada ADT a lo largo del libro.

Resumen

Los tipos de datos abstractos son un elemento esencial de la programación orientada a objetos que se utilizan ampliamente en la programación moderna. En esta sección, hemos visto:

Definir un tipo de datos abstracto como una clase de Java, con variables de instancia para definir los valores del tipo de datos e métodos de instancia para implementar las operaciones en esos valores.
Desarrollar múltiples implementaciones de la misma API, utilizando diferentes representaciones del mismo dato abstracto.Tipo de datos abstractos.
Distinguir entre APIs, clientes e implementaciones de un tipo de datos abstracto.
Diseñar APIs para tipos de datos abstractos.
Desarrollar clientes y clientes de prueba para su uso en pruebas y depuración.
Razonar sobre la corrección de una implementación de tipo de datos abstracto, utilizando aserciones.
Comparar el rendimiento de diferentes implementaciones del mismo API.

Estas actividades son una parte esencial del desarrollo de cualquier programa Java. Cada programa Java que escribamos involucrará el uso de tipos de datos abstractos de bibliotecas; muchos implicarán el desarrollo de nuevos tipos de datos abstractos. En la siguiente sección, consideramos tres tipos de datos abstractos fundamentales que son componentes esenciales en una gran cantidad de programas, y en la Sección 1.4 consideramos el proceso de analizar las características de rendimiento de las implementaciones en detalle.

Chapter 2 Algorithms Fundamentals Chapter 4 Searching Algorithms