Ordenación Rápida

public class OrdenadorRapido {
    public static void main(String[] args) {
        int datos[] = {9,1,8,2,7,3,6,4,5};
        ordenacionRapida(datos,0,datos.length - 1);
        System.out.println("Array ordenado: " + Arrays.toString(datos));
    }
    private static void ordenacionRapida(int[] arreglo, int inicio, int fin) {
        if(inicio >= fin)
            return;
        // Dividir el array y obtener el índice del pivote
        int indicePivote = particion(arreglo, inicio, fin);
        // Ordenar recursivamente las mitades
        ordenacionRapida(arreglo, inicio, indicePivote - 1);
        ordenacionRapida(arreglo,indicePivote + 1, fin);
    }

    private static int particion(int[] arreglo, int inicio, int fin) {
        // Seleccionar el último elemento como pivote
        int pivote = arreglo[fin];
        // Índice del elemento más pequeño
        int indiceMenor = inicio - 1;
        
        for(int j = inicio; j < fin; j++){
            if(arreglo[j] < pivote){
                indiceMenor++;
                // Intercambiar elementos
                int temporal = arreglo[j];
                arreglo[j] = arreglo[indiceMenor];
                arreglo[indiceMenor] = temporal;
            }
        }
        // Colocar el pivote en su posición correcta
        int temporal = arreglo[indiceMenor + 1];
        arreglo[indiceMenor + 1] = arreglo[fin];
        arreglo[fin] = temporal;
        return indiceMenor + 1;
    }
}

Ordenación por Mezcla

public class MezclaOrdenacion {
    static int contador = 0;
    public static void main(String[] args) {
        int datos[] = {9,1,8,2,7,3,6,4,5};
        int resultado[] = ordenacionPorMezcla(datos, 0, datos.length - 1);
        System.out.println("Array ordenado: " + Arrays.toString(resultado));
    }
    private static int[] ordenacionPorMezcla(int datos[], int izquierda, int derecha){
        // Caso base: cuando el subarray tiene un solo elemento
        if(izquierda == derecha)
            return new int[]{datos[izquierda]};
        
        // Dividir el array en dos mitades
        int medio = (derecha - izquierda)/2 + izquierda;
        int izquierdaArray[] = ordenacionPorMezcla(datos, izquierda, medio);
        int derechaArray[] = ordenacionPorMezcla(datos, medio + 1, derecha);
        return combinarArrays(izquierdaArray, derechaArray);
    }
    private static int[] combinarArrays(int izq[], int der[]){
        int combinado[] = new int[izq.length + der.length];
        int indiceCombinado = 0;
        int indiceIzq = 0;
        int indiceDer = 0;
        
        // Combinar los dos arrays en orden
        while(indiceIzq < izq.length && indiceDer < der.length){
            combinado[indiceCombinado++] = izq[indiceIzq] < der[indiceDer] ? 
                                          izq[indiceIzq++]:der[indiceDer++];
        }
        
        // Agregar los elementos restantes
        while(indiceIzq < izq.length){
            combinado[indiceCombinado++] = izq[indiceIzq++];
        }
        while(indiceDer < der.length){
            combinado[indiceCombinado++] = der[indiceDer++];
        }
        return combinado;
    }
}

Algoritmo de Dijkstra

public class CaminoMasCorto {
    public static void main(String[] args) {
        int infinito = Integer.MAX_VALUE/2;
        int nodos[] = {1,2,3,4,5};
        int matrizAdyacencia[][] = new int[nodos.length + 1][nodos.length + 1];
        
        // Configurar la matriz de adyacencia
        matrizAdyacencia[1] = new int[]{infinito, 0, 1, infinito, 3, infinito};
        matrizAdyacencia[2] = new int[]{infinito, infinito, 0, 3, 1, infinito};
        matrizAdyacencia[3] = new int[]{infinito, infinito, infinito, 0, infinito, 1};
        matrizAdyacencia[4] = new int[]{infinito, infinito, infinito, 1, 0, infinito};
        matrizAdyacencia[5] = new int[]{infinito, infinito, infinito, infinito, infinito, 0};
        
        // Calcular distancias desde el nodo 1 a todos los demás
        int distancias[] = {infinito, 0, infinito, infinito, infinito, infinito};
        boolean visitados[] = new boolean[nodos.length + 1];
        
        // Procesar cada nodo
        for(int i = 0; i < nodos.length; i++){
            int nodoActual = encontrarMinimo(distancias, visitados);
            visitados[nodoActual] = true;
            
            // Actualizar distancias a los nodos vecinos
            for(int j = 1; j < distancias.length; j++){
                if(nodoActual != j && distancias[j] > matrizAdyacencia[nodoActual][j] + distancias[nodoActual]){
                    distancias[j] = matrizAdyacencia[nodoActual][j] + distancias[nodoActual];
                }
            }
        }
        System.out.println("Distancia mínima al nodo 5: " + distancias[5]);
    }
    
