0

I am testing my implementation of the sort algorithm in pset3, so I added the code to generate pseudo random numbers so I could test. I found that the while loop only gets executed randomly. For example, when I try ./testsort 300 to generate 300 random numbers, sometimes it works and sometimes it does not!

When I try to generate a lower amount of random numbers, for example with ./generate 100, it always work. But when the amount of random numbers to generate increases, the execution gets sloppy( sometimes it works, sometimes it does not ). Very high numbers, like 1000, never work though.

Why does this happen?

#define _XOPEN_SOURCE

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

void sort(int values[], int n);

// upper limit on range of integers that can be generated
#define LIMIT 65536

const int MAX = 2000;

int main(int argc, string argv[])
{
  // generate random numbers
  int randomValues[MAX];

  // if command line arguments does not equal
  // 2 and 3, send user error message
  if (argc != 2 && argc != 3)
  {
      printf("Usage: ./generate n [s]\n");
      return 1;
  }

  // convert the first argument to an integer
  int n = atoi(argv[1]);

  // if seed is provided, seed the random number generator
  if (argc == 3)
  {
      srand48((long) atoi(argv[2]));
  }
  else
  {
      srand48((long) time(NULL));
  }

  // output n numbers of pseudorandom numbers
  for (int i = 0; i < n; i++)
  {
      randomValues[i] = (int) (drand48() * LIMIT);
      //printf("%i\n", (int) (drand48() * LIMIT));
  }

  for (int i = 0; i < n; i++)
  {
    printf("[%i] -> %i\n",i , randomValues[i]);
  }

  sort(randomValues, n);

  // success
  return 0;
}


/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    int intHolder1;
    int intHolder2;
    bool stillsorting;
    int sortcount;

    stillsorting = true;

    while ( stillsorting == true ){
    sortcount = 0;
    for( int i=0; i<=(n - 2); i++ ){

      if( values[i] > values[i + 1] ){

          //swap them
          intHolder2 = values[i]; // 41 (assumption)
          intHolder1 = values[i + 1 ]; // 39
          values[i + 1] = intHolder2;
          values[i] = intHolder1;

        }
        else if(  values[i] < values[i + 1] ) {
          sortcount += 1;
        }

        if( sortcount == (n - 1) ){
          stillsorting = false;
          //printf("sortcount is %i\n", sortcount);
        } 

      }
    }
  //printf("sortcount is %i\n", sortcount);

  for( int i=0; i<=(n - 1); i++ ){
    printf("(sorted)values[%i] is  %i\n", i, values[i]);
  }
}
2

The while loop is not random. The sort function doesn't handle duplicates (ie values[i] == values[i + 1]) so the while loop goes "infinite" because if( sortcount == (n - 1) ) is never true. I suspect if you run the program 10 times in a row with 100, it will eventually fail. As n gets bigger, it is more likely there will be duplicates in randomNumbers.

1
  • Thank you. I also found from a friend about the birthday problem which is closely related to my question. link
    – Dami
    Jun 6 '17 at 5:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .