/**
 * ss.c - A simple program to analyze shell sort.
 */

// +---------+--------------------------------------------------------
// | Headers |
// +---------+

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


// +-----------+------------------------------------------------------
// | Constants |
// +-----------+

// The sizes of arrays we're testing
#define SIZES { 16, 32, 64, 128 }

// The number of sizes
#define NUM_SIZES 4

// The number of tests to do per size
#define TESTS_PER_SIZE 32


// +---------+--------------------------------------------------------
// | Globals |
// +---------+

static int comparisons;
static int assignments;


// +-----------+------------------------------------------------------
// | Functions |
// +-----------+

/**
 * shell_sort, annotated to count assignments and comparisons.
 */
void 
shell_sort (int a[], int size)
{
  int i, j;
  int h = 1;

  do 
    {
      h = h * 3 + 1;
    } 
  while (h <= size);

  do 
    {
      h /= 3;
      for (i = h; i < size; i++)
        {
          int v = a[i];
          for (j = i; j >= h && ++comparisons && a[j - h] > v; j -= h)
            {
              ++assignments;
              a[j] = a[j - h];
            }
          if (i != j)
            {
              ++assignments;
              a[j] = v;
            }
        } // for
    } 
  while (h != 1);
} // shell_sort

/**
 * Experimentally analyze the running time of shell sort for an array 
 * of the specified size.
 */
void
analyze_ss (int size)
{
  int rep;
  int i;

  int min_assignments = INT_MAX;
  int min_comparisons = INT_MAX;
  int max_assignments = 0;
  int max_comparisons = 0;
  int sum_assignments = 0;
  int sum_comparisons = 0;
  int values[size];

  // Repeat TESTS_PER_SIZE times
  for (rep = 0; rep < TESTS_PER_SIZE; rep++)
    {
      // Reset the counts
      assignments = 0;
      comparisons = 0;
      // Initialize the array
      for (i = 0; i < size; i++)
        values[i] = rand ();
      // Sort the array
      shell_sort (values, size);
      // Update data
      if (comparisons < min_comparisons)
        min_comparisons = comparisons;
      if (comparisons > max_comparisons)
        max_comparisons = comparisons;
      sum_comparisons += comparisons;
      if (assignments < min_assignments)
        min_assignments = assignments;
      if (assignments > max_assignments)
        max_assignments = assignments;
      sum_assignments += assignments;
    } // for

  // Print results
  printf ("|%5d || %5d | %5d | %5d || %5d | %5d | %5d |\n",
          size,
          min_comparisons, sum_comparisons/TESTS_PER_SIZE, max_comparisons,
          min_assignments, sum_assignments/TESTS_PER_SIZE, max_assignments);
} // analyze_ss

int
main (int argc, char *argv[])
{
  int i;
  int sizes[] = SIZES;

  if (argc > 1)
    srand (atoi (argv[1]));

  printf ("| SIZE ||      COMPARISONS      ||      ASSIGNMENTS      |\n");
  printf ("|      ||  MIN  |  AVE  |  MAX  ||  MIN  |  AVE  |  MAX  |\n");

  for (i = 0; i < NUM_SIZES; i++)
    {
      analyze_ss (sizes[i]);
    }

  return 0;
} // main