📗 Temario Maestro EDA — Estructura de Datos y Algoritmos (Java)

1º Grado en Ingeniería Informática · UAX · Convocatoria extraordinaria · Hoja de teoría completa desde cero: abstracción y encapsulación, complejidad (Big-O), todos los métodos de ordenación, estructuras de datos, búsqueda y recursión. Todo el código está compilado y ejecutado.

1 · Java desde cero: los términos que usa todo lo demás

class Coche {
    // ATRIBUTOS: los datos que guarda cada objeto de esta clase
    String marca;
    int velocidad;

    // CONSTRUCTOR: se ejecuta al hacer "new" y deja el objeto listo
    Coche(String marca) {
        this.marca = marca;    // this.marca = el atributo; marca = el parámetro
        this.velocidad = 0;
    }

    // MÉTODOS: las acciones que el objeto sabe hacer
    void acelerar(int cuanto) {
        velocidad = velocidad + cuanto;
    }

    void mostrar() {
        System.out.println(marca + " va a " + velocidad + " km/h");
    }
}

Y un programa que usa la clase (el método main es el punto de entrada: es static porque se ejecuta sin necesidad de crear ningún objeto antes):

public static void main(String[] args) {
    Coche c1 = new Coche("Seat");     // new crea el OBJETO; c1 guarda su referencia
    Coche c2 = new Coche("Toyota");   // otro objeto DISTINTO, con sus propios datos

    c1.acelerar(50);
    c1.acelerar(30);
    c2.acelerar(20);

    c1.mostrar();     // cada objeto recuerda SU estado
    c2.mostrar();

    Coche c3 = c1;    // ¡OJO! esto NO copia el coche: c3 apunta al MISMO objeto
    c3.acelerar(40);
    c1.mostrar();     // el cambio hecho "por c3" se ve por c1: son el mismo coche
}

Seat va a 80 km/h
Toyota va a 20 km/h
Seat va a 120 km/h

Tipos primitivos vs objetos

Java tiene 8 tipos primitivos (no son objetos, guardan directamente el valor): int (enteros), double (decimales), boolean (true/false), char (un carácter), y las variantes long, float, short, byte. Todo lo demás (String, arrays, tus clases) son objetos y se manejan por referencia.

static significa "de la clase, no de cada objeto": un método static (como main o Math.max) se llama sin crear objetos. this es, dentro de un método, la referencia al objeto sobre el que se ha llamado; se usa sobre todo para distinguir atributo de parámetro: this.marca = marca;

2 · Abstracción y encapsulación

2.1 Los modificadores de visibilidad

2.2 Clase bien encapsulada: atributos privados + constructor con validación + getters/setters

Compara una clase mal hecha con su versión correcta:

class ProductoMal {           // ASÍ NO: todo público, sin ningún control
    public String nombre;
    public double precio;
    public int stock;
}

class Producto {
    private String nombre;    // privados: solo la propia clase los toca
    private double precio;
    private int stock;

    public Producto(String nombre, double precio, int stock) {
        this.nombre = nombre;
        setPrecio(precio);    // reutilizo la validación de los setters
        setStock(stock);
    }

    public String getNombre() { return nombre; }
    public double getPrecio() { return precio; }
    public int    getStock()  { return stock; }

    // SETTERS con validación: el objeto nunca queda en un estado absurdo
    public void setPrecio(double precio) {
        if (precio < 0) throw new IllegalArgumentException("Precio negativo: " + precio);
        this.precio = precio;
    }
    public void setStock(int stock) {
        if (stock < 0) throw new IllegalArgumentException("Stock negativo: " + stock);
        this.stock = stock;
    }

    public void vender(int unidades) {
        if (unidades <= 0 || unidades > stock) {
            System.out.println("Venta imposible de " + unidades + " uds de " + nombre);
            return;
        }
        stock -= unidades;
    }
}

Ejemplo completo con reglas de negocio (fíjate: no hay setSaldo a propósito, porque el saldo solo debe cambiar por operaciones controladas):

class CuentaBancaria {
    // 1. ATRIBUTOS PRIVADOS: nadie puede tocarlos directamente desde fuera
    private String titular;
    private double saldo;

    // 2. CONSTRUCTOR con validación: es imposible crear una cuenta inválida
    public CuentaBancaria(String titular, double saldoInicial) {
        if (titular == null || titular.isEmpty()) {
            throw new IllegalArgumentException("El titular es obligatorio");
        }
        if (saldoInicial < 0) {
            throw new IllegalArgumentException("El saldo inicial no puede ser negativo");
        }
        this.titular = titular;        // this.titular = atributo; titular = parámetro
        this.saldo = saldoInicial;
    }

    // 3. GETTERS: lectura controlada. OJO: no hay setSaldo() a propósito,
    //    el saldo SOLO cambia a través de depositar() y retirar().
    public String getTitular() { return titular; }
    public double getSaldo()   { return saldo; }

    // 4. OPERACIONES con validación (aquí vive la lógica de la clase)
    public void depositar(double cantidad) {
        if (cantidad <= 0) {
            System.out.println("Depósito rechazado: la cantidad debe ser positiva");
            return;                     // la operación inválida se ignora
        }
        saldo += cantidad;
    }

    public boolean retirar(double cantidad) {
        if (cantidad <= 0 || cantidad > saldo) {
            return false;               // nunca se permite dejar el saldo negativo
        }
        saldo -= cantidad;
        return true;
    }

    @Override
    public String toString() {
        return "Cuenta de " + titular + " | saldo: " + saldo + " EUR";
    }
}

Programa de prueba y su salida real:

public static void main(String[] args) {
    CuentaBancaria c = new CuentaBancaria("Ana Pérez", 100.0);
    System.out.println(c);

    c.depositar(50);
    System.out.println("Tras depositar 50 -> saldo = " + c.getSaldo());

    System.out.println("¿Puedo retirar 500? " + c.retirar(500)
            + " (saldo sigue en " + c.getSaldo() + ")");
    System.out.println("¿Puedo retirar 80?  " + c.retirar(80)
            + " -> saldo = " + c.getSaldo());

    c.depositar(-10);
    System.out.println("Saldo final: " + c.getSaldo());
}

Cuenta de Ana Pérez | saldo: 100.0 EUR
Tras depositar 50 -> saldo = 150.0
¿Puedo retirar 500? false (saldo sigue en 150.0)
¿Puedo retirar 80?  true -> saldo = 70.0
Depósito rechazado: la cantidad debe ser positiva
Saldo final: 70.0

2.3 Herencia: extends y super

2.4 Clases abstractas y métodos abstractos

abstract class Figura {
    private String nombre;                 // atributo común, encapsulado

    public Figura(String nombre) { this.nombre = nombre; }

    public String getNombre() { return nombre; }

