Arrays and Values

[zeppelyn]

So, I'm merely just a student learning and all that. The assignment has four components: write a bubble sort function with test program, write a quick sort function with a test program, write a shell sort function with a test program, then finally write a main program. For each compare in the array, it'll cost a unit, and for each swap costing 6.

#include <iostream>
#include <stdlib.h>

#define N 20

using namespace std;
int bsort(int Ar[], int count, int swc)
  {
    int swaps;
    swaps = 1;
    while(swaps)
      {
        swaps = 0;
        for (int i = 0; i < N - 1; i++)
          {
            count++;
            if (Ar[i] > Ar[i + 1])
              {
                swap(Ar[i], Ar[i + 1]);
                swaps = 1;
                swc += 6;
              }
          }
      }
    return count;
    return swc;
  }

#if __INCLUDE_LEVEL__ < 1

int main()
  {
    int Ar[N], count, swc;
    for (int i = 0; i < N; i++){Ar[i] = rand() % 100;}
    for (int x = 0; x < N; x++){cout << bsort(&Ar[x], count, swc) << endl;}
  }

#endif

I know that there's an issue with processing all that, but I'm really unclear as to how to get that done - to be able to sort the array and get the costs for the compares and swaps. I'm sorry if I seem very.. unintelligent about it.

[Ancient Dragon]

int bsort(int Ar[], int count, int swc)

Are you required to use that or did you make it up yourself? I would have passed count and swc by reference so that the bsort() can change it for main(). Then in main() you don't call bsort() in a loop, but only once.

Also, replace that define on line 4 with const.

const int N = 20;
int bsort(int Ar[], int& count, int& swc)
{


}

int main()
{
    int Ar[N], count = 0, swc = 0;
    for (int i = 0; i < N; i++)
    {
        Ar[i] = rand() % 100;
    }
    bsort(Ar,count,swc);
}

[zeppelyn]

Okay, so I did as you said, and compiled it and it ran, but when I originally ran it.. I ended up with 280 compare units, and 690 swap units as the costs. Does that sound reasonable? Because it sounds too high to me. I haven't done it on paper yet, but I feel that it'd be a lot lower. I changed the remainder in rand from 100 to 10, and ended up with less swap units, but more compare units.

#include <iostream>
#include <stdlib.h>
using namespace std;

const int N = 20;

int bsort(int Ar[], int& count, int& swc)
  {
    int swaps;
    swaps = 1;
    while(swaps)
      {
        swaps = 0;
        for(int i = 0; i < N - 1; i++)
          {
            count++;
            if(Ar[i] > Ar[i + 1])
              {
                swap(Ar[i], Ar[i + 1]);
                swaps = 1;
                swc += 6;
              }
          }
      }
    for(int x = 0; x < N; x++)
      {
        cout << Ar[x] << endl;
      }
  }

int main()
  {
    int Ar[N], count = 0, swc = 0;
    for(int i = 0; i < N; i++)
      {
        Ar[i] = rand() % 10;
      }
    bsort(Ar, count, swc);
    cout << endl;
    cout << count << endl;
    cout << swc << endl;
  }

I also just wrote my shell sort part of the assignment, and ended up with the same results as the compare and swap costs.

[WaltP]

The number of compares in a real bubble sort is the Summation of N, N=0 to n-1. What is 1+2+3...+19?

Yours on the other hand is (20*20)-1 I believe.

So you might want to loop up how a real buble sort is defined and correct yours.

[zeppelyn]

I looked up the bubble sort and it's basically the same thing that I have in my program.

http://mathbits.com/MathBits/CompSci/Arrays/Bubble.htm

[WaltP]

I looked up the bubble sort and it's basically the same thing that I have in my program.

Really? I see 1 while and 1 for in your program. The program you linked to uses 2 for statements.

I tested your sort with a 'real' bubble sort and came up with this:

Given an array in sorted order the number of compares for:
yours: 19 -- real: 19 (minimum)

Given an array in reverse order the number of compares for:
yours: 380 -- real: 190 (maximum)

Given an array in random order the number of compares for:
yours: 247 -- real: 169

[zeppelyn]

Tried it your way, still got same results.

void bsort(int Ar[], int& count, int& swc)
  {
    int swaps, N = 20;;
    swaps = 1;
    for(int i = 1; i <= N && swaps; i++)
      {
        swaps = 0;
        for(int j = 0; j < (N - 1); j++)
          {
            count++;
            if(Ar[j] > Ar[j + 1])
              {
                swap(Ar[j], Ar[j + 1]);
                swaps = 1;
                swc += 6;
              }
          }
      }
    for(int x = 0; x < N; x++)
      cout << Ar[x] << endl;
  }

At this point, I think it's just got something to do with my count and swc variables, but I'm also not sure where to put them if I continue getting such high numbers.

[WaltP]

I tried the code you pointed to. It's the same as yours. It's kind of a bad algorithm.

Here's mine:

    compare = 0    
    loop from j = 0 to N-2  // for (j=0; j<N-1; j++)
    {
        swaps = 0;
        loop from i = 1 to N-j-1
            increment compare
            test if Array(i-1) > Array(i)
                if so, swap
                increment swaps
        if swaps is 0 exit loop j
    }

compare will now contain the number of compares made.

[WaltP]

I now see where you got your initial algorithm. It's in Wikipedia along with a couple enhancements.

[zeppelyn]

Yeah, so I guess my main question with it now is: why count and swc are so high? I don't think they should be that high, even with a bubble sort, but when I do the same in the shell sorting algorithm, I get the same results. So I'm not sure if it's an issue with the count and swc variables, or if it's a problem with the algorithm itself.

All the algorithms I'm given are from the professor himself, so I'm quite clear as to what it is I'm doing wrong with the two variables.

[WaltP]

No, it's your naive algorithm. You go throught the comparisons a maximum of (N-1)^2 [361] times

If you stop comparing the values that are already in place, you can cut the comparisons to the summation(0-19) [190] times.