Métodos Fundamentales de Ordenación y Búsqueda en Algoritmos

Conceptos Fundamentales de Ordenación

Ordenar significa reorganizar un conjunto de datos u objetos en una secuencia definida. Los métodos de ordenación se clasifican en dos categorías principales:

Ordenación Interna (o de arreglos): Se utiliza cuando los elementos del arreglo se encuentran en la memoria principal de la computadora.
Ordenación Externa (o de archivos): Se utiliza cuando los elementos se encuentran en archivos almacenados en dispositivos de almacenamiento secundario, como discos o cintas.

Clasificación de Métodos de Ordenación Interna

Los métodos de ordenación interna pueden ser clasificados en dos tipos:

Métodos Directos (Complejidad O(n²)): Incluyen algoritmos como Inserción, Selección Directa y Burbuja.
Métodos Logarítmicos (Complejidad O(N log N)): Incluyen algoritmos altamente eficientes como Quicksort, Heapsort y Montículo.

Conceptos de Algoritmos y Eficiencia

Definición de Algoritmo

Un Algoritmo es un conjunto de reglas definidas para resolver un problema. Su ejecución requiere diversos recursos.

Un algoritmo se considera mejor cuanto menos recursos consume. Sin embargo, existen otros criterios importantes:

Facilidad de programación.
Longitud y claridad del código.
Facilidad de entendimiento.
Robustez.

Eficiencia y Complejidad

La Eficiencia de un algoritmo es la cantidad de recursos de cómputo que necesita. Esto se traduce en cuánto tiempo de ejecución y espacio de memoria requiere (también conocido como complejidad).

Factores que Influyen en el Consumo de Recursos

El consumo de recursos de un algoritmo depende de múltiples factores. Consideremos el siguiente ejemplo de pseudocódigo:

i := 0
a[n+1] := x
repetir
    i := i + 1
hasta a[i] == x

La respuesta sobre cuánto tiempo y memoria consume es: Depende (de $n$, $x$, el contenido de $a$, los tipos de datos y la máquina).

Factores Externos

La máquina donde se ejecute.
El lenguaje de programación y el compilador usado.
La implementación que haga el programador del algoritmo, en particular, las estructuras de datos utilizadas.

Factores Relacionados con los Datos de Entrada

Tamaño de los datos de entrada: Ejemplo: Procesar un archivo de log con N líneas.
Contenido de los datos de entrada:
- Mejor Caso (tₚ): El contenido favorece una rápida ejecución.
- Peor Caso (tₜ): La ejecución más lenta posible.
- Caso Promedio (tₚ): Media de todos los posibles contenidos.

Complejidad de los Algoritmos y Notación Asintótica

Los tiempos y el espacio de complejidad de los algoritmos se analizan utilizando la Notación Asintótica.

Notación Asintótica

La notación asintótica describe el comportamiento de la complejidad del tiempo y espacio que un algoritmo necesita. Establece una función que describe el comportamiento de un algoritmo, utilizando lenguaje matemático.

La Notación O Grande (Big O)

La notación de la O (O Grande) provee de los límites superiores de la función $f$.

Definición Formal

Dada una función $f: N \to R^+$, la clase $O(f)$ (que se lee O-grande de f) se define por:

$$O(f) = \{g : N \to R^+ \mid \exists c \in R^+, \exists n_0 \in N : \forall n \ge n_0, g(n) \le c f(n)\}$$

Intuitivamente, esta definición refleja que el crecimiento asintótico de las funciones $g$ es, como mucho, proporcional al de la función $f$. Informalmente, la tasa de crecimiento de la función $f$ es una cota superior para las tasas de crecimiento de las funciones $g$.

Algoritmos de Ordenación Interna

Inserción Directa (Insertion Sort)

A continuación, se presenta el pseudocódigo del algoritmo de Inserción (asumiendo que a es un arreglo de n elementos):

Insercion(a, n)
1.- Repetir con i = 2 hasta n
    Hacer aux = a[i] y k = i - 1
    1.1 Repetir mientras (k >= 1) y (aux < a[k])
        Hacer a[k+1] = a[k]
        k = k - 1
    1.2 // Fin ciclo del paso 1.1
    Hacer a[k+1] = aux
    i = i + 1
2.- // Fin del ciclo paso 1

Selección Directa (Selection Sort)

Seleccion(a, n)
1.- Repetir con i = 1 hasta n - 1
    Hacer menor = a[i] y k = i
    1.1 Repetir con j desde i + 1 hasta n
        1.1.1 Si a[j] < menor entonces
            Hacer menor = a[j] y k = j
        1.1.2 // Fin del paso 1.1.1
        j = j + 1
    1.2 // Fin del ciclo del paso 1.1
    Hacer a[k] = a[i]
    a[i] = menor
2.- // Fin del paso 1

Método de Shell (Shellsort)

Este método es una versión mejorada del método de Inserción Directa, llamado así en honor a su autor, Donald L. Shell.

Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño, pero con incrementos decrecientes. El tiempo de ejecución de este método es del orden $O(n^{3/2})$ o mejor, dependiendo de la secuencia de saltos.

Shell(a, n) // Arreglo a de n elementos
1.- Hacer inter = n + 1
2.- Repetir mientras (inter > 1)
    Hacer inter = parte_entera(inter / 2)
    band = 1
    2.1 Repetir mientras (band = 1)
        Hacer band = 0 e i = 1
        2.1.1 Repetir mientras ((i + inter) ≤ n)
            2.1.1.1 Si a[i] > a[i + inter] entonces
                Hacer aux = a[i], a[i] = a[i + inter]
                a[i + inter] = aux y band = 1
            2.1.1.2 // Fin de 2.1.1.1
            Hacer i = i + 1
        2.1.2 // Fin de 2.1.1
    2.2 // Fin de 2.1
3.- // Fin de 2

Método Quicksort

Actualmente, Quicksort es considerado uno de los algoritmos de ordenación más eficientes y veloces.

La idea central de este algoritmo es:

Se toma un elemento x (pivote) de una posición cualquiera del arreglo.
Se ubica x en la posición correcta del arreglo, de tal forma que todos los elementos a su derecha sean mayores o iguales a x, y los de la izquierda sean menores o iguales.
Se repiten los pasos anteriores de forma recursiva para los subconjuntos de datos que se encuentran a la izquierda y la derecha de x.
El proceso termina cuando todos los elementos se encuentran en su posición correcta en el arreglo.

Pseudocódigo Recursivo de Quicksort

recursivo(ini, fin)
1.- Hacer izq = ini, der = fin, pos = ini y band = V (Verdadero)
2.- Repetir mientras (band == V)
    Hacer band = F (Falso)
    2.1 Repetir mientras (A[pos] ≤ A[der] y pos <> der)
        Hacer der = der - 1
    2.2 // Fin de ciclo paso 2.1
    2.3 Si pos <> der entonces
        Hacer aux = A[pos], A[pos] = A[der], A[der] = aux y pos = der
        2.3.1 Repetir mientras (A[pos] ≥ A[izq] y pos <> izq)
            Hacer izq = izq + 1
        2.3.2 // Fin del ciclo paso 2.3.1
        2.3.3 Si pos <> izq entonces
            Hacer band = V, aux = A[pos], A[pos] = A[izq], A[izq] = aux y pos = izq
        2.3.4 // Fin de la condición 2.3.3
    2.4 // Fin de condición del paso 2.3
3.- // Fin del ciclo paso 2

4.- Si (pos - 1) > ini entonces
    recursivo(ini, pos - 1) // Llamada recursiva izquierda
5.- // Fin del paso 4

6.- Si fin > (pos + 1) entonces
    recursivo(pos + 1, fin) // Llamada recursiva derecha

Algoritmos de Búsqueda

Búsqueda Binaria

La Búsqueda Binaria consiste en dividir el intervalo de búsqueda en dos partes, comparando el elemento buscado con el elemento central. En caso de no ser iguales, se redefinen los extremos del intervalo.

Importante: Este método funciona solo para arreglos ordenados.

Pseudocódigo de Búsqueda Binaria

Binaria(v, n, x) // Busca el elemento x en el vector v de n componentes
1.- Hacer izq = 1, der = n y b = 0
2.- Repetir mientras (izq ≤ der) y (b = 0)
    Hacer cen = parte_entera((izq + der) / 2)
    2.1 Si x = v[cen] entonces
        Hacer b = 1
    sino // Redefinir intervalo de búsqueda
        2.1.1 Si x > v[cen] entonces
            Hacer izq = cen + 1
        sino
            Hacer der = cen - 1
        2.1.2 // Fin de 2.1.1
    2.2 // Fin de 2.1
3.- // Fin de ciclo 2
4.- Si b = 1 entonces
    Escribir “El elemento está en cen”
sino
    Escribir “El elemento no está en el arreglo”
5.- // Fin de 4

Búsqueda por Transformación de Claves (Hashing)

El Hashing permite tener acceso directamente a los datos.

Se utilizan funciones Hash para calcular el índice en el cual se almacenará el dato y, posteriormente, buscarlo.
Se utiliza un método para solucionar colisiones, las cuales se generan cuando se intenta insertar un dato en un índice que ya se encuentra ocupado.

Funciones Hash

Es crucial seleccionar una buena función hash. A continuación, se presentan algunas:

Función Módulo (por División)

$$H(k) = (k \mod N) + 1$$

$K$: clave a transformar.
$N$: cantidad de elementos.
$H(k)$: índice generado.

Ejemplo: $N=100$. Si $k_1=7259$ y $k_2=9359$.

$$H(k_1) = (7259 \mod 100) + 1 = 60$$

$$H(k_2) = (9359 \mod 100) + 1 = 60$$

Función Cuadrado

$$H(k) = \text{dígitos\_centrales}(k^2) + 1$$

Ejemplo: $N=100, k=7259$.

$$K^2 = 52,693,081$$

$$H(k) = \text{dígitos\_centrales}(52,693,081) + 1 = 94$$

Función Plegamiento (Folding)

$$H(k) = \text{dígitos\_menos\_sig}((d_1\dots d_i) + (d_{i+1}\dots d_j) + \dots + (d_l\dots d_n)) + 1$$

Ejemplo: Usando valores anteriores ($k=7259$).

$$H(k) = \text{dígitos\_menos\_sig}(72 + 59) + 1 = \text{dígitos\_menos\_sig}(131) + 1 = 32$$

Función Truncamiento

Consiste en tomar algunos dígitos de la clave y formar con ellos un índice.

$$H(k) = \text{elegir\_dígitos}(d_1, d_2, \dots d_n) + 1$$

Ejemplo: $k=7259$. Si se elige el primer (7) y tercer (5) dígito, se forma 75.

$$H(k) = \text{elegir\_dígitos}(7259) + 1 = 76$$

Este método también se puede aplicar a claves alfabéticas o alfanuméricas.

Solución de Colisiones

Una colisión ocurre cuando se generan dos índices iguales con diferentes claves. Los métodos para solucionar colisiones se clasifican en:

Reasignación (Direccionamiento Abierto).
Arreglos Anidados.
Encadenamiento (Direccionamiento Cerrado).

1. Reasignación (Direccionamiento Abierto)

Consiste en buscar una nueva posición dentro del arreglo principal cuando ocurre una colisión.

Prueba Lineal: Una vez detectada la colisión, recorre el arreglo en forma secuencial, a partir del punto de la colisión, buscando la siguiente localidad vacía (para inserción) o el elemento (para búsqueda).
Prueba Cuadrática: Es similar a la prueba lineal, pero las direcciones se generan mediante incrementos cuadráticos: $D+1, D+4, D+9, \dots, D+I^2$.
Doble Dirección Hash: Una vez detectada la colisión, se genera otra dirección hash utilizando una segunda función, tomando como clave la dirección anterior. El proceso termina cuando se halla el dato o se encuentra una posición vacía.

2. Arreglos Anidados

Consiste en que cada elemento del arreglo principal contenga otro arreglo (o vector) con las claves que han colisionado. Este método puede ser sencillo conceptualmente, pero resulta poco práctico en la implementación real.

3. Encadenamiento (Direccionamiento Cerrado)

Consiste en que cada elemento del arreglo principal contiene un apuntador a una lista ligada. La lista ligada contendrá los valores colisionados.

Una desventaja es que ocupa espacio adicional al del vector e implica el manejo de listas ligadas. Si las listas crecen demasiado, se pierde la facilidad de acceso directo que proporciona el hashing.