    // Métodos ABSTRACTOS: se declaran pero NO se implementan aquí,
    // porque cada figura calcula su área y su perímetro de forma distinta.
    public abstract double area();
    public abstract double perimetro();

    // Método CONCRETO heredado por todas las hijas (usa los abstractos):
    public void describir() {
        System.out.println(nombre + " -> área = " + redondear(area())
                + ", perímetro = " + redondear(perimetro()));
    }

    private static double redondear(double v) {   // 2 decimales
        return Math.round(v * 100) / 100.0;
    }
}

class Circulo extends Figura {
    private double radio;

    public Circulo(double radio) {
        super("Círculo de radio " + radio);   // llama al constructor del padre
        this.radio = radio;
    }
    @Override public double area()      { return Math.PI * radio * radio; }
    @Override public double perimetro() { return 2 * Math.PI * radio; }
}

class Rectangulo extends Figura {
    private double base, altura;

    public Rectangulo(double base, double altura) {
        super("Rectángulo " + base + "x" + altura);
        this.base = base;
        this.altura = altura;
    }
    @Override public double area()      { return base * altura; }
    @Override public double perimetro() { return 2 * (base + altura); }
}

2.5 Polimorfismo

public static void main(String[] args) {
    // POLIMORFISMO: un array del tipo PADRE guarda objetos de las HIJAS
    Figura[] figuras = {
        new Circulo(3),
        new Rectangulo(4, 5),
        new Circulo(1)
    };
    double total = 0;
    for (Figura f : figuras) {   // la MISMA llamada...
        f.describir();           // ...ejecuta un código distinto según el objeto
        total += f.area();
    }
    System.out.println("Suma de todas las áreas: " + Math.round(total * 100) / 100.0);
    // Figura f = new Figura("x");  // NO COMPILA: una clase abstracta no se instancia
}

Círculo de radio 3.0 -> área = 28.27, perímetro = 18.85
Rectángulo 4.0x5.0 -> área = 20.0, perímetro = 18.0
Círculo de radio 1.0 -> área = 3.14, perímetro = 6.28
Suma de todas las áreas: 51.42

2.6 Interfaces

2.7 Sobrescritura vs sobrecarga (¡no confundir!)

@Override es una anotación opcional pero muy recomendable: le pide al compilador que compruebe que de verdad estás sobrescribiendo algo (si te equivocas en la firma, avisa).

Ejemplo completo que junta TODO (interfaz + abstracta + herencia + polimorfismo + sobrecarga + instanceof):

interface Bonificable {
    double bonus();               // CONTRATO: quien lo implemente DEBE tener bonus()
}

abstract class Empleado {
    private String nombre;
    private double salarioBase;

    public Empleado(String nombre, double salarioBase) {
        this.nombre = nombre;
        this.salarioBase = salarioBase;
    }
    public String getNombre()      { return nombre; }
    public double getSalarioBase() { return salarioBase; }

    // SOBRECARGA (overloading): mismo nombre, PARÁMETROS distintos, misma clase
    public void subirSalario(double cantidad)     { salarioBase += cantidad; }
    public void subirSalario(double c, int veces) { salarioBase += c * veces; }

    // Cada tipo de empleado calcula su salario a su manera:
    public abstract double salarioMensual();

    @Override
    public String toString() {
        return nombre + " cobra " + salarioMensual() + " EUR";
    }
}

class EmpleadoFijo extends Empleado implements Bonificable {
    private int trienios;

    public EmpleadoFijo(String nombre, double salarioBase, int trienios) {
        super(nombre, salarioBase);
        this.trienios = trienios;
    }
    // SOBRESCRITURA (overriding): MISMA firma que el padre, redefinida en la hija
    @Override public double salarioMensual() {
        return getSalarioBase() + 50 * trienios + bonus();
    }
    @Override public double bonus() { return 100; }
}

class EmpleadoTemporal extends Empleado {
    private int horasExtra;

    public EmpleadoTemporal(String nombre, double salarioBase, int horasExtra) {
        super(nombre, salarioBase);
        this.horasExtra = horasExtra;
    }
    @Override public double salarioMensual() {
        return getSalarioBase() + 15 * horasExtra;
    }
}

public static void main(String[] args) {
    List<Empleado> plantilla = new ArrayList<>();
    plantilla.add(new EmpleadoFijo("Lucía", 1500, 2));
    plantilla.add(new EmpleadoTemporal("Marcos", 1100, 10));

    for (Empleado e : plantilla) {
        System.out.println(e);              // polimorfismo: cada uno usa SU salarioMensual()
        if (e instanceof Bonificable) {     // ¿cumple este objeto el contrato Bonificable?
            System.out.println("   (incluye bonus de " + ((Bonificable) e).bonus() + ")");
        }
    }
    plantilla.get(1).subirSalario(50);      // usa la sobrecarga de 1 parámetro
    plantilla.get(1).subirSalario(10, 3);   // usa la sobrecarga de 2 parámetros
    System.out.println("Marcos tras las subidas: " + plantilla.get(1).salarioMensual());
}

Lucía cobra 1700.0 EUR
   (incluye bonus de 100.0)
Marcos cobra 1250.0 EUR
Marcos tras las subidas: 1330.0

3 · Complejidad: la notación O grande desde cero

3.1 El método de 5 pasos para determinar la complejidad de un código (escríbelos en el examen)

1. Di cuál es el tamaño del problema n (casi siempre n = a.length o el parámetro n). Sin esto no hay nota completa.
2. Para cada bucle: ¿cuántas vueltas da y de qué depende? (contador +1 → n vueltas; contador ×2 o ÷2 → log₂ n vueltas).
3. ¿El bucle interno depende del externo? (p. ej. j <= i) → no multipliques: plantea la SUMA del trabajo real.
4. Bucles seguidos se SUMAN (gana el dominante); bucles anidados independientes se MULTIPLICAN.
5. Quédate con el término dominante y tira las constantes: 2n+10 → O(n); n²/2 → O(n²).

3.2 Patrones que hay que reconocer a golpe de vista

3.3 Ejemplos resueltos paso a paso (código real, ejecutado y contado)

Bucle simple → O(n)

public static int c1(int[] a) {
    int suma = 0;
    for (int i = 0; i < a.length; i++) {
        suma += a[i];
    }
    return suma;
}

n = a.length. Un único bucle de n vueltas con trabajo O(1) dentro → n·O(1) = O(n).

Bucle anidado DEPENDIENTE → O(n²)

public static int c4(int n) {
    int c = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            c++;
        }
    }
    return c;
}

n = parámetro. El bucle externo da n vueltas; el interno da i vueltas (depende del externo). Trabajo total = 1+2+3+...+n = n(n+1)/2 = n²/2 + n/2 → domina n² → O(n²). La ejecución lo confirma: c4(8) = 36 = 8·9/2.

Contador que se multiplica → O(log n)

