Thread: Psuedo random numbers in a bubble sort.

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    17

    Psuedo random numbers in a bubble sort.

    Basically, I'm unsure of how to utilize the function rand(). All I want to do is create 20 random numbers, use a bubble sort on them, print the sorted list and the time it takes to sort it.

    Code:
    #include <cstdlib>
    #include <iostream>
    #include <ctime>
    #include <cstdlib>
    
    using std::cout;
    using std::endl;
    
    int main()
    {
        void bubble(int a[], int n);
        void print(int a[], int n);
        int random(int n);
        
        int n = 20;
        int a[n];
        
        a[n] = random(n);
        clock_t start = clock();
        bubble(a, n);
        clock_t end = clock();
        print(a, n);
        double time_elapsed = double(end - start)/CLOCKS_PER_SEC;
        
        system("PAUSE");
    }
    
    void swap(int a, int b)
    {
       int temp;
       
       temp = a;
       a = b;
       b = temp;
    }
    
    void bubble(int a[], int n)
    {
       int sorted = false;
       int pass = 1;
       
       while (pass < n && !sorted)
       {
          sorted = true;
          for ( int i = 0; i <= n - pass - 1; i++)
          {
             if (a[i] > a[i + 1])
             {
                swap(a[i], a[i + 1]);
                sorted = false;
             }
          }
          pass = pass + 1;
       }
    }
    
    void print(const int a[], int n)
    {
       for (int i = 0; i <= n; i++)
          cout << a[i] << " " << endl;
    }
    
    int random(int n)
    {
       int a[n];
       
       for (int i = 0; i <= n; i++)
          a[i] = rand();
       return a[n];
    }

  2. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Current standard C++ doesn't support variable-length arrays, so you can't do this.
    Code:
        int n = 20;
        int a[n];
    For starters, try a static array.

    Pass parameters to random in the same way you do to print. An array of size n may be indexed from 0 to n-1. Note this issue in this loop:
    Code:
       for (int i = 0; i <= n; i++)
    Consider using a much larger array if you want to actually notice the difference.

    Also, consider seeding the random number generator. The FAQ mentions some of this.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    17
    Code:
    int n = 10;
    int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    So I change it to a static array but I still get the message:

    Code:
    [Linker error] undefined reference to `print(int*, int)'
    And as for clock, I plan on creating an array with 50,000 numbers, but I wanted to test 20 first.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> I'm unsure of how to utilize the function rand().
    Do you want to make rand() give different values each time you run the program? If so, you should seed the random number generator with the current time and srand().

    Do you want all the numbers to be within a specific range? If so, then you will want to manipulate the result of rand() to fit it in that range. Otherwise, it will return a number between 0 and RAND_MAX (I think that's inclusive).

    >> a[n] = random(n);
    This is not what you want. You should pass a into random and let it fill the array. a[n] is out of bounds and not a valid member of the array.

    >> Current standard C++ doesn't support variable-length arrays, so you can't do this.
    You could also make n a const int which would make it legal in C++ since the array size would be a compile time constant.

    >> undefined reference to `print(int*, int)'
    Move the function declarations above main().

  5. #5
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by Daved View Post
    >> Current standard C++ doesn't support variable-length arrays, so you can't do this.
    You could also make n a const int which would make it legal in C++ since the array size would be a compile time constant.
    Aye. But the stack size issue may come into play at some point, considering the arrays' declarations.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> But the stack size issue may come into play at some point, considering the arrays' declarations.
    True, I hadn't seen the 50,000 item comment.

    I would use a vector for any array that is too large to fit on the stack.

  7. #7
    Registered User
    Join Date
    Mar 2006
    Posts
    17
    Ok, so I got random to work, but my bubble isn't working now. It seems to be exiting the function before it does any sorting because I get the same order I had before the sort as I have afterwards. Here is the sort posted again just in case I made any changes from the previous version.

    Code:
    void swap(int a, int b)
    {
       int temp;
       
       temp = a;
       a = b;
       b = temp;
    }
    
    void bubble(int a[], int n)
    {
       int sorted = false;
       int pass = 1;
       
       while (pass < n && !sorted)
       {
          sorted = true;
          for ( int i = 0; i <= n - pass - 1; i++)
          {
             if (a[i] > a[i + 1])
             {
                swap(a[i], a[i + 1]);
                sorted = false;
             }
          }
          pass = pass + 1;
       }
    }

  8. #8
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    If you're going to end up using 50,000 numbers, I would suggest another algorithm. Bubble sort is going to take a long time to sort that. I would go with shell sort.

    Edit... even shell sort would be too slow with 50,000, you'll have to use merge sort.
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  9. #9
    Registered User
    Join Date
    Mar 2006
    Posts
    17
    Quote Originally Posted by Sentral View Post
    If you're going to end up using 50,000 numbers, I would suggest another algorithm. Bubble sort is going to take a long time to sort that. I would go with shell sort.

    Edit... even shell sort would be too slow with 50,000, you'll have to use merge sort.
    Well, using a bubble sort and timing how long it takes is the point of this program, so using another one wouldn't really suffice.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I think your bubble sort is not actually swapping anything, because your swap() function takes its arguments by value instead of by reference.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Mar 2006
    Posts
    17
    Quote Originally Posted by laserlight View Post
    I think your bubble sort is not actually swapping anything, because your swap() function takes its arguments by value instead of by reference.
    Yup, that was it. I can't believe I didn't catch that.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help generating multiple random numbers
    By d-dub in forum C++ Programming
    Replies: 7
    Last Post: 10-30-2006, 01:00 PM
  2. Storing random number in array(sequential search & bubble sort)
    By dukethacore in forum C++ Programming
    Replies: 5
    Last Post: 07-20-2005, 08:28 AM
  3. Another brain block... Random Numbers
    By DanFraser in forum C# Programming
    Replies: 2
    Last Post: 01-23-2005, 05:51 PM
  4. random numbers
    By ballmonkey in forum C++ Programming
    Replies: 3
    Last Post: 01-18-2005, 02:16 PM
  5. Bubble Sort... which type?
    By gflores in forum C++ Programming
    Replies: 8
    Last Post: 08-15-2004, 04:48 AM