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];
}

---

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.

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.

>> 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().

Quote:

---

Originally Posted by Daved

>> 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.

>> 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.

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;
  }
}

---

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.

Quote:

---

Originally Posted by Sentral

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.

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 laserlight

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.