/* 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);

}