1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C Bubble sort help

  1. Jul 26, 2011 #1
    Hi,

    I am trying to write a program that sorts an array of random numbers.
    Unfortunately, it does not work out as i had hoped, im getting some strange output.


    Here's my code:
    Code (Text):

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


    /* Function Prototypes */
    int rand(void);
    void srand(unsigned int seed);
    void bubblesort(int array[]);

    static unsigned long int next = 1;


    int main() {

        int array[10000] = { 0 };
        int *ap,*fp;
        srand(23);


       
        for(ap = array; ap<&array[1000]; ap++) {      
            *ap = rand();
        }
           
            /*Sort it*/
            bubblesort(&array[10000]);

          /*Print it*/
          for (fp = array; fp<&array[10000]; fp++)
              printf("%d ",*fp);
                 
                  return 0;
    }

    void bubblesort(int array[]) {
       

        int ARRAY_LENGTH,temp;
        ARRAY_LENGTH = sizeof(array)/sizeof(int);
       
        for(int i=0; i<ARRAY_LENGTH; i++) {

                if(array[ARRAY_LENGTH] < array[ARRAY_LENGTH - i]) {
                        temp = array[ARRAY_LENGTH];
                        array[ARRAY_LENGTH] = array[ARRAY_LENGTH -i];
                        array[ARRAY_LENGTH -i] = temp;
                }

        }

    }
       
    int rand(void) {

    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536)%32768;
    }

    void srand(unsigned int seed) {
           
            next = seed;
    }
     
     
  2. jcsd
  3. Jul 26, 2011 #2

    I like Serena

    User Avatar
    Homework Helper

    Hi James! :smile:

    I'll start from the top.

    Your for-loop to fill the array fills only the first 1000 elements, so 9000 elements will be left uninitialized. In this case they will be zero though.

    In your call to bubblesort you index the array with 10000 and take the address of that element.
    But that is out of range.
    So you'd not be sorting the actual array.
    You should specify simply "array" as parameter instead of "&array[10000]".

    In your bubblesort function you have specified int array[] as parameter.
    Here you have a common pitfall.
    In itself this is correct, but it gives no clue to how big the array is.
    You should pass the size of the array as a separate parameter.

    In your bubblesort function you try to calculate the ARRAY_LENGTH with sizeof(array)/sizeof(int).
    In itself this is a proper way to find the number of elements in the array, but not here.
    As I mentioned before, when you pass an array to a function, you lose the information about how big it is.
    Typically you should do this calculation before calling the function, and pass this size as a parameter.

    In your bubblesort function you index the array with ARRAY_LENGTH, but this element is not part of the array (if it would have been properly calculated). It is one beyond the last.
    So your algorithm for bubblesort is flawed.
    Where did you get it?
    The if-statement as you have it won't work.

    Cheers! :smile:
     
  4. Jul 26, 2011 #3
    Hello Serena!

    Thanks for the input.

    I've made the said above corrections.
    Why wont the if statement work?
     
  5. Jul 26, 2011 #4

    I like Serena

    User Avatar
    Homework Helper

    Before I explain further, can you show your corrections please?
     
  6. Jul 26, 2011 #5
    Code (Text):

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


    /* Function Prototypes */
    int rand(void);
    void srand(unsigned int seed);
    void bubblesort(int array[],[color=red]int arraysize[/color]);

    static unsigned long int next = 1;


    int main() {

        int array[10000] = { 0 };
        int *ap,*fp;
        srand(23);


       
        for(ap = array; ap<&array[[color=red]10000[/color]]; ap++) {      
            *ap = rand();
        }
           
            /*Sort it*/
            [color=red]bubblesort(array,sizeof(array)/sizeof(int));[/color]

          /*Print it*/
          for (fp = array; fp<&array[10000]; fp++)
              printf("%d ",*fp);
                 
                  return 0;
    }

    void bubblesort(int array[],[color=red]int arraysize[/color]) {
       
                          .
                          .
                          .


       

        }
     
     
    Last edited: Jul 27, 2011
  7. Jul 26, 2011 #6
    What coding scheme is this?
     
  8. Jul 27, 2011 #7

    I like Serena

    User Avatar
    Homework Helper

    Your corrections look good! :smile:

    What do you know about the bubblesort algorithm and how it works?
    Why is it called "bubble" sort for that matter?
     
  9. Jul 27, 2011 #8
    It steps through the whole list and 'pushes' the smaller elements towards the beginning. Ie swaps a and b, if a > b.
     
  10. Jul 27, 2011 #9

    I like Serena

    User Avatar
    Homework Helper

    Yes, it steps through the list, and (usually) compares 2 consecutive elements, and swaps them if applicable.
    I think it also works if you compare each element in the list with the last one and swap them if applicable.
    As yet, you're not indexing the last element, but the one beyond it.

    If you run through the list like that once, will it be sorted when you've done?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: C Bubble sort help
  1. Bubble-sort algorithm (Replies: 3)

Loading...