public static int c5(int n) {
    int c = 0;
    for (int j = 1; j <= n; j *= 2) {
        c++;
    }
    return c;
}

j toma los valores 1, 2, 4, 8, ..., n: se multiplica por 2 en cada vuelta, así que da ⌊log₂ n⌋+1 vueltas → O(log n). Verificado: c5(1000) = 10.

Log externo × lineal interno (independientes) → O(n log n)

public static int c6(int n) {
    int c = 0;
    for (int i = 1; i <= n; i *= 2) {
        for (int k = 0; k < n; k++) {
            c++;
        }
    }
    return c;
}

El externo da log₂ n vueltas; el interno SIEMPRE da n (no depende de i) → se multiplican: O(n log n). Verificado: c6(1000) = 10·1000 = 10000.

La TRAMPA: interno dependiente geométrico → O(n)

public static int c7(int n) {
    int c = 0;
    for (int i = 1; i <= n; i *= 2) {
        for (int k = 0; k < i; k++) {
            c++;
        }
    }
    return c;
}

Parece el anterior, pero el interno da i vueltas con i = 1,2,4,...,n → hay que SUMAR: 1+2+4+...+n ≈ 2n → O(n), ¡no O(n log n)! Verificado: c7(1024) = 2047 ≈ 2·1024.

Recursión que divide por 2 → O(log n)

public static int c8(int n) {
    if (n <= 1) return 0;
    return 1 + c8(n / 2);
}

Cada llamada reduce n a la mitad y hace trabajo O(1): n → n/2 → n/4 → ... → 1, es decir, log₂ n llamadas → O(log n). Verificado: c8(1024) = 10 divisiones.

Doble recursión → O(2ⁿ)

public static long c9(int n) {
    if (n <= 1) return n;
    return c9(n - 1) + c9(n - 2);
}

Cada llamada genera DOS llamadas: el árbol de llamadas se duplica en cada nivel y tiene profundidad n → del orden de 2ⁿ llamadas → O(2ⁿ) (exponencial: Fibonacci ingenuo). Es el motivo de que c9(50) tardaría años mientras c9(10) es instantáneo.

Programa de verificación de TODOS los conteos anteriores:

c1(a) = 32  (recorre las 6 posiciones una vez)
c2 PEOR caso, x=100 no está:  36 iteraciones (6x6 = n^2)
c2 MEJOR caso, x=3 el primero: 0 iteraciones (el bucle interno corta siempre)
c3(10)   = 1000  (10^3 = n^3)
c4(8)    = 36  (1+2+...+8 = 8*9/2 = 36 ~ n^2/2)
c5(1000) = 10  (1,2,4,...,512 -> ~log2 de n vueltas)
c6(1000) = 10000  (~log2(n) * n = 10 * 1000)
c7(1024) = 2047  (1+2+4+...+1024 = 2047 ~ 2n, ¡O(n), no n log n!)
c8(1024) = 10  (1024->512->...->1: log2(1024) = 10 llamadas)
c9(10)   = 55  (Fibonacci: el ARBOL de llamadas crece ~2^n)

3.4 Tabla de órdenes de complejidad, de mejor a peor

4 · Los métodos de ordenación, uno a uno

Para cada método: la idea con una analogía, el código Java completo y comentado (compilado y ejecutado), la traza real sobre un array pequeño, sus complejidades y cuándo conviene. Estable significa que dos elementos iguales conservan su orden relativo original (importa al ordenar objetos por un campo: dos alumnos con la misma nota no se "cruzan").

4.1 Burbuja (Bubble Sort) y burbuja mejorada

/** BURBUJA CLÁSICA: en cada pasada compara VECINOS y los intercambia si
 *  están desordenados; el mayor "burbujea" hasta el final del array. */
public static void burbuja(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {           // n-1 pasadas como máximo
        for (int j = 0; j < n - 1 - i; j++) {   // los i últimos YA están colocados
            if (a[j] > a[j + 1]) {              // vecinos desordenados...
                int tmp = a[j];                 // ...intercambio clásico con
                a[j] = a[j + 1];                //    variable temporal
                a[j + 1] = tmp;
            }
        }
        System.out.println("Tras la pasada " + (i + 1) + ": " + Arrays.toString(a));
    }
}

Las dos optimizaciones clásicas (justo lo que pide el examen real): (1) la bandera huboCambios — si una pasada entera no intercambia nada, el array ya está ordenado y se corta (así el mejor caso pasa a ser O(n)); (2) el límite decreciente n-1-i — la cola ya ordenada no se vuelve a comparar.

/** BURBUJA MEJORADA. Dos optimizaciones:
 *  1) bandera huboCambios: si una pasada no intercambia nada, el array ya
 *     está ordenado y se PARA (mejor caso O(n));
 *  2) límite decreciente (n-1-i): la zona final ya ordenada no se revisita. */
public static void burbujaMejorada(int[] a) {
    int n = a.length;
    boolean huboCambios = true;
    for (int i = 0; i < n - 1 && huboCambios; i++) {
        huboCambios = false;                    // supongo que ya está ordenado
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                huboCambios = true;             // esta pasada SÍ tocó algo
            }
        }
        System.out.println("Tras la pasada " + (i + 1) + ": " + Arrays.toString(a)
                + (huboCambios ? "" : "   <- pasada sin cambios: ya ordenado, ¡PARO!"));
    }
}

Traza real con la secuencia del examen [1, 4, 8, 10, 2]:

BURBUJA CLÁSICA sobre [1, 4, 8, 10, 2]
Tras la pasada 1: [1, 4, 8, 2, 10]
Tras la pasada 2: [1, 4, 2, 8, 10]
Tras la pasada 3: [1, 2, 4, 8, 10]
Tras la pasada 4: [1, 2, 4, 8, 10]

BURBUJA MEJORADA sobre [1, 4, 8, 10, 2]
Tras la pasada 1: [1, 4, 8, 2, 10]
Tras la pasada 2: [1, 4, 2, 8, 10]
Tras la pasada 3: [1, 2, 4, 8, 10]
Tras la pasada 4: [1, 2, 4, 8, 10]   <- pasada sin cambios: ya ordenado, ¡PARO!

Lectura de la traza: pasada 1: 1-4 bien, 4-8 bien, 8-10 bien, 10-2 se intercambian → el 10 llega al final. Pasada 2: el 8 empuja al 2 → queda [1,4,2,8,10]. Pasada 3: el 4 empuja al 2 → ordenado. Pasada 4: sin cambios → la versión mejorada PARA aquí.

Cuándo conviene: casi nunca en la práctica; es el método didáctico por excelencia. *El mejor caso O(n) solo con la bandera y datos ya ordenados.

4.2 Selección (Selection Sort)

/** SELECCIÓN: busca el MÍNIMO de la zona sin ordenar y lo intercambia con
 *  la primera posición libre. Una colocación definitiva por pasada. */