    private static int encontrarMinimo(int[] distancias, boolean[] visitados) {
        int indiceMinimo = 1;
        int minimo = Integer.MAX_VALUE;
        
        for(int i = 1; i < distancias.length; i++){
            if(!visitados[i] && minimo > distancias[i]){
                minimo = distancias[i];
                indiceMinimo = i;
            }
        }
        return indiceMinimo;
    }
}

Ordenación Personalizada

import java.util.Arrays;
import java.util.Comparator;

public class Alumno implements Comparable<Alumno>{
    int puntuacion;
    int edad;
    
    Alumno(int puntuacion, int edad){
        this.puntuacion = puntuacion;
        this.edad = edad;
    }
    
    public int getPuntuacion() { return puntuacion; }
    public void setPuntuacion(int puntuacion) { this.puntuacion = puntuacion; }
    public int getEdad() { return edad; }
    public void setEdad(int edad) { this.edad = edad; }
    
    @Override
    public int compareTo(Alumno otro) {
        if(this.puntuacion != otro.puntuacion)
            return Integer.compare(otro.puntuacion, this.puntuacion);
        return Integer.compare(this.edad, otro.edad);
    }
    
    public static void main(String[] args) {
            Alumno alumnos[] = new Alumno[3];
            alumnos[0] = new Alumno(1,2);
            alumnos[1] = new Alumno(1,0);
            alumnos[2] = new Alumno(2,0);
            
            // Método 1: Implementar Comparable
            Arrays.sort(alumnos);
            System.out.println("Ordenado con Comparable: " + Arrays.toString(alumnos));
            
            // Método 2: Comparator anónimo
            Arrays.sort(alumnos, new Comparator<Alumno>() {
                @Override
                public int compare(Alumno a1, Alumno a2) {
                    if(a1.getPuntuacion() != a2.getPuntuacion())
                        return a2.getPuntuacion() - a1.getPuntuacion();
                    return a1.getEdad() - a2.getEdad();
                }
            });
            
            // Método 3: Expresión lambda
            Arrays.sort(alumnos, (a1, a2) -> {
                if(a1.getPuntuacion() != a2.getPuntuacion())
                    return a2.getPuntuacion() - a1.getPuntuacion();
                return a1.getEdad() - a2.getEdad();
            });
            
            // Método 4: Comparator con métodos referenciados
            Arrays.sort(alumnos, Comparator.comparing(Alumno::getPuntuacion)
                .reversed()
                .thenComparing(Alumno::getEdad));
    }
}

Impresión Alternada de Números Pares e Impares

public class ImpresorAlternado {
    private static final Object cerrojo = new Object();
    private static int contador = 0;
    private static final int MAXIMO = 200;
    
    public static void main(String[] args) {
        Thread hilo1 = new Thread(new Impresor(), "Hilo-1");
        Thread hilo2 = new Thread(new Impresor(), "Hilo-2");
        hilo1.start();
        hilo2.start();
    }
    
    static class Impresor implements Runnable {
        @Override
        public void run() {
            while (true) {
                synchronized (cerrojo) {
                    if (contador > MAXIMO) {
                        break;
                    }
                    System.out.println(Thread.currentThread().getName() + " imprime: " + contador++);
                    cerrojo.notify();
                    try {
                        if (contador <= MAXIMO) {
                            cerrojo.wait();
                        }
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
            }
        }
    }
}

Ordenaicón por Burbuja

public class OrdenacionBurbuja {
    public static void main(String[] args) {
        int array[] = {8,7,6,5,4,3,2,1};
        ordenacionBurbujaAscendente(array);
        System.out.println("Array ordenado ascendente: " + Arrays.toString(array));
        
        int arrayDesc[] = {1,2,3,4,5,6,7,8};
        ordenacionBurbujaDescendente(arrayDesc);
        System.out.println("Array ordenado descendente: " + Arrays.toString(arrayDesc));
    }
    
    private static void ordenacionBurbujaAscendente(int[] arreglo) {
        for(int i = 0; i < arreglo.length; i++){
            boolean intercambio = false;
            for(int j = 0; j < arreglo.length - i - 1; j++){
                if(arreglo[j] > arreglo[j + 1]){
                    intercambiar(arreglo, j, j + 1);
                    intercambio = true;
                }
            }
            if(!intercambio)
                break;
        }
    }
    
