CODEWITHSUNDEEP
arrayscsortingbubble-sort
random dude
random dude

Reputation: 63

Why do I get a random number in the first element of the sorted array?

I am new to C and when I do this which makes the elements in the list arranged:

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

int main()
{
    int list[] = {6, 4, 8, 1, 0, 9, 11, 50, 60, 10};
    int i, j, aux, k;
    int len = sizeof(list) / sizeof(list[0]);
    for (i = 0; i < len; i++)
    {
        for (j = 0; j < len; j++)
        {
            if (list[j] > list[j + 1])
            {
                aux = list[j + 1];
                list[j + 1] = list[j];
                list[j] = aux;
            }
        }
    }
    for (k = 0; k < len; k++)
    {
        printf("%d  ", list[k]);
    }
    return 0;
}

Output :

-13168  0  1  4  6  8  9  10  11  50

Why is the first value -13168?

Upvotes: 1

Views: 413

Answers (5)

anastaciu
anastaciu

Reputation: 23832

As said list[j + 1] steps out of the bounds of the array, and as said using for (j = 0; j < len - 1; j++) will solve the issue.

However, as it is, the second loop will always go through the entire array and that is not needed, as the values are swapped i will be incremented and the number of needded iterations will become lesser , so you can use i iterator in the stop condition of the second loop thus optimizing it by reducing the number of iterations.

for (i = 0; i < len - 1; i++) //len - 1 is enough
{
    for (j = 0; j < len - i - 1; j++) //replacing < len with  < len - i - 1
    {
        if (list[j] > list[j + 1])
        {
            aux = list[j + 1];
            list[j + 1] = list[j];
            list[j] = aux;
        }
    }
}

Live demo

This is a more appropriate bubble sort.

Even for such a small array the difference in performance is noticeable, but there is still room for improvement.

When a swap no longer occurs in the loop it means that the array is sorted, so if we were to add a flag to stop ordering when this happens then you would have a very well optimized bubble sort algorithm:

int ordered = 0;
//...    
for (i = 0; i < len - 1; i++)
{
    ordered = 0; //reset flag
    for (j = 0; j < len - i - 1; j++)
    {
        if (list[j] > list[j + 1])
        {
            aux = list[j + 1];
            list[j + 1] = list[j];
            list[j] = aux;  
            ordered = 1; //if the swap occurs, the ordering continues
        }
    }
    if (ordered == 0) //otherwise the array is ordered and the ordering ends
        break; 
}

Live demo

As you can see by the testing this is a very fast bubble sort.

Benchmark results:

enter image description here

Upvotes: 0

abraxas
abraxas

Reputation: 29

There is an error in the second loop:

for(j = 0; j < len; j++)

should be

for(j = 0; j < len - 1; j++)

Upvotes: 0

Bimal Raj Gyawali
Bimal Raj Gyawali

Reputation: 1

When you are accessing list[j+1], you are out of bound in last iteration .

So, change inner loop to :

       for(j=0;j<len-1;j++){ }

Upvotes: 0

Holger
Holger

Reputation: 919

Your outer loop is useless. You never use i. I think you wanted:

for(i=0;i<len;i++){
    for(j=0;j<i;j++){
        if(list[j] > list[i]){
            aux = list[i];
            list[i] = list[j];
            list[j] = aux;
        }
    }
}

Upvotes: 0

Yunnosch
Yunnosch

Reputation: 26763

Both your i and your j walk all the range of legal indices in the array.
But you do access list[j+1] which is one beyond the array, read there and sort the value you get from there.

Upvotes: 1

Related Questions