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! :frown:

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. :p
Still need to use pointers, though...

Quote:

---

... 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.

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.

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

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];

Quote:

---

Originally Posted by camel-man

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.

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...

In C, that is a common error - going out of bounds in an array access. You have to watch it.