    private static void ordenacionBurbujaDescendente(int[] arreglo) {
        for(int i = 0; i < arreglo.length; i++){
            boolean intercambio = false;
            for(int j = 0; j < arreglo.length - i - 1; j++){
                if(arreglo[j] < arreglo[j + 1]){
                    intercambiar(arreglo, j, j + 1);
                    intercambio = true;
                }
            }
            if(!intercambio)
                break;
        }
    }
    
    private static void intercambiar(int arreglo[], int i, int j){
        int temporal = arreglo[i];
        arreglo[i] = arreglo[j];
        arreglo[j] = temporal;
    }
}

Ordenación por Inserción

public class OrdenacionInsercion {
    public static void main(String[] args) {
        int datos[] = {5,2,9,1,5,6};
        ordenacionInsercion(datos);
        System.out.println("Array ordenado: " + Arrays.toString(datos));
    }
    
    private static void ordenacionInsercion(int[] arreglo) {
        for(int i = 1; i < arreglo.length; i++){
            int actual = arreglo[i];
            int j = i - 1;
            
            // Mover elementos mayores que el actual una posición adelante
            while (j >= 0 && arreglo[j] > actual) {
                arreglo[j + 1] = arreglo[j];
                j--;
            }
            arreglo[j + 1] = actual;
        }
    }
}

Ordenación por Montículo

public class OrdenacionMonticulo {
    public static void main(String[] args) {
        int datos[] = {4,10,3,5,1};
        ordenacionPorMonticulo(datos);
        System.out.println("Array ordenado: " + Arrays.toString(datos));
    }
    
    public static void ordenacionPorMonticulo(int[] arreglo) {
        int n = arreglo.length;
        
        // Construir el montículo (reorganizar el array)
        for (int i = n / 2 - 1; i >= 0; i--) {
            montificar(arreglo, n, i);
        }
        
        // Extraer elementos uno por uno del montículo
        for (int i = n - 1; i > 0; i--) {
            // Mover la raíz actual al final
            int temporal = arreglo[0];
            arreglo[0] = arreglo[i];
            arreglo[i] = temporal;
            
            // Llamar a montificar en el montículo reducido
            montificar(arreglo, i, 0);
        }
    }
    
    private static void montificar(int[] arreglo, int n, int i) {
        int raiz = i;
        int hijoIzquierdo = 2 * i + 1;
        int hijoDerecho = 2 * i + 2;
        
        // Si el hijo izquierdo es más grande que la raíz
        if (hijoIzquierdo < n && arreglo[hijoIzquierdo] > arreglo[raiz]) {
            raiz = hijoIzquierdo;
        }
        
        // Si el hijo derecho es más grande que la raíz actual
        if (hijoDerecho < n && arreglo[hijoDerecho] > arreglo[raiz]) {
            raiz = hijoDerecho;
        }
        
        // Si la raíz no es el elemento más grande, intercambiar y continuar montificando
        if (raiz != i) {
            int intercambio = arreglo[i];
            arreglo[i] = arreglo[raiz];
            arreglo[raiz] = intercambio;
            
            // Recursivamente montificar el subárbol afectado
            montificar(arreglo, n, raiz);
        }
    }
}

Algoritmo de Eculides para Máximo Común Divisor

public class MaximoComunDivisor {
    public static void main(String[] args) {
        int a = 48;
        int b = 18;
        System.out.println("MCD de " + a + " y " + b + " es: " + mcd(a, b));
        
        int c = 60;
        int d = 48;
        System.out.println("MCD de " + c + " y " + d + " es: " + mcd(c, d));
    }

    // Algoritmo de Euclides
    public static int mcd(int a, int b) {
        while (b != 0) {
            int residuo = a % b;
            a = b;
            b = residuo;
        }
        return a;
    }
}

Patrón Singleton con Verificación Doble

public class SingletonSeguro {
    // Volatile para evitar problemas de visibilidad entre hilos
    private volatile static SingletonSeguro instanciaUnica;

    // Constructor privado para prevenir instanciación
    private SingletonSeguro(){}

    // Método público para obtener la instancia
    public static SingletonSeguro obtenerInstancia(){
        // Primera verificación (fuera del bloque sincronizado)
        if(instanciaUnica == null){
            synchronized (SingletonSeguro.class){
                // Segunda verificación (dentro del bloque sincronizado)
                if(instanciaUnica == null){
                    instanciaUnica = new SingletonSeguro();
                }
            }
        }
        return instanciaUnica;
    }
    
