Help understanding bubblesort hw?

This is a discussion on Help understanding bubblesort hw? within the C Programming forums, part of the General Programming Boards category; When swch stays with a value of zero, then the sorting will stop....

  1. #46
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    When swch stays with a value of zero, then the sorting will stop.

  2. #47
    Registered User
    Join Date
    Apr 2009
    Posts
    34
    that doesn't work cause i can type in 6 and get a negative number sir

  3. #48
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    [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:

    Quote 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;
    }
    Last edited by MK27; 04-20-2009 at 04:08 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #49
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You're going to tell me what negative number you're talking about, right?

    I was worried about your sleep after Midnight, now I'm worried about mine!

  5. #50
    Registered User
    Join Date
    Apr 2009
    Posts
    34
    i've never heard of a flag, my teacher is an idiot.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    /* The actual method of sorting */
    
    void bubblesort(int a[],int n);
    
    int main()
    {
        int list = 0;
        int a[4] = { 4, 8, 2, 1};
        printf("Before: ");
        while(list < sizeof(a) / sizeof(a[0]))
            printf("%d", a[list++]);
        printf("\n");
        bubblesort(a, sizeof(a) / sizeof(int));
        list = 0;
        printf("After: ");
        while(list < sizeof(a) / sizeof(a[0]))
            printf("%d", a[list++]);
        printf("\n");
        system("pause");
        return 0;  
    }
    
    
    /*Defining the bubblesort*/ 
    void bubblesort(int a[],int n) 
    {
        printf("Please enter an integer: ");
        scanf("%d", &n);
        int cmp, pass, tmp, swch;
        pass = 0;
        cmp = 0;
        swch = 1;
        while(swch)
        {
            swch = 0;
            cmp = 1;
            while(cmp < n - pass)
            {
                if(a[cmp-1] > a[cmp])
                {
                     swch = 1;
                     tmp = a[cmp-1]; 
                     a[cmp-1] = a[cmp]; 
                     a[cmp] = tmp;
                }
                cmp++;
            }    
            pass++; 
        }     
        printf("Our Sort had %d comparisons, and %d passes\n", cmp, pass);
    }
    if i use that code and type in the number 6
    i get the answer of -1124

  6. #51
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by beretta View Post
    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...
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #52
    Registered User
    Join Date
    Apr 2009
    Posts
    34
    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

  8. #53
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You don't need sizeof, anything.

    If you were malloc'ing your own memory dynamically, then you would need sizeof().

  9. #54
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Looks mostly fine to me...

    Quote Originally Posted by beretta View Post
    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.
    Last edited by MK27; 04-20-2009 at 04:31 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #55
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    MK, how is sizeof() going to help sort an array of 100 elements, which might hold only 20 numbers in it?

    Since it's not dynamically allocated, why emphasize sizeof(), when sizeof() won't help in the above case, which is common?

  11. #56
    Registered User
    Join Date
    Apr 2009
    Posts
    34
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    /* The actual method of sorting */
    
    void bubblesort(int a[],int n);
    
    int main()
    {
        int n;
        int list = 0;
        int a[4] = { 4, 8, 2, 1};
        printf("Please enter an integer: ");
        scanf("%d", &n);
        printf("Before: ");
        while(list < sizeof(a) / sizeof(a[0]))
            printf("%d", a[list++]);
        printf("\n");
        bubblesort(a, sizeof(a) / sizeof(int));
        list = 0;
        printf("After: ");
        while(list < sizeof(a) / sizeof(a[0]))
            printf("%d", a[list++]);
        printf("\n");
        system("pause");
        return 0;  
    }
    
    
    
    /*Defining the bubblesort*/ 
    void bubblesort(int a[],int n) 
    {
        int cmp, pass, tmp, end;
        pass = 1;
        
        while(pass <= n-1)
        {
           cmp = 0;
           end = n - 1 - pass;
            while(cmp <= end)
            {
                if(a[cmp] > a[cmp+1])
                {
                     
                     tmp = a[cmp]; 
                     a[cmp] = a[cmp+1]; 
                     a[cmp+1] = tmp;
                     cmp++;
                }
               pass++; 
            }    
             
        }     
        printf("Our Sort had %d comparisons, and %d passes\n", cmp, pass);
    }
    what about this version. can you fix this one?

  12. #57
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Last edited by Adak; 04-20-2009 at 04:52 AM.

  13. #58
    Registered User
    Join Date
    Apr 2009
    Posts
    34
    how can you make sense of it?

  14. #59
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.
    Last edited by MK27; 04-20-2009 at 05:03 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  15. #60
    Registered User
    Join Date
    Apr 2009
    Posts
    34
    didn't work for me

Page 4 of 5 FirstFirst 12345 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 05:21 PM
  2. Replies: 10
    Last Post: 12-05-2008, 12:47 PM
  3. Understanding Headers
    By AeonMoth in forum C++ Programming
    Replies: 2
    Last Post: 06-27-2007, 06:53 AM
  4. trouble understanding the source file structure
    By Mario F. in forum C++ Programming
    Replies: 5
    Last Post: 05-26-2006, 07:46 PM
  5. understanding recursive functions
    By houler in forum C Programming
    Replies: 7
    Last Post: 12-09-2004, 12:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21