SelectionSortOnList

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct list_t list_t;
struct list_t {
  int element;
  list_t *next;
};
static int random_int(int upper);
static int *new_random_array(int n);
static void puts_array(int *a, int n);
static list_t *new_cell(int element);
static list_t *make_list(int n);
static void puts_list(list_t *head);
static void selection_sort_recur(int *a, int n);
static void selection_sort_on_list_recur(list_t **head);
int main(void);
static int random_int(int upper) {
  return (int) ((rand() / ((double) RAND_MAX + 1.)) * upper);
}
static int *new_random_array(int n) {
  int i;
  int *a = (int *) malloc(n * sizeof(int));
  for (i = 0; i < n; i++)
    a[i] = random_int(100);
  return a;
}
static void puts_array(int *a, int n) {
  int i;
  printf("[");
  for (i = 0; i < n; i++) {
    printf("%d", a[i]);
    if (i < n - 1) printf(", ");
  }
  printf("]\n");
}
static list_t *new_cell(int element) {
  list_t *new = (list_t *) malloc(sizeof(list_t));
  new->element = element;
  new->next = NULL;
  return new;
}
static list_t *make_list(int n) {
  int i;
  list_t *head, *p;
  for (i = 0; i < n; i++) {
    if (i == 0) {
      head = new_cell(random_int(100));
      continue;
    }
    p = new_cell(random_int(100));
    p->next = head;
    head = p;
  }
  return head;
}
static void puts_list(list_t *head) {
  list_t *p;
  printf("[");
  for (p = head; p; p = p->next) {
    printf("%d", p->element);
    if (p->next) printf(", ");
  }
  printf("]\n");
}
static void selection_sort_recur(int *a, int n) {
  int i = 0, j, min = a[0];
  if (n == 1) return;
  for (j = 1; j < n; j++)
    if (a[j] < min) {
      min = a[j];
      i = j;
    }
  if (i != 0) {
    a[i] = a[0];
    a[0] = min;
    selection_sort_recur(a + 1, n - 1);
  }
}
static void selection_sort_on_list_recur(list_t **head) {
  list_t *p, *min = *head, *prev, *prev_min = *head;
  if (!(*head)->next) return;
  for (prev = *head, p = (*head)->next; p; prev = p, p = p->next)
    if (p->element < min->element) {
      min = p;
      prev_min = prev;
    }
  if (prev_min != *head) {
    prev_min->next = *head;
    p = min->next;
    min->next = (*head)->next;
    (*head)->next = p;
    *head = min;
    selection_sort_on_list_recur(&((*head)->next));
  }
}
int main(void) {
  const int n = 10;
  int *a;
  list_t *head;
  srand((unsigned) time(NULL));
  puts("Array:");
  a = new_random_array(n);
  puts_array(a, n);
  selection_sort_recur(a, n);
  puts_array(a, n);
  puts("List:");
  head = make_list(n);
  puts_list(head);
  selection_sort_on_list_recur(&head);
  puts_list(head);
  return 0;
}