using System;
using System.Text;

namespace Practica4Tema3
{
    // lista enlazada
    class Nodo
    {
        public int valor;
        public Nodo siguiente;

        public Nodo(int valor)
        {
            this.valor = valor;
            this.siguiente = null;
        }
    }

    public class Practica4Tema3
    {
        // imprimir enlazada
        public static void imprimirLista(Nodo head)
        {
            Nodo actual = head;
            StringBuilder sb = new StringBuilder();
            while (actual != null)
            {
                sb.Append(actual.valor);
                if (actual.siguiente != null)
                {
                    sb.Append(" ---> ");
                }
                actual = actual.siguiente;
            }
            Console.WriteLine(sb.ToString());
        }

        // Bubble para enlazada
        public static void bubbleSort(Nodo head)
        {
            if (head == null) return;

            bool intercambiado;
            int iteracion = 1;

            do
            {
                intercambiado = false;
                Nodo actual = head;

                Console.WriteLine("Iteracion #" + iteracion + " burbujeando...");
                while (actual.siguiente != null)
                {
                    if (actual.valor > actual.siguiente.valor)
                    {
                        // Intercambiar valores
                        int temp = actual.valor;
                        actual.valor = actual.siguiente.valor;
                        actual.siguiente.valor = temp;
                        intercambiado = true;
                    }
                    actual = actual.siguiente;
                }
                imprimirLista(head);
                iteracion++;
            } while (intercambiado);
        }

        public static void Main(string[] args)
        {
            // Enlazada valores fijos
            Nodo head = new Nodo(42);
            head.siguiente = new Nodo(12);
            head.siguiente.siguiente = new Nodo(89);
            head.siguiente.siguiente.siguiente = new Nodo(5);
            head.siguiente.siguiente.siguiente.siguiente = new Nodo(23);

            Console.WriteLine("Lista enlazada ORIGINAL (desordenada):");
            imprimirLista(head);

            // Aplicar Bubble Sort
            bubbleSort(head);

            Console.WriteLine("\nLista enlazada ORDENADA (con Burbujitas aplicadas):");
            imprimirLista(head);
            Console.WriteLine("Del caos al orden");
        }
    }
}