Needing some advice with my Bubble Sort.

[zeppelyyn]

So, I say Bubble Sort, but it's actually one piece of an assignment that encompasses the bubble, shell, and quick sorts. But I feel if I get some advice with one that it'll put me in the right direction to finishing the others as well. Ultimately, my bubble sort generates an array of 20 random numbers, sorts the array, but while it's sorting, it's also supposed to count the costs of comparisons and swaps.

Basically, a compare costs 1 unit, and a swap costs 6 units. I just need some idea of where to start in order to calculate it, because right now, my comparison cost counts all the way up to (most recently) 2060866457.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

#define N 20

int bubble(int thatAR[])
  {
    int swaps = 1;
    int cost;

    while(swaps)
      {
        swaps = 0;

        for (int i = 0; i < N-1; i++)
          {
            if (thatAR[i] > thatAR[i+1])
              {
                cost++;
                swap(thatAR[i], thatAR[i+1]);
                swaps = 1;
              }
          }
      }
    return cost;
  }

#if __INCLUDE_LEVEL__ < 1

int main()
  {
    int thisAR[N];
    int cost;

    srand((unsigned)time(NULL));
    for(int i = 0; i < N; i++)
      {
        thisAR[i] = rand()%100;
      }

    cout << "Unsorted: ";
    for(int i = 0; i < N; i++)
      {
        cout << thisAR[i] << " ";
      }
    cout << endl;

    bubble(thisAR);
    cost = bubble(thisAR);

    cout << "Sorted  : ";
    for (int x = 0; x < N; x++)
      {
        cout << thisAR[x] << " ";
      }
    cout << endl;
    cout << endl;

    cout << "COST: ";
    cout << cost << endl;

    return 0;
  }

#endif

Try not to be too harsh. :)

[ccsdude]

the reason why cost is something like that is because you didn't initialize it so it gets a random junk value...
Simpli change line 11 int cost = 0

By the way I think you should erase line 50 or are you meant to sort it twice?

[zeppelyyn]

Okay, so I do have my program fixed basically (after you mentioned line 50), because originally my idea was to sort it, then since my bubble function returned cost, that I'd make it equal to cost in my main function. But as to your original advice of changing line 11, I had already tried that previously and it was always printing out "0" as the cost. It wouldn't do anything but print 0 until I had just initialized the variable by itself without a value.

But I ended up rewriting the program and it seems like it does what it's supposed to now.

In case you were interested in how I ended up fixing it (which you're probably not, but oh well, heh):

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

#define N 20

void bubble(int thatAR[])
   {
      int swaps = 1;
      int cost = 0;
      int swcost = 0;

      cout << "UNSORTED: ";
      for (int i = 0; i < N; i++)
         {
            cout << thatAR[i] << ' ';
         }
      cout << endl;

      while (swaps)
         {
            swaps = 0;

            for (int j = 0; j < N-1; j++)
               {
                  cost++;
                  if (thatAR[j] > thatAR[j+1])
                     {
                        swap(thatAR[j], thatAR[j+1]);
                        swaps = 1;
                        swcost += 6;
                     }
               }
         }

      cout << "SORTED  : ";
      for (int x = 0; x < N; x++)
         {
            cout << thatAR[x] << ' ';
         }
      cout << endl;

      cout << "\nCOST: " << cost << " COMPARES, ";
      cout << swcost << " SWAPS" << endl;
   }

#if __INCLUDE_LEVEL__ < 1

int main()
   {
      int thisAR[N];

      srand(time(NULL));
      for (int i = 0; i < N; i++)
         {
            thisAR[i] = rand()%100;
         }

      bubble(thisAR);
      return 0;
   }

#endif 

[andywestken]

It would be better if you passed the array size as a function parameter, rather than using the global. Then you can eliminate the #define.

void bubble(int thatAR[], int N)
   {
      // etc 

int main()
   {
      const int N = 20; // rather than #define
      int thisAR[N];

      srand(time(NULL));
      for (int i = 0; i < N; i++)
         {
            thisAR[i] = rand()%100;
         }

      bubble(thisAR, N); // pass size
      return 0;
   }

Andy

PS why += 6 when you swap?

[vlad from moscow]

You could decrease the number of operations if the upper limit of the loop

            for (int j = 0; j < N-1; j++)
               {
                  cost++;
                  if (thatAR[j] > thatAR[j+1])
                     {
                        swap(thatAR[j], thatAR[j+1]);
                        swaps = 1;
                        swcost += 6;
                     }
               }
         }

would be decreased by one after each iteration of the while loop.