Thread: Help understanding bubblesort hw?

[edit] WHOOPS! I just noticed there's 4 pages here, not 2! (I though the last post was hours ago)...anyway you might find this handy:

Originally Posted by your prof

...an improvement. The improvement is based on the following observation. When there is no exchange between any data in a pass of the bubble sort, the sequence
is already sorted in non-decreasing order. As a result, there is no need to continue and hence can terminate the sort.

That's a modified bubblesort; it uses a flag:

Code:

#include "stdio.h"

void bubblesort (int *ray, int len) {
        int i, flag=0, tmp;
        while (flag==0) {
                for (i=0;i<len-1;i++) {  /* loop thru all the elements, first to SECOND last */
                        if (ray[i]>ray[i+1]) {        /* (since we must compare to the next element) */
                                tmp=ray[i+1];
                                ray[i+1]=ray[i];
                                ray[i]=tmp;
                                flag++;    /* a change made, flag goes up */
                        }   
                }   
                if (flag==0) break;    /* no changes made! while loop is finished */
                flag=0; /* reset flag */
        }   
}

int main () {
        int ray[11]={666,10,6,34,5,16,102,45,7,9,1}, i;
        bubblesort(ray,11);
                /* verify */
        for (i=0;i<11;i++) printf("%d\n",ray[i]);
        return 0;
}

Originally Posted by beretta

i've never heard of a flag, my teacher is an idiot.

Yeah, sorry -- I honestly didn't notice the rest of the thread and thought you'd gotten stuck. Don't get too distracted by my little contribution

The reason you're not using a flag is you're not using two loops in the function, you're using a control loop for the function, which should accomplish the same thing, so that's okay. Lemme take a look at your last post...

Looks mostly fine to me...

Originally Posted by beretta

yea, and honestly im not even sure if i should be using:
while(list < sizeof(a) / sizeof(a[0])) or bubblesort(a, sizeof(a) / sizeof(int));
meaning the sizeof parts

Well, you are suppose to be inputing all the data anyway, so that will determine the number you are calculating now with sizeof.

The bubblesort is done, now you just have to organize the rest of it. Move this into main:

Code:

printf("Please enter an integer: ");
scanf("%d", &n);

The last place that should be is in the sort function. You want to get all the user input *before* anything else happens.

Then just turn your while/printf loop

Code:

while(list < sizeof(a) / sizeof(a[0]))
        printf("%d", a[list++]);

into an actual function, as per the prof's specs.

w/r/t the user input have you/are you supposed to use malloc() to create a dynamically sized array?

ps. you are using a flag -- you call it "swch". I thought of it that way too (as something that's switched on as a signal). The term "flag" prevents confusion with the "switch/case" construct which is used in C and most other languages.

No. It makes no sense in main().

sizeof(a) / sizeof(a[0]) will not tell you how many elements are being used in the array, so it's no good for this.

I think the sizeof issue is a red herring at this point.

Here's a way to input the data. If you aren't using malloc(), then you need to set the array bigger than the user could possibly want it; n will act as a control with the functions, so the extra elements won't be involved.

Code:

#include <stdio.h>
#include <stdlib.h>

void showarray (int *rayptr, int len) {
        int i=0;
        while (i<len) {
                printf("%d ",rayptr[i]);
                i++;
        }
        printf("\n");
}

int main() {
        int n, a[100], i=0; /* presume we won't need more than one hundred numbers */
        printf("Enter an array size: ");
        scanf("%d",&n);
        printf("Enter %d numbers seperated by spaces: ",n);
        while (i<n) {
                scanf("%d",&a[i]);
                i++;
        }   
                /* verify using a showarray function */
        showarray(a,n);
        return 0;
}

Just combine that with your bubblesort. This does not verify the input -- it presumes the user is able to properly enter the numbers.