#include <stdlib.h>

typedef struct Element
{
  int data;
  struct Element* next;
} Element;

typedef Element* List;


int compare_elements_greater(const Element *lhs, const Element *rhs)
{
  return lhs->data > rhs->data;
}


void bubble_sort(List *root, int (*comparison)(const Element*, const Element*))
{
  // If the list has 0 or 1 element, it is already sorted:
  if (! *root || !(*root)->next)
    return;

  // Otherwise use extra stupid sort:
  int num_changes;
  do
    {
      num_changes = 0;
      Element **p1 = root;
      Element *p2 = *root;
      Element *p3 = (*root)->next;
      
      while (p3)
        {
          if (comparison(p2, p3))
            {
              ++num_changes;
              
              *p1 = p3; 
              p2->next = p3->next; 
              p3->next = p2;        
              
              p1 = &p3->next;
              p3 = p2->next;  
            }
          else
            {
              p1 = &p2->next;
              p2 = p3;
              p3 = p3->next; 
            }
        }
    }
  while (num_changes);
}


List create_list()
{
  return NULL;
}


int insert_list(int value, List *list)
{
  List old_list = *list;
  *list = malloc(sizeof(Element));
  if (*list)
    {
      (*list)->data = value;
      (*list)->next = old_list;
      return 1;
    }
  else
    {
      *list = old_list;
      return 0;
    }
}


void delete_list(List* list)
{
  while (*list)
    {
      List next = (*list)->next;
      free(*list);
      *list = next;
    }
}


List iterate_list(List *list)
{
  *list = (*list)->next;
  return *list;
}


int get_list_data(List list)
{
  return list->data;
}



#include <time.h>
#include <stdio.h>

int main()
{
  List list = create_list();

  srand(time(0));
  for(int i = 0; i < 25; ++i)
    {
      if (!insert_list(rand() % 42, &list))
        {
          fputs("Fehler beim Einfügen!\n", stderr);
          goto Exception;
        }
    }

  bubble_sort(&list, &compare_elements_greater);

  for(List iterator = list; iterator; iterate_list(&iterator))
    {
      printf("%d\n", get_list_data(iterator));
    }

 Exception:
  delete_list(&list);
}