/* bubblesort.c
 *
 * Bubblesort sorting algorithm implemented recursively.
 *
 * Copyright (C) David Thomas, 2010-2017.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* ----------------------------------------------------------------------- */

/* recursive bubblesort interior */
static int bubblesort_swap(int *a, int nelems, int depth, int highest)
{
  /* we test pairs of numbers. so the final case is when nelems is one, not
   * zero */
  if (nelems <= 1)
    return highest;

  if (a[0] > a[1])
  {
    /* swap */
    int t = a[0];
    a[0] = a[1];
    a[1] = t;

    highest = depth;
  }

  return bubblesort_swap(a + 1, nelems - 1, depth + 1, highest);
}

/* recursive bubblesort exterior */
static void bubblesort__recursive(int *a, int nelems)
{
  int highest;

  highest = bubblesort_swap(a,
                            nelems,
                            1 /* initial depth */,
                            0 /* initial 'highest' */);
  if (highest > 0)
    bubblesort__recursive(a, highest);
}

/* iterative bubblesort */
static void bubblesort__loop(int *a, int nelems)
{
  int max = nelems - 1;

  do
  {
    int i;
    int highest;

    /* swap overlapping pairs of values */
    highest = 0;

    for (i = 0; i < max; i++)
    {
      int t;

      if (a[i] <= a[i + 1])
        continue;

      /* swap */
      t = a[i];
      a[i] = a[i + 1];
      a[i + 1] = t;

      highest = i;
    }

    /* only need to go this high next iteration */
    max = highest;
  }
  while (max > 0);
}

/* ----------------------------------------------------------------------- */

/* is the given array sorted? (loop variant) */
static int is_ordered__loop(const int *a, int nelems)
{
  while (--nelems)
  {
    if (a[0] > a[1])
      return 0; /* not ordered */
    a++;
  }

  return 1; /* we ran out of elements: the array must be ordered */
}

/* is the given array sorted? (recursive variant) */
static int is_ordered__recursive(const int *a, int nelems)
{
  /* we test pairs of numbers. so the final case is when nelems is one, not
   * zero */
  if (nelems <= 1)
    return 1; /* we ran out of elements: the array must be ordered */

  if (a[0] > a[1])
    return 0; /* not ordered */

  return is_ordered__recursive(a + 1, nelems - 1);
}

/* ----------------------------------------------------------------------- */

#define MINRAND 0
#define MAXRAND 100
static void generate_random(unsigned int seed, int *a, int n)
{
  srand(seed);

  while (n--)
    *a++ = MINRAND + rand() / (RAND_MAX / (MAXRAND - MINRAND + 1) + 1);
}

/* ----------------------------------------------------------------------- */

#define MAXELEMS 20
#define SEED 0xa8cb8794

void test_bubblesort(void)
{
  int a[MAXELEMS];
  int b[MAXELEMS];
  int i;

  /* first test the looping variant */

  generate_random(SEED, a, MAXELEMS);
  bubblesort__loop(a, MAXELEMS);

  for (i = 0; i < MAXELEMS - 1; i++)
    printf("%d, ", a[i]);
  printf("%d\n", a[i]);

  if (!is_ordered__loop(a, MAXELEMS))
    fprintf(stderr, "Failure: Loop results are not ordered!\n");

  /* now test the recursive variant */

  generate_random(SEED, b, MAXELEMS);
  bubblesort__recursive(b, MAXELEMS);

  for (i = 0; i < MAXELEMS - 1; i++)
    printf("%d, ", b[i]);
  printf("%d\n", b[i]);

  if (!is_ordered__recursive(b, MAXELEMS))
    fprintf(stderr, "Failure: Recursive results are not ordered!\n");

  /* do they match? */

  if (memcmp(a, b, MAXELEMS * sizeof(a[0])) != 0)
  {
    fprintf(stderr, "Failure: Sorted results don't match!\n");
    return;
  }

  printf("OK!\n");
}

int main(void)
{
    test_bubblesort();
}