# Pastebin smVgAebl
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int n = 10;			// integer array of size n

// SETUP  --------------------------------------------------------------------

void
fill_array (int *array, int n)
{
  int i;
  for (i = 0; i < n; i++)
    {
      array[i] = n - i;
    }
}

void
print_array (int *array, int n)
{
  int i;
  printf ("[");
  for (i = 0; i < n; i++)
    {
      if (i == (n - 1))
	printf ("%d]\n", array[i]);
      else
	printf ("%d, ", array[i]);
    }
}

// ALGORITHMS ----------------------------------------------------------------------------
// ------ BUBBLE
void
bubble_sort (int array[], int n)
{
  int c, d, t;

  for (c = 0; c < n - 1; c++)
    {
      for (d = 0; d < n - c - 1; d++)
	{
	  if (array[d] > array[d + 1])
	    {
	      t = array[d];
	      array[d] = array[d + 1];
	      array[d + 1] = t;
	    }
	}
    }
}

 // ------ SHAKER
void
shaker_sort (int array[], int n)
{

  register int a;
  int sort;
  int t;

  do
    {
      sort = 0;
      for (a = n - 1; a > 0; --a)
	{
	  if (array[a - 1] > array[a])
	    {
	      t = array[a - 1];
	      array[a - 1] = array[a];
	      array[a] = t;
	      sort = 1;
	    }
	}
      for (a = 1; a < n; ++a)
	{
	  if (array[a - 1] > array[a])
	    {
	      t = array[a - 1];
	      array[a - 1] = array[a];
	      array[a] = t;
	      sort = 1;
	    }
	}
    }
  while (sort);
}

 // ------ DECK
void
deck_sort (int array[], int n)
{
  int c, d, t;

  for (c = 1; c <= n - 1; c++)
    {
      d = c;

      while (d > 0 && array[d - 1] > array[d])
	{
	  t = array[d];
	  array[d] = array[d - 1];
	  array[d - 1] = t;

	  d--;
	}
    }

}

// ----- Selection
void
selection_sort (int array[], int n)
{
  int c, d, t, position, swap;
  for (c = 0; c < (n - 1); c++)
    {
      position = c;

      for (d = c + 1; d < n; d++)
	{
	  if (array[position] > array[d])
	    position = d;
	}
      if (position != c)
	{
	  swap = array[c];
	  array[c] = array[position];
	  array[position] = swap;
	}
    }

}

// ----- SHELL

void
shell_sort (int array[], int n)
{
  int i, j, k, tmp;
  for (i = n / 2; i > 0; i = i / 2)
    {
      for (j = i; j < n; j++)
	{
	  for (k = j - i; k >= 0; k = k - i)
	    {
	      if (array[k + i] >= array[k])
		break;
	      else
		{
		  tmp = array[k];
		  array[k] = array[k + i];
		  array[k + i] = tmp;
		}
	    }
	}
    }
}

// ------ QUICKSORT

void
quicksort (int array[], int n, int m)
{
  int i, j, pivot, temp;

  if (m < n)
    {
      pivot = m;
      i = m;
      j = n;

      while (i < j)
	{
	  while (array[i] <= array[pivot] && i < n)
	    i++;
	  while (array[j] > array[pivot])
	    j--;
	  if (i < j)
	    {
	      temp = array[i];
	      array[i] = array[j];
	      array[j] = temp;
	    }
	}

      temp = array[pivot];
      array[pivot] = array[j];
      array[j] = temp;


      quicksort (array, m, j - 1);
      quicksort (array, j + 1, n);

    }
}

// ----------------------------------------------------------------------------


void
test (void (*f) (int *, int))
{
  time_t start, end;
  double dif;
  int *array = NULL;
  array = (int *) malloc (n * (sizeof (int)));

  fill_array (array, n);
  //print_array (array, n);

  time (&start);
  (*f) (array, n);
  time (&end);
  dif = difftime (end, start);
  printf (" took %f seconds to run.\n", dif);
  //print_array (array, n);
}

void
testq (void (*f) (int *, int, int))
{
  time_t start, end;
  double dif;
  int *array = NULL;
  array = (int *) malloc (n * (sizeof (int)));

  fill_array (array, n);
  //print_array (array, n);

  time (&start);
  (*f) (array, n, 0);
  time (&end);
  dif = difftime (end, start);
  printf (" took %f seconds to run.\n", dif);
  //print_array (array, n);
}

// ------ MAIN
int
main ()
{

  printf ("1. Bubble sort     |");
  test (bubble_sort);
  printf ("2. Shaker sort     |");
  test (shaker_sort);
  printf ("3. Deck sort       |");
  test (deck_sort);
  printf ("4. Selection sort  |");
  test (selection_sort);
  printf ("5. Shell sort      |");
  test (shell_sort);
  printf ("6. Quick sort      |");
  testq (quicksort);

  return 0;
}