/* bisweepsort.c by mwberryman on metalshell.com
 *
 * Based on the sort algorithm in bubblesort.c which is
 * as simple as it gets in the sorting business.
 *
 * Added basic improvements to make a bi-directional sweep
 * sort.  Added check to short-circuit sort operation as soon
 * as the program detects that the array is sorted.  Limit
 * sweeping of values to the unsorted middle of the array.
 *
 * Also added some debugging messages so one can follow the
 * progress of a sort.
 *
 * http://www.metalshell.com/
 *
 */
 
#include <stdlib.h>
#include <stdio.h>
 
#define ARRAY_SIZE 20
 
void print_array(int *array) {
  int x;
  for(x = 0; x < ARRAY_SIZE; x++) {
    if(x != ARRAY_SIZE-1)
      fprintf(stdout, "%d, ", array[x]);
    else
      fprintf(stdout, "%d\n", array[x]);
  }
}
 
int main() {
  int iarray[ARRAY_SIZE];
  int x, y, holder;
 
  // Seed rand()
  srand((unsigned int)time(NULL));
 
  for(x = 0; x < ARRAY_SIZE; x++)
    iarray[x] = (int)(rand() % 100);
 
  fprintf(stdout, "Before Sort\n---------------\n");
  print_array(iarray);
  printf("\n");
 
 
  // Bubble sort method with bi-directional sweeping.
  //
  // Check after each sweep if any more sweeps need
  // to be done.  If any sweep results in no movement
  // of values then the array is sorted so short_circuit
  // the sort operation.
  //
  // After each sweep reduce the upper or lower limit
  // of array which must be swept.
 
 
  int ul=ARRAY_SIZE;
  int ll=0;
  int sorted=1;
  for(x = ll; x < ARRAY_SIZE; x++) {
 
    /* Sweep largest value to end */
 
    printf("x=%d\n",x);
    sorted=1;
    for(y = ll; y < ul-1; y++) {
      printf("y=%d ",y);
      if(iarray[y] > iarray[y+1]) {
        holder = iarray[y+1];
        iarray[y+1] = iarray[y];
        iarray[y] = holder;
        sorted=0;
      }
    }
    printf("\n");
    print_array(iarray);
 
    /* short circuit the process if array is now sorted */
    if (sorted) { printf("Found sorted A\n"); break; }
 
    /* Reduce upper limit on array since the larger values have
       been swept to the end. */
    ul--;
 
   /* Bubble smallest value to beginning */
 
    sorted=1;
    for(y = ul-1; y > ll; y--) {
      printf("y=%d ",y);
      if(iarray[y] < iarray[y-1]) {
        holder = iarray[y-1];
        iarray[y-1] = iarray[y];
        iarray[y] = holder;
        sorted=0;
      }
    }
    printf("\n");
    print_array(iarray);
 
    /* short circuit the process if array is now sorted */
    if (sorted) { printf("Found sorted B\n"); break; }
 
    /* Increase lower limit on array since the smaller values have
       been swept to the beginning. */
    ll++;
  }
 
  fprintf(stdout, "\nAfter Sort\n---------------\n");
  print_array(iarray);
 
}