C Bubble Sort Help | Get Programming Assistance

[James889]

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, I am getting some strange output.


Here's my code:

#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;
}

 

[I like Serena]

Hi James!

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!

 

[James889]

Hello Serena!

Thanks for the input.

I've made the said above corrections.
Why won't the if statement work?

 

[I like Serena]

Before I explain further, can you show your corrections please?

 

[James889]

#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]) {
    
                      .
                      .
                      .   

    }

 

[GreenPrint]

What coding scheme is this?

 

[I like Serena]

Hello Serena!

Thanks for the input.

I've made the said above corrections.
Why won't the if statement work?

Your corrections look good!

What do you know about the bubblesort algorithm and how it works?
Why is it called "bubble" sort for that matter?

 

[James889]

It steps through the whole list and 'pushes' the smaller elements towards the beginning. Ie swaps a and b, if a > b.

 

[I like Serena]

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?