Sorting

/* Program: sorting.c
 * ---------------------------------------------------------------------
 * This program implements and demonstrates several algorithms for
 * sorting arrays of integers.
 * ---------------------------------------------------------------------
 * Course: Data structures practical
* ---------------------------------------------------------------------
 */


/* Header files */

#include <stdio.h>


/* Selection sort */

void ssort (int a[], int n)
{
   int i, j;

   for (i = 0; i < n-1; i++) {
      int min = a[i], minj = i;

      for (j = i+1; j < n; j++)
         if (a[j] < min)
            min = a[minj = j];

      a[minj] = a[i];
      a[i] = min;
   }
}


/* Insertion sort */

void isort (int a[], int n)
{
   int i, j;

   for (i = 1; i < n; i++) {
      int x = a[i];

      for (j = i-1; j >= 0; j--)
         if (x < a[j])
            a[j+1] = a[j];
         else
            break;
         a[j+1] = x;
   }
}


/* Bubble sort */

void bsort (int a[], int n)
{
   int i, j;

   for (i = 0; i < n; i++)
      for (j = n-1; j > i; j--)
         if (a[j-1] > a[j]) {
            int temp = a[j-1];

            a[j-1] = a[j];
            a[j] = temp;
         }
}


/* Quick sort */

void qsort_auxil (int a[], int lower, int upper)
{
   if (lower < upper) {
      int x = a[(lower + upper) / 2];
      int i = lower, j = upper;

      for (i = lower, j = upper; i <= j; i++, j--) {
         while (a[i] < x) i++;
         while (a[j] > x) j--;

         if (i <= j) {
            int temp = a[i];

            a[i] = a[j];
            a[j] = temp;
         }
      }
      qsort_auxil(a, lower, j);
      qsort_auxil(a, i, upper);
   }
}

void qsort (int a[], int n)
{
   qsort_auxil(a, 0, n-1);
}


/* Main program -- for testing */

int test (int a[], int n)
{
   int i;

   for (i = 1; i < n; i++)
      if (a[i-1] > a[i]) {
         printf("\nERROR IN SORTING !!!\n\n");
         return 0;
      }
   return 1;
}


int main ()
{
   const int c[] = { 44, 55, 12, 42, 94, 18, 6, 67 };

#define n (sizeof(c) / sizeof(c[0]))

   int x[n];
   int i;

   printf("Original array:\n");
   for (i=0; i<n; i++) printf("%d ", c[i]); printf("\n");

   printf("\nSelection sort:\n");
   for (i=0; i<n; i++) x[i] = c[i];
   ssort(x, n);
   for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
   test(x, n);

   printf("\nInsertion sort:\n");
   for (i=0; i<n; i++) x[i] = c[i];
   isort(x, n);
   for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
   test(x, n);

   printf("\nBubble sort:\n");
   for (i=0; i<n; i++) x[i] = c[i];
   bsort(x, n);
   for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
   test(x, n);

   printf("\nQuick sort:\n");
   for (i=0; i<n; i++) x[i] = c[i];
   qsort(x, n);
   for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
   test(x, n);

   return 0;
}