public static void seleccion(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {       // posición que voy a rellenar
        int posMin = i;                     // candidato a mínimo
        for (int j = i + 1; j < n; j++) {   // busco el mínimo real del resto
            if (a[j] < a[posMin]) {
                posMin = j;
            }
        }
        int tmp = a[i];                     // intercambio el mínimo con a[i]
        a[i] = a[posMin];
        a[posMin] = tmp;
        System.out.println("Paso " + (i + 1) + ": coloco el mínimo " + a[i]
                + " en la posición " + i + " -> " + Arrays.toString(a));
    }
}

SELECCIÓN sobre [29, 10, 14, 37, 13]
Paso 1: coloco el mínimo 10 en la posición 0 -> [10, 29, 14, 37, 13]
Paso 2: coloco el mínimo 13 en la posición 1 -> [10, 13, 14, 37, 29]
Paso 3: coloco el mínimo 14 en la posición 2 -> [10, 13, 14, 37, 29]
Paso 4: coloco el mínimo 29 en la posición 3 -> [10, 13, 14, 29, 37]

Cuándo conviene: cuando lo caro es MOVER datos: hace como mucho n-1 intercambios (el mínimo posible). Siempre es O(n²) aunque el array ya esté ordenado, porque siempre busca el mínimo entero.

4.3 Inserción (Insertion Sort)

/** INSERCIÓN: mantiene ordenada la zona izquierda; toma el siguiente
 *  elemento y lo desplaza hacia atrás hasta su sitio (como ordenar cartas). */
public static void insercion(int[] a) {
    for (int i = 1; i < a.length; i++) {    // a[0] ya es una "zona ordenada" de 1
        int valor = a[i];                   // elemento a colocar
        int j = i - 1;
        while (j >= 0 && a[j] > valor) {    // mientras el de la izquierda sea mayor...
            a[j + 1] = a[j];                // ...lo desplazo un hueco a la derecha
            j--;
        }
        a[j + 1] = valor;                   // hueco encontrado: inserto el valor
        System.out.println("Inserto " + valor + " -> " + Arrays.toString(a));
    }
}

INSERCIÓN sobre [25, 9, 14, 3, 20]
Inserto 9 -> [9, 25, 14, 3, 20]
Inserto 14 -> [9, 14, 25, 3, 20]
Inserto 3 -> [3, 9, 14, 25, 20]
Inserto 20 -> [3, 9, 14, 20, 25]

Cuándo conviene: arrays pequeños o CASI ordenados (su mejor caso O(n) es real: si cada elemento está cerca de su sitio apenas desplaza). Por eso se usa como remate de otros algoritmos.

4.4 Mezcla (Mergesort)

/** MERGESORT (divide y vencerás):
 *  1) DIVIDE el trozo por la mitad hasta llegar a trozos de 1 elemento;
 *  2) MEZCLA (merge) los trozos de dos en dos, que ya vienen ordenados. */
public static void mergeSort(int[] a, int ini, int fin) {
    if (ini >= fin) return;             // CASO BASE: 0 o 1 elementos -> ya ordenado
    int mid = (ini + fin) / 2;          // punto de corte
    mergeSort(a, ini, mid);             // 1) ordeno la mitad izquierda
    mergeSort(a, mid + 1, fin);         // 2) ordeno la mitad derecha
    merge(a, ini, mid, fin);            // 3) mezclo ambas mitades ya ordenadas
    System.out.println("MEZCLO a[" + ini + ".." + fin + "] -> " + trozo(a, ini, fin));
}

/** Mezcla dos zonas YA ordenadas: a[ini..mid] y a[mid+1..fin]. */
public static void merge(int[] a, int ini, int mid, int fin) {
    int[] aux = new int[fin - ini + 1];     // array auxiliar: la memoria O(n) extra
    int i = ini, j = mid + 1, k = 0;

    while (i <= mid && j <= fin) {          // comparo las CABEZAS, copio la menor
        if (a[i] <= a[j]) {                 // el <= hace a Mergesort ESTABLE
            aux[k++] = a[i++];
        } else {
            aux[k++] = a[j++];
        }
    }
    while (i <= mid) aux[k++] = a[i++];     // restos de la izquierda (si quedan)
    while (j <= fin) aux[k++] = a[j++];     // restos de la derecha (si quedan)

    for (k = 0; k < aux.length; k++) {      // vuelco el auxiliar al array original
        a[ini + k] = aux[k];
    }
}

Traza real con [31, 7, 24, 9, 15, 2] (se muestra cada mezcla; las divisiones son: [31 7 24 | 9 15 2] → [31 7|24] y [9 15|2] → trozos de 1):

MERGESORT sobre [31, 7, 24, 9, 15, 2]
MEZCLO a[0..1] -> [7 31]
MEZCLO a[0..2] -> [7 24 31]
MEZCLO a[3..4] -> [9 15]
MEZCLO a[3..5] -> [2 9 15]
MEZCLO a[0..5] -> [2 7 9 15 24 31]
Resultado final: [2, 7, 9, 15, 24, 31]

Cuándo conviene: cuando necesitas garantía de O(n log n) SIEMPRE o estabilidad. Es el estándar para ordenar listas enlazadas y datos externos. Su "precio" es la memoria O(n) extra. ¿Por qué n log n? El array se parte log₂ n niveles, y en cada nivel las mezclas tocan las n posiciones → n × log n.

4.5 Rápido (Quicksort)

/** QUICKSORT (divide y vencerás, al revés que Mergesort: el trabajo se hace
 *  ANTES de las llamadas recursivas, en la partición):
 *  1) elige un PIVOTE (aquí, el primer elemento del trozo);
 *  2) PARTICIONA: menores a su izquierda, mayores a su derecha
 *     -> el pivote queda COLOCADO en su posición definitiva;
 *  3) repite recursivamente en el trozo izquierdo y en el derecho. */
public static void quickSort(int[] a, int ini, int fin) {
    if (ini >= fin) return;                 // CASO BASE: 0 o 1 elementos
    int p = particionar(a, ini, fin);       // coloca el pivote y devuelve su posición
    quickSort(a, ini, p - 1);               // ordeno los menores
    quickSort(a, p + 1, fin);               // ordeno los mayores
}

/** Partición con pivote = a[ini]. 'i' marca la frontera de los menores:
 *  tras el bucle, todo lo de ini+1..i es menor que el pivote. */
public static int particionar(int[] a, int ini, int fin) {
    int pivote = a[ini];
    int i = ini;                            // frontera de la zona de menores
    for (int j = ini + 1; j <= fin; j++) {
        if (a[j] < pivote) {                // a[j] es menor -> lo paso a la
            i++;                            //    zona de menores
            intercambiar(a, i, j);
        }
    }
    intercambiar(a, ini, i);                // el pivote, a su sitio definitivo
    System.out.println("Partición de a[" + ini + ".." + fin + "], pivote " + pivote
            + " queda en la posición " + i + " -> " + Arrays.toString(a));
    return i;
}

