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?
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;
}
}
}
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;
}
As you can see by the testing this is a very fast bubble sort.
