Puzzle DE50

Sort an array using D46 and D48

[E-7] Write function that uses the answers to D46 and D48 to sort an array. In other words, sort an integer array by randomly scrambling it until it ends up sorted. Here is a testing program:

int randInt( int min, int max );
void scrambleArray( int size, int arr[] );
int inOrder( int size, int arr[] );

void reallyBadSort( int size, int arr[] );

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

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

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

Here is a result of running the program:

  58   49   75   60    0    2   38   19   14   53
  93   68

start: 1107849418
end  : 1107849706
elapsed time: 288 seconds

   0    2   14   19   38   49   53   58   60   68
  75   93

Sorting an array of 12 integers on my 3GHz 64-bit Athlon took 288 seconds, almost 5 minutes! This is because this algorithm takes O(n!) time. Sorting an array of 13 integers will take 13 times longer than the array of 12 integers, or about 65 minutes. Sorting an array of 14 integers takes 14 times longer than that, or 910 minutes, about 15 hours. Sorting an array of 17 integers will take about ten years. This is not a practical algorithm.