    public void mostrarMensaje() {
        System.out.println("Instancia Singleton: " + this.hashCode());
    }
}

Caché LRU (Menos Recientemente Usado)

import java.util.HashMap;
import java.util.Map;

public class CacheLRU {
    private int capacidad;
    private Map<Integer, Nodo> mapa = new HashMap<>();
    private Nodo cabeza = new Nodo(0, 0);
    private Nodo cola = new Nodo(0, 0);
    
    class Nodo {
        int clave, valor;
        Nodo prev, next;
        
        Nodo(int clave, int valor) {
            this.clave = clave;
            this.valor = valor;
        }
    }
    
    CacheLRU(int capacidad){
        this.capacidad = capacidad;
        cabeza.next = cola;
        cola.prev = cabeza;
    }
    
    int get(int clave){
        Nodo nodo = obtenerNodo(clave);
        if(nodo == null) return -1;
        
        // Mover el nodo al frente (más recientemente usado)
        moverAlFrente(nodo);
        return nodo.valor;
    }
    
    void put(int clave, int valor){
        Nodo nodo = obtenerNodo(clave);
        
        // Si el nodo existe, actualizar su valor
        if(nodo != null){
            nodo.valor = valor;
            moverAlFrente(nodo);
            return;
        }
        
        // Crear un nuevo nodo y agregarlo al frente
        nodo = new Nodo(clave, valor);
        agregarAlFrente(nodo);
        mapa.put(clave, nodo);
        
        // Si se supera la capacidad, eliminar el menos recientemente usado
        if(mapa.size() > capacidad){
            Nodo menosReciente = cola.prev;
            mapa.remove(menosReciente.clave);
            eliminarNodo(menosReciente);
        }
    }
    
    private Nodo obtenerNodo(int clave) {
        if(!mapa.containsKey(clave))
            return null;
        
        Nodo nodo = mapa.get(clave);
        moverAlFrente(nodo);
        return nodo;
    }
    
    private void moverAlFrente(Nodo nodo) {
        eliminarNodo(nodo);
        agregarAlFrente(nodo);
    }
    
    private void agregarAlFrente(Nodo nodo) {
        nodo.prev = cabeza;
        nodo.next = cabeza.next;
        cabeza.next.prev = nodo;
        cabeza.next = nodo;
    }
    
    private void eliminarNodo(Nodo nodo) {
        nodo.prev.next = nodo.next;
        nodo.next.prev = nodo.prev;
    }
}

Deadlock (Interbloqueo)

public class Interbloqueo {
    static final Object recurso1 = new Object();
    static final Object recurso2 = new Object();
    
    public static void main(String[] args) {
        Thread hilo1 = new Thread(new TareaHilo(), "Hilo-1");
        Thread hilo2 = new Thread(new TareaHilo(), "Hilo-2");
        hilo1.start();
        hilo2.start();
    }
    
    static class TareaHilo implements Runnable{
        @Override
        public void run() {
            if(Thread.currentThread().getName().equals("Hilo-1")){
                synchronized (recurso1){
                    System.out.println("Hilo-1 obtuvo Recurso1");
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                    synchronized (recurso2){
                        System.out.println("Hilo-1 obtuvo Recurso2");
                    }
                }
            } else {
                synchronized (recurso2){
                    System.out.println("Hilo-2 obtuvo Recurso2");
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                    synchronized (recurso1){
                        System.out.println("Hilo-2 obtuvo Recurso1");
                    }
                }
            }
        }
    }
}

Modelo Productor-Consumidor

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class ModeloProductorConsumidor {
    static int capacidad = 10;
    static BlockingQueue<Integer> cola = new ArrayBlockingQueue<>(capacidad);
    static int contador = 1;

    static class Productor implements Runnable {
        @Override
        public void run() {
            while (true) {
                try {
                    System.out.println(Thread.currentThread().getName() + " produciendo: " + contador);
                    cola.put(contero++);
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
    }

    static class Consumidor implements Runnable{
        @Override
        public void run() {
            while (true) {
                try {
                    int elemento = cola.take();
                    System.out.println(Thread.currentThread().getName() + " consumió: " + elemento);
                    Thread.sleep(1500);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
    }

    public static void main(String[] args) {
        Thread[] productores = new Thread[3];
        Thread[] consumidores = new Thread[3];
        
        for(int i = 0; i < productores.length; i++){
            productores[i] = new Thread(new Productor(), "Productor-" + (i + 1));
            productores[i].start();
        }

        for (int i = 0; i < consumidores.length; i++) {
            consumidores[i] = new Thread(new Consumidor(), "Consumidor-" + (i + 1));
            consumidores[i].start();
        }
    }
}