#include <iostream>

// This is a quick node struct with underlying integral data type.
struct Node
{
    int Data;
    Node* Link;

    Node(int data, Node* link)
    {
        Data = data;
        Link = link;
    }
};

// This is the function that swaps two nodes. Its parameters are
// addresses of pointers that point to the elements to be swapped.
void node_swap(Node** a, Node** b)
{
    Node* a1 = *a;
    Node* a2 = a1->Link;

    Node* b1 = *b;
    Node* b2 = b1->Link;

    b1->Link = a1;
    a1->Link = b2;

    *a = b1;
}

int main()
{
    // This is a quick linked list that is obviously unsorted.
    Node z(67, nullptr);
    Node y(49, &z);
    Node x(55, &y);
    Node w(60, &x);
    Node v(78, &w);
    Node u(77, &v);
    Node t(10, &u);
    Node s(69, &t);
    Node r(82, &s);
    Node q(28, &r);
    Node p(29, &q);
    Node o(27, &p);
    Node n(14, &o);
    Node m(95, &n);
    Node l(91, &m);
    Node k(79, &l);
    Node j(31, &k);
    Node i( 3, &j);
    Node h(37, &i);
    Node g(76, &h);
    Node f(99, &g);
    Node e(65, &f);
    Node d(19, &e);
    Node c(64, &d);
    Node b(35, &c);
    Node a(51, &b);

    Node* head = &a;

    // This is to display the entire linked list.
    std::cout << "Unsorted: ";
    
    for (Node* t = head; t != nullptr; t = t->Link)
    {
        std::cout << t->Data << ' ';
    }

    std::cout << std::endl;

    // This is the bubble sort algorithm.
    bool has_swapped;

    do
    {
        has_swapped = false;

        for (Node** t = &head; (*t)->Link != nullptr; t = &(*t)->Link)
        {
            if ((*t)->Data > (*t)->Link->Data)
            {
                node_swap(t, &(*t)->Link);
                has_swapped = true;
            }
        }
    } while (has_swapped);    

    // This is to display the entire linked list.
    std::cout << "  Sorted: ";
    
    for (Node* t = head; t != nullptr; t = t->Link)
    {
        std::cout << t->Data << ' ';
    }

    std::cin.get();

    return 0;
}