Thread: Bubblesort

  1. #1
    Registered User
    Join Date
    Oct 2011
    Location
    Southampton, United Kingdom
    Posts
    7

    Arrow Bubblesort

    Hi all,

    I'm learning C for the first time as part of my engineering degree and one of my labs recently required that I write a Bubblesort algorithm (to demonstrate my use of pointers e.t.c.). But I couldn't do it!

    We were given this snippet of code to start us off and a link to the Bubblesort wiki page to view the description and Pseudocode.

    Code:
    void sort(const int * input, int * output, const int size)
    Now, I got so far as to do ONE successful pass.

    E.g. from an array of numbers 9876543210 my program would give 8765432109.

    Code:
    #include <stdio.h>
    
    #define ARRAY_SIZE 10
    
    
    void sort(const int * input, int * output, const int size);
    
    
    int main(void)
    {
        
            int mixed[ARRAY_SIZE] = { 9,8,7,6,5,4,3,2,1,0 };
            int fixed[ARRAY_SIZE] = { 9,8,7,6,5,4,3,2,1,0 };
            sort(mixed,fixed,ARRAY_SIZE);
    
    
    }
    
    
    void sort(const int * input, int * output, const int size)
    {
    
    
        int i = 0;
        int temp;
        for (i=0;i<size;++i)
        {
            if (output[i]>output[i+1])
            {
                temp = output[i];
                output[i] = output[i+1];
                output[i+1] = temp;
            }
        }
        for (i=0;i<size;i+=1)
        {
        
            printf("%i\n",output[i]);
        
        }
    }
    This code kinda sucks, I know. I didn't use pointers fully and "input" is not used at all. But I really don't know how to progress from here.

    All the example code I've seen on the internet have a nested for loop, something like this:

    Code:
    • int i,j,t;
    • for(i=n-2;i>=0;i--)
    • {
    • for(j=0;j<=i;j++)
    • {



    ... So I was about to ask wtf is happening here - but I think I just figured it out. For every pass (limited by i, so that j+1 never exceeds the size of the array), i is decreased by 1 and the loop starts again!

    Am I right?

    Anyway... first post, hello all, I will probably be returning soon.
    Still need to use pointers, though...

  2. #2
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    ... So I was about to ask wtf is happening here - but I think I just figured it out. For every pass (limited by i, so that j+1 never exceeds the size of the array), i is decreased by 1 and the loop starts again!

    Am I right?
    Well, yes, that is what's going on.

    The effect of one pass of bubblesort is that the largest element in your array is in the correct position (eg, at the end). So the idea is that if you do a pass over each range 0 <= j <= i where i decreases like in the example code, you end up getting the largest element at position n, the second largest at n-1, etc. ...until i == 0 and then the list is sorted.
    Consider this post signed

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    BubbleSort normally sorts in-place, but you could always start by copying from the input array to the output array and then just sorting the output array in-place.
    The loop for printing the output afterwards should really be back in main.
    Show us how you get on with the nested loops.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User svanski's Avatar
    Join Date
    Oct 2011
    Posts
    8
    Bubble sort - Wikipedia, the free encyclopedia On right side they have small animation where you can see how bubble sort works.

    You have done good job so far the only thing you have left is repetition of. So basically all you need is a big loop in your sort function.

    Code:
     I will give you "pseudo" code [I used while loop.]
    
    
    some "counter variable" that is same as array size or is initialized to zero;.
    
    while  (while that counter is not zero or is not equal to size of your array) [depends what you decide your counter variable to be] {
    
    then do the loops that you have already...
    
    decremented  or increment variable [again depends how you set your counter variable ]
    
    } close while loop 
    and do print loop.
    Hope this helps

  5. #5
    Registered User camel-man's Avatar
    Join Date
    Jan 2011
    Location
    Under the moon
    Posts
    693
    correct me if im wrong
    Code:
      for (i=0;i<size;++i)
        {
            if (output[i]>output[i+1])
            {
                temp = output[i];
                output[i] = output[i+1];
                output[i+1] = temp;
            }
        }
    Wouldnt it be best to go to size-1? that way he wont go off the end of the array when referring to output[i+1];

  6. #6
    Registered User svanski's Avatar
    Join Date
    Oct 2011
    Posts
    8
    Quote Originally Posted by camel-man View Post
    Wouldnt it be best to go to size-1? that way he wont go off the end of the array when referring to output[i+1];
    This is a good point; I am pretty noob to C programming so do not take my word for it. However, I tested this code with some modifications and I think, it knows that the array at the end has "\0" value, which represents the end. So even if he ran loop 12 times he will be running around the circles so basically resorting the array. If you "printf output[size +1 or +5 or...]" you will see that depending on +"#" it will go to the end and then jump to the begging of the array and continue counting... ( I tested the code on gcc [Linaro] 4.4.5). And that is what I observed.

  7. #7
    Registered User svanski's Avatar
    Join Date
    Oct 2011
    Posts
    8
    I was wrong. The results that I was getting were not right. If you print more than the size you are going off to forbidden land. C does not puts \0 automatically at the end...

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    In C, that is a common error - going out of bounds in an array access. You have to watch it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bubblesort Help
    By xanimeangiex in forum C++ Programming
    Replies: 1
    Last Post: 11-20-2010, 05:33 PM
  2. Need help with Bubblesort
    By kburyanek in forum C Programming
    Replies: 9
    Last Post: 11-13-2009, 02:41 PM
  3. old and new bubblesort?
    By ingenting in forum C Programming
    Replies: 2
    Last Post: 05-11-2009, 01:41 PM
  4. C++ bubblesort and structure help
    By ReignFire in forum C++ Programming
    Replies: 2
    Last Post: 10-17-2005, 02:25 AM
  5. bubblesort
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 10-02-2001, 10:45 PM