C50 Answer

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

/* Puzzle C50 -- randomly scramble an array until it is sorted
|
*/
int randInt( int min, int max );
void scrambleArray( int arr[], int size );

void reallyBadSort( int arr[], int size )
{
  while ( inOrder( arr, size ) > 0 )
    scrambleArray( arr, size );
}

int inOrder( int arr[], int size )
{
  int j, count=0 ;

  for ( j=0; j<size-1; j++ )
  {
    if ( arr[j] > arr[j+1] ) count++ ;
  }

  return count;
}

void scrambleArray( int arr[], int size )
{
  int j, twin; /* element j and its twin are swapped */
  int twinVal;

  for ( j=0; j<size-1; j++ )
  {
    /* for each element j, pick a random twin and swap */
    twin = randInt(j,size-1);
    twinVal = arr[twin];
    arr[twin] = arr[j];
    arr[j] = twinVal;
  }
}

void printArray( int arr[], int size )
{
  const int N = 10;
  int j;
  
  for ( j=0; j<size; j++ )
  {
    if ( j%N == N-1 )
      printf("%4d\n", arr[j] );
    else
      printf("%4d ", arr[j] );    
  }
}

int randInt( int min, int max )
{
  return (rand()*(max-min+1))/(RAND_MAX+1) + min ;
}

void fillArrayRandom( int arr[], int size, int low, int high )
{
  int j;
  for ( j=0; j<size; j++ )
    arr[j] = randInt( low, high );
}

int main(int argc, char *argv[])
{
  const int SIZE = 20 ;
  int x[SIZE] ;
  int num;
  long start, end;
  
  srand( time(0) );
  fillArrayRandom( x, SIZE, 0, 100 );
  printArray( x, SIZE );
  printf("\n\n");

  printf( "start: %ld\n", start=time(0) );
  
  reallyBadSort( x, SIZE );
  
  printf( "end  : %ld\n", end=time(0) );
  printf( "elapsed time: %ld seconds\n\n", end-start );
  printArray( x, SIZE );

  printf("\n\n");
  system("PAUSE");	
  return 0;
}