static void intercambiar(int[] a, int x, int y) {
    int t = a[x]; a[x] = a[y]; a[y] = t;
}

Traza real con [35, 12, 48, 7, 29, 50, 18]:

QUICKSORT sobre [35, 12, 48, 7, 29, 50, 18]
Partición de a[0..6], pivote 35 queda en la posición 4 -> [18, 12, 7, 29, 35, 50, 48]
Partición de a[0..3], pivote 18 queda en la posición 2 -> [7, 12, 18, 29, 35, 50, 48]
Partición de a[0..1], pivote 7 queda en la posición 0 -> [7, 12, 18, 29, 35, 50, 48]
Partición de a[5..6], pivote 50 queda en la posición 6 -> [7, 12, 18, 29, 35, 48, 50]
Resultado final: [7, 12, 18, 29, 35, 48, 50]

Cuándo conviene: el más rápido en la práctica sobre arrays (buen uso de caché, sin memoria extra). Peor caso O(n²): cuando el pivote cae siempre en un extremo, p. ej. array YA ordenado con pivote = primero → particiones de tamaño 0 y n-1 (pregunta clásica). Se mitiga eligiendo pivote aleatorio o "mediana de tres".

4.6 Montículo (Heapsort)

/** HEAPSORT: usa un MAX-HEAP (montículo binario donde cada padre es MAYOR
 *  o igual que sus hijos, guardado en el propio array: hijos de i en 2i+1 y 2i+2).
 *  FASE 1: construir el montículo -> el máximo queda en a[0].
 *  FASE 2: intercambiar a[0] con el último, encoger el montículo y reparar. */
public static void heapSort(int[] a) {
    int n = a.length;
    // FASE 1: construir el max-heap hundiendo desde el último padre hacia la raíz
    for (int i = n / 2 - 1; i >= 0; i--) {
        hundir(a, n, i);
    }
    System.out.println("Montículo construido: " + Arrays.toString(a));

    // FASE 2: extraer el máximo n-1 veces
    for (int fin = n - 1; fin > 0; fin--) {
        int tmp = a[0]; a[0] = a[fin]; a[fin] = tmp;  // máximo -> al final
        hundir(a, fin, 0);                            // reparo el montículo restante
        System.out.println("Extraigo " + a[fin] + " -> " + Arrays.toString(a)
                + "  (ordenado desde la posición " + fin + ")");
    }
}

/** "Hunde" el nodo i: mientras algún hijo sea mayor que él, se intercambia
 *  con el mayor de sus hijos (n = tamaño actual del montículo). */
private static void hundir(int[] a, int n, int i) {
    int mayor = i;
    int izq = 2 * i + 1;                    // hijo izquierdo
    int der = 2 * i + 2;                    // hijo derecho
    if (izq < n && a[izq] > a[mayor]) mayor = izq;
    if (der < n && a[der] > a[mayor]) mayor = der;
    if (mayor != i) {                       // algún hijo le gana ->
        int tmp = a[i]; a[i] = a[mayor]; a[mayor] = tmp;
        hundir(a, n, mayor);                // sigo hundiendo más abajo
    }
}

Traza real con [19, 4, 27, 11, 8]:

HEAPSORT sobre [19, 4, 27, 11, 8]
Montículo construido: [27, 11, 19, 4, 8]
Extraigo 27 -> [19, 11, 8, 4, 27]  (ordenado desde la posición 4)
Extraigo 19 -> [11, 4, 8, 19, 27]  (ordenado desde la posición 3)
Extraigo 11 -> [8, 4, 11, 19, 27]  (ordenado desde la posición 2)
Extraigo 8 -> [4, 8, 11, 19, 27]  (ordenado desde la posición 1)
Resultado final: [4, 8, 11, 19, 27]

Cuándo conviene: cuando quieres O(n log n) garantizado SIN memoria extra (a diferencia de Mergesort). Construir el montículo es O(n); luego n extracciones × reparación O(log n) → O(n log n).

4.7 Shellsort (inserción con saltos)

/** SHELLSORT: es una INSERCIÓN mejorada. Compara elementos separados por un
 *  SALTO (gap) que empieza grande (n/2) y se va reduciendo a la mitad hasta 1.
 *  Con gap grande, los elementos lejanos de su sitio viajan rápido; el último
 *  pase (gap=1) es una inserción normal sobre una lista ya casi ordenada. */
public static void shellSort(int[] a) {
    int n = a.length;
    for (int gap = n / 2; gap >= 1; gap /= 2) {   // gaps: n/2, n/4, ..., 1
        for (int i = gap; i < n; i++) {           // inserción "a saltos de gap"
            int valor = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > valor) {
                a[j] = a[j - gap];                // desplazo gap posiciones
                j -= gap;
            }
            a[j] = valor;
        }
        System.out.println("Tras el pase con gap " + gap + ": " + Arrays.toString(a));
    }
}

SHELLSORT sobre [45, 23, 67, 12, 38, 7]
Tras el pase con gap 3: [12, 23, 7, 45, 38, 67]
Tras el pase con gap 1: [7, 12, 23, 38, 45, 67]

Cuándo conviene: mejora clara sobre la inserción con muy poco código extra; útil en sistemas con poca memoria.

4.8 Tabla resumen de TODOS los métodos

*con la bandera de la burbuja mejorada.

5 · Estructuras de datos

5.1 Arrays

Bloque de casillas contiguas en memoria, de tamaño fijo, accesibles por índice desde 0: int[] a = new int[5]; o int[] a = {3, 8, 1};. Acceder a a[i] es O(1) (la dirección se calcula con una multiplicación). A cambio: insertar o borrar en medio obliga a desplazar todo lo que hay detrás → O(n), y no puede crecer (hay que crear otro array y copiar).

5.2 Listas enlazadas (simples)

class ListaEnlazada {
    // El NODO: una caja con el dato y la flecha al siguiente
    private static class Nodo {
        int dato;
        Nodo siguiente;                   // null = no hay siguiente
        Nodo(int dato) { this.dato = dato; }
    }

    private Nodo primero;                 // única puerta de entrada a la lista

    /** Insertar al principio: O(1), no hay que recorrer nada. */
    public void insertarPrincipio(int valor) {
        Nodo nuevo = new Nodo(valor);
        nuevo.siguiente = primero;        // 1) el nuevo apunta al antiguo primero
        primero = nuevo;                  // 2) la cabeza pasa a ser el nuevo
    }

    /** Insertar al final: O(n), hay que llegar hasta el último nodo. */
    public void insertarFinal(int valor) {
        Nodo nuevo = new Nodo(valor);
        if (primero == null) {            // CASO ESPECIAL: lista vacía
            primero = nuevo;
            return;
        }
        Nodo actual = primero;
        while (actual.siguiente != null) {   // avanzo hasta el ÚLTIMO nodo
            actual = actual.siguiente;
        }
        actual.siguiente = nuevo;         // lo engancho al final
    }

    /** Contar nodos: el recorrido universal de las listas enlazadas. */
    public int contar() {
        int c = 0;
        for (Nodo a = primero; a != null; a = a.siguiente) {
            c++;
        }
        return c;
    }

    /** ¿Está el valor en la lista? */
    public boolean contiene(int valor) {
        for (Nodo a = primero; a != null; a = a.siguiente) {
            if (a.dato == valor) return true;
        }
        return false;
    }

    /** Elimina el primer nodo con ese valor (el caso "es el primero" es especial). */
    public boolean eliminar(int valor) {
        if (primero == null) return false;
        if (primero.dato == valor) {          // caso especial: borrar la cabeza
            primero = primero.siguiente;
            return true;
        }
        Nodo actual = primero;
        while (actual.siguiente != null && actual.siguiente.dato != valor) {
            actual = actual.siguiente;        // me paro en el nodo ANTERIOR al buscado
        }
        if (actual.siguiente == null) return false;   // no estaba
        actual.siguiente = actual.siguiente.siguiente; // "puenteo" el nodo eliminado
        return true;
    }

    public void imprimir() {
        StringBuilder sb = new StringBuilder("primero -> ");
        for (Nodo a = primero; a != null; a = a.siguiente) {
            sb.append(a.dato).append(" -> ");
        }
        System.out.println(sb.append("null"));
    }
}

public static void main(String[] args) {
    ListaEnlazada lista = new ListaEnlazada();
    lista.insertarFinal(10);
    lista.insertarFinal(20);
    lista.insertarPrincipio(5);
    lista.insertarFinal(30);
    lista.imprimir();
    System.out.println("contar() = " + lista.contar());
    System.out.println("contiene(20) = " + lista.contiene(20));
    System.out.println("eliminar(20) = " + lista.eliminar(20));
    System.out.println("eliminar(99) = " + lista.eliminar(99));
    lista.imprimir();
}

primero -> 5 -> 10 -> 20 -> 30 -> null
contar() = 4
contiene(20) = true
eliminar(20) = true
eliminar(99) = false
primero -> 5 -> 10 -> 30 -> null

5.3 Listas doblemente enlazadas

Cada nodo tiene DOS referencias: siguiente y anterior, y la lista suele guardar primero y ultimo. Se puede recorrer en ambos sentidos e insertar/borrar por los dos extremos en O(1). El precio: cada operación debe mantener el DOBLE de referencias coherentes. Para insertar un nodo entre A y B hay que ajustar 4 flechas: nuevo.anterior=A, nuevo.siguiente=B, A.siguiente=nuevo, B.anterior=nuevo.

class ListaDoble {
    static class Nodo {
        int dato;
        Nodo anterior;    // flecha hacia atrás
        Nodo siguiente;   // flecha hacia delante
        Nodo(int dato) { this.dato = dato; }
    }

    private Nodo primero, ultimo;

    /** Inserta al principio: O(1). */
    public void insertarPrincipio(int valor) {
        Nodo nuevo = new Nodo(valor);
        if (primero == null) {            // CASO ESPECIAL: lista vacía
            primero = ultimo = nuevo;
            return;
        }
        nuevo.siguiente = primero;        // 1) el nuevo mira adelante al antiguo primero
        primero.anterior = nuevo;         // 2) el antiguo primero mira atrás al nuevo
        primero = nuevo;                  // 3) actualizo la cabeza
    }

    /** Inserta al final: O(1) gracias a la referencia 'ultimo'. */
    public void insertarFinal(int valor) {
        Nodo nuevo = new Nodo(valor);
        if (ultimo == null) {
            primero = ultimo = nuevo;
            return;
        }
        nuevo.anterior = ultimo;          // 1) el nuevo mira atrás al antiguo último
        ultimo.siguiente = nuevo;         // 2) el antiguo último mira adelante al nuevo
        ultimo = nuevo;                   // 3) actualizo la cola
    }

    /** Inserta 'valor' justo DESPUÉS del primer nodo que contenga 'ref'.
     *  Hay que reajustar 4 referencias: las 2 del nuevo y una de cada vecino. */
    public boolean insertarDespuesDe(int ref, int valor) {
        Nodo actual = primero;
        while (actual != null && actual.dato != ref) {
            actual = actual.siguiente;    // busco el nodo de referencia: O(n)
        }
        if (actual == null) return false; // 'ref' no está en la lista

        Nodo nuevo = new Nodo(valor);
        nuevo.anterior = actual;               // 1) nuevo mira atrás a 'actual'
        nuevo.siguiente = actual.siguiente;    // 2) nuevo mira adelante al que seguía
        if (actual.siguiente != null) {
            actual.siguiente.anterior = nuevo; // 3) el vecino derecho mira atrás al nuevo
        } else {
            ultimo = nuevo;                    //    (no había vecino: nuevo es el último)
        }
        actual.siguiente = nuevo;              // 4) 'actual' mira adelante al nuevo
        return true;
    }

    /** Elimina el primer nodo con ese valor "puenteándolo" entre sus vecinos. */
    public boolean eliminar(int valor) {
        Nodo actual = primero;
        while (actual != null && actual.dato != valor) {
            actual = actual.siguiente;
        }
        if (actual == null) return false;      // no estaba

        if (actual.anterior != null) {
            actual.anterior.siguiente = actual.siguiente;
        } else {
            primero = actual.siguiente;        // era el primero
        }
        if (actual.siguiente != null) {
            actual.siguiente.anterior = actual.anterior;
        } else {
            ultimo = actual.anterior;          // era el último
        }
        return true;
    }

    public void imprimirAdelante() {
        StringBuilder sb = new StringBuilder("primero -> ");
        for (Nodo a = primero; a != null; a = a.siguiente) {
            sb.append(a.dato).append(" <-> ");
        }
        System.out.println(sb.append("null"));
    }

    public void imprimirAtras() {
        StringBuilder sb = new StringBuilder("ultimo  -> ");
        for (Nodo a = ultimo; a != null; a = a.anterior) {
            sb.append(a.dato).append(" <-> ");
        }
        System.out.println(sb.append("null"));
    }
}

public static void main(String[] args) {
    ListaDoble lista = new ListaDoble();
    lista.insertarFinal(10);
    lista.insertarFinal(20);
    lista.insertarFinal(40);
    lista.insertarDespuesDe(20, 30);       // inserta 30 entre 20 y 40
    lista.insertarPrincipio(5);
    lista.imprimirAdelante();
    lista.imprimirAtras();                 // comprobar las flechas 'anterior'
    System.out.println("eliminar(40): " + lista.eliminar(40));
    System.out.println("eliminar(99): " + lista.eliminar(99));
    lista.imprimirAdelante();
    lista.imprimirAtras();
}

primero -> 5 <-> 10 <-> 20 <-> 30 <-> 40 <-> null
ultimo  -> 40 <-> 30 <-> 20 <-> 10 <-> 5 <-> null
eliminar(40): true
eliminar(99): false
primero -> 5 <-> 10 <-> 20 <-> 30 <-> null
ultimo  -> 30 <-> 20 <-> 10 <-> 5 <-> null

5.4 Pilas (LIFO)

class PilaArray {
    private int[] datos;      // almacén de los elementos
    private int tope;         // índice de la CIMA (-1 = pila vacía)

    public PilaArray(int capacidad) {
        datos = new int[capacidad];
        tope = -1;
    }
    public boolean estaVacia() { return tope == -1; }
    public boolean estaLlena() { return tope == datos.length - 1; }

    public void push(int e) {                    // apilar: O(1)
        if (estaLlena()) throw new RuntimeException("Pila llena");
        datos[++tope] = e;                       // avanzo el tope y guardo encima
    }
    public int pop() {                           // desapilar: O(1)
        if (estaVacia()) throw new RuntimeException("Pila vacía");
        return datos[tope--];                    // devuelvo la cima y retrocedo
    }
    public int peek() {                          // consultar la cima sin sacarla: O(1)
        if (estaVacia()) throw new RuntimeException("Pila vacía");
        return datos[tope];
    }
}

Aplicación estrella (con la pila del propio Java, ArrayDeque): comprobar paréntesis equilibrados.

/** Comprueba con una PILA si (), [] y {} están correctamente equilibrados. */
public static boolean equilibrada(String expr) {
    Deque<Character> pila = new ArrayDeque<>();
    for (int i = 0; i < expr.length(); i++) {
        char c = expr.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            pila.push(c);                       // apertura: la apilo
        } else if (c == ')' || c == ']' || c == '}') {
            if (pila.isEmpty()) return false;   // cierre sin pareja pendiente
            char abre = pila.pop();             // debe casar con la ÚLTIMA apertura
            if ((c == ')' && abre != '(') ||
                (c == ']' && abre != '[') ||
                (c == '}' && abre != '{')) {
                return false;                   // cierra un símbolo que no toca
            }
        }
    }
    return pila.isEmpty();      // si sobra alguna apertura, NO está equilibrada
}

peek: 8
pop:  8
pop:  3
pop:  5
¿vacía? true

{[()]}  -> true
([)]    -> false
(((     -> false

5.5 Colas (FIFO)

class ColaEnlazada {
    private static class Nodo {
        String dato;
        Nodo siguiente;
        Nodo(String dato) { this.dato = dato; }
    }

    private Nodo primero;   // FRENTE: por aquí se SACA
    private Nodo ultimo;    // FINAL:  por aquí se METE
    private int n;          // contador de elementos

    public boolean estaVacia() { return primero == null; }
    public int tamano()        { return n; }

    public void encolar(String e) {              // O(1) gracias a 'ultimo'
        Nodo nuevo = new Nodo(e);
        if (estaVacia()) {
            primero = nuevo;                     // cola vacía: el nuevo es a la vez
        } else {                                 //   el primero...
            ultimo.siguiente = nuevo;            // si no, el antiguo último lo engancha
        }
        ultimo = nuevo;                          // ...y el último
        n++;
    }

    public String desencolar() {                 // O(1)
        if (estaVacia()) throw new RuntimeException("Cola vacía");
        String dato = primero.dato;
        primero = primero.siguiente;             // el segundo pasa a ser el frente
        if (primero == null) ultimo = null;      // quedó vacía: cuidar también 'ultimo'
        n--;
        return dato;
    }

    public String frente() {                     // consultar sin sacar: O(1)
        if (estaVacia()) throw new RuntimeException("Cola vacía");
        return primero.dato;
    }
}

public static void main(String[] args) {
    ColaEnlazada c = new ColaEnlazada();
    c.encolar("Ana");
    c.encolar("Luis");
    System.out.println("desencolar: " + c.desencolar());   // sale Ana (la primera)
    c.encolar("Marta");
    c.encolar("Pedro");
    System.out.println("frente:     " + c.frente());       // Luis, sin sacarlo
    System.out.println("desencolar: " + c.desencolar());
    System.out.println("desencolar: " + c.desencolar());
    System.out.println("quedan " + c.tamano() + " -> frente: " + c.frente());
}

desencolar: Ana
frente:     Luis
desencolar: Luis
desencolar: Marta
quedan 1 -> frente: Pedro

5.6 Árboles binarios y árboles binarios de búsqueda (ABB)

Insertando 45, 23, 67, 12, 38, 51, 89, 30 se obtiene este ABB:

            45
          /    \
       23        67
      /  \      /  \
    12    38  51    89
         /
       30

class ABB {
    private static class Nodo {
        int dato;
        Nodo izquierdo, derecho;
        Nodo(int dato) { this.dato = dato; }
    }

    private Nodo raiz;

    /** Método público "lanzadera" + método privado recursivo (patrón habitual). */
    public void insertar(int valor) {
        raiz = insertar(raiz, valor);
    }
    private Nodo insertar(Nodo actual, int valor) {
        if (actual == null) {                   // CASO BASE: hueco encontrado
            return new Nodo(valor);
        }
        if (valor < actual.dato) {              // menores -> subárbol izquierdo
            actual.izquierdo = insertar(actual.izquierdo, valor);
        } else if (valor > actual.dato) {       // mayores -> subárbol derecho
            actual.derecho = insertar(actual.derecho, valor);
        }                                       // iguales: no se insertan (sin duplicados)
        return actual;
    }

    /** Búsqueda: aprovecha el orden del ABB, NO recorre todo el árbol. */
    public boolean buscar(int valor) {
        Nodo actual = raiz;
        while (actual != null) {
            System.out.print("visito " + actual.dato + "  ");
            if (valor == actual.dato) {
                System.out.println("-> ¡encontrado!");
                return true;
            }
            actual = (valor < actual.dato) ? actual.izquierdo : actual.derecho;
        }
        System.out.println("-> no está");
        return false;
    }

    // Los TRES recorridos: solo cambia DÓNDE se procesa la raíz
    public void preorden()  { preorden(raiz);  System.out.println(); }
    private void preorden(Nodo n) {
        if (n == null) return;                  // caso base ¡SIEMPRE!
        System.out.print(n.dato + " ");         // Raíz, Izquierda, Derecha
        preorden(n.izquierdo);
        preorden(n.derecho);
    }

    public void inorden()   { inorden(raiz);   System.out.println(); }
    private void inorden(Nodo n) {
        if (n == null) return;
        inorden(n.izquierdo);                   // Izquierda, Raíz, Derecha
        System.out.print(n.dato + " ");
        inorden(n.derecho);
    }

    public void postorden() { postorden(raiz); System.out.println(); }
    private void postorden(Nodo n) {
        if (n == null) return;
        postorden(n.izquierdo);                 // Izquierda, Derecha, Raíz
        postorden(n.derecho);
        System.out.print(n.dato + " ");
    }
}

public static void main(String[] args) {
    ABB arbol = new ABB();
    int[] valores = {45, 23, 67, 12, 38, 51, 89, 30};
    for (int v : valores) {
        arbol.insertar(v);
    }
    System.out.print("Preorden:  "); arbol.preorden();
    System.out.print("Inorden:   "); arbol.inorden();     // ¡sale ORDENADO!
    System.out.print("Postorden: "); arbol.postorden();
    System.out.println();
    System.out.println("Buscar 30:");
    arbol.buscar(30);
    System.out.println("Buscar 99:");
    arbol.buscar(99);
}

Preorden:  45 23 12 38 30 67 51 89 
Inorden:   12 23 30 38 45 51 67 89 
Postorden: 12 30 38 23 51 89 67 45 

Buscar 30:
visito 45  visito 23  visito 38  visito 30  -> ¡encontrado!
Buscar 99:
visito 45  visito 67  visito 89  -> no está

5.7 Tablas hash

Map guarda pares clave → valor (cada clave una sola vez). El patrón "contar frecuencias" es el más pedido:

/** Cuenta cuántas veces aparece cada nombre usando un Map. */
public static Map<String, Integer> frecuencias(String[] nombres) {
    Map<String, Integer> frec = new HashMap<>();
    for (String s : nombres) {
        // si no estaba, parte de 0; si estaba, coge su valor actual y suma 1
        frec.put(s, frec.getOrDefault(s, 0) + 1);
    }
    return frec;
}

Y la estructura de la pregunta 1 del examen real: TreeSet (sin duplicados + SIEMPRE ordenado, operaciones O(log n) porque por dentro es un árbol equilibrado):

public static void demoTreeSet() {
    TreeSet<Integer> ids = new TreeSet<>();     // sin duplicados + SIEMPRE ordenado
    ids.add(50);
    ids.add(20);
    ids.add(70);
    System.out.println("¿Se añade 20 otra vez? " + ids.add(20));  // false: duplicado
    System.out.println("Contenido (orden automático): " + ids);
    System.out.println("¿Contiene 70? " + ids.contains(70) + "  (búsqueda O(log n))");
    System.out.println("Menor: " + ids.first() + " | Mayor: " + ids.last());
}

¿Se añade 20 otra vez? false
Contenido (orden automático): [20, 50, 70]
¿Contiene 70? true  (búsqueda O(log n))
Menor: 20 | Mayor: 70

Marta aparece 1 veces
Ana aparece 3 veces
Luis aparece 2 veces

5.8 Las implementaciones del framework de colecciones de Java

*amortizado: de vez en cuando toca redimensionar el array interno.

6 · Búsqueda lineal y binaria

/** BÚSQUEDA LINEAL: mira las casillas una a una. Vale para arrays SIN ordenar. */
public static int busquedaLineal(int[] a, int x) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == x) return i;    // encontrado: devuelvo su posición
    }
    return -1;                      // recorrido entero sin éxito
}

/** BÚSQUEDA BINARIA (exige array ORDENADO): mira el centro y descarta
 *  media tabla en cada paso -> O(log n). */
public static int busquedaBinaria(int[] a, int x) {
    int ini = 0, fin = a.length - 1;
    while (ini <= fin) {                    // mientras quede zona por mirar
        int mid = (ini + fin) / 2;          // posición central
        System.out.println("  miro a[" + mid + "] = " + a[mid]);
        if (a[mid] == x) return mid;        // ¡es él!
        if (a[mid] < x) ini = mid + 1;      // x está a la DERECHA: descarto mitad izq.
        else            fin = mid - 1;      // x está a la IZQUIERDA: descarto mitad der.
    }
    return -1;                              // la zona se agotó: no está
}

/** La misma idea, en versión RECURSIVA. */
public static int busquedaBinariaRec(int[] a, int x, int ini, int fin) {
    if (ini > fin) return -1;               // CASO BASE 1: zona vacía -> no está
    int mid = (ini + fin) / 2;
    if (a[mid] == x) return mid;            // CASO BASE 2: encontrado
    if (a[mid] < x) {
        return busquedaBinariaRec(a, x, mid + 1, fin);   // mitad derecha
    }
    return busquedaBinariaRec(a, x, ini, mid - 1);       // mitad izquierda
}

Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Lineal, buscar 23  -> posición 5
Binaria, buscar 23:
  miro a[4] = 16
  miro a[7] = 56
  miro a[5] = 23
  -> posición 5
Binaria, buscar 7:
  miro a[4] = 16
  miro a[1] = 5
  miro a[2] = 8
  -> posición -1
Binaria recursiva, buscar 91 -> posición 9

7 · Recursión

/** n! = n * (n-1) * ... * 2 * 1. Versión recursiva. */
public static long factorial(int n) {
    if (n <= 1) return 1;             // CASO BASE: detiene la recursión
    return n * factorial(n - 1);      // CASO RECURSIVO: problema más pequeño
}

La misma función imprimiendo su pila de llamadas (la sangría muestra la profundidad):

/** Igual que factorial, pero imprimiendo la pila de llamadas. */
public static long factorialTraza(int n, String sangria) {
    System.out.println(sangria + "entra factorial(" + n + ")");
    if (n <= 1) {
        System.out.println(sangria + "caso base -> devuelve 1");
        return 1;
    }
    long resultado = n * factorialTraza(n - 1, sangria + "   ");
    System.out.println(sangria + "devuelve " + n + " * factorial(" + (n - 1)
            + ") = " + resultado);
    return resultado;
}

/** Suma recursiva: el elemento i + la suma del resto del array. */
public static int sumaArray(int[] a, int i) {
    if (i == a.length) return 0;          // CASO BASE: no quedan elementos
    return a[i] + sumaArray(a, i + 1);    // primero + suma del resto
}

Traza de factorial(4):
entra factorial(4)
   entra factorial(3)
      entra factorial(2)
         entra factorial(1)
         caso base -> devuelve 1
      devuelve 2 * factorial(1) = 2
   devuelve 3 * factorial(2) = 6
devuelve 4 * factorial(3) = 24
factorial(4) = 24

sumaArray({3,1,4,1,5}) = 14

Fin del temario · Sigue con Examen_Maestro_EDA.html y corrígete con Examen_Maestro_EDA_SOLUCIONES.html