# pset3 --> bubble sort

I am in sort section of . I am implementing a bubble sort algorithm, but it seems that, although `values[]` is being sorted, elements are being moved one position forward in memory. For example:

For the command ./generate 5 2

• The values given are:

the array of values

But when sorted the array looks like this (I am using printf just to see how the array is looking, which and where are the values):

I WONDER WHAT IS THE ISSUE HERE AND ANY CLUE TO SOLVE IT.

The code for `void sort(int values[], int n)` is this:

``````void sort(int values[], int n)
{
// TODO: implement an O(n^2) sorting algorithm

for(int h = 0; h < n ; h++)
{
for( int i = 0; i < n; i++)
{
if (values[i+1] < values[i])
{

int temp = values[i];
values[i] = values[i +1];
values[i+1] = temp;

printf("cycle = %i\n", i);
printf("    values[i] --> %i\n", values[i]);
printf("    values[i+1] --> %i\n", values[i+1]);
printf("    values[i+2] --> %i\n", values[i+2]);
printf("    values[i+3] --> %i\n", values[i+3]);
printf("    values[i+4] --> %i\n", values[i+4]);
printf("    values[i+5] --> %i\n\n", values[i+5]);

}
else
{

}
}
}
}
``````

The problem is that you are swapping values[i] with values[i+1] while also allowing i to go to a maximum of n-1.

Let's say that n=10, so the array has 10 elements, 0 through 9. When the code sorts through the array, at the end of the first pass, i=9. The code compares values[i] to values[i+1], or values[9] to values[10], which isn't defined. Instead of erroring out, it's treating values[10] as 0, and sorts it to the bottom of the list. Once the sort is complete, it's also ejecting the largest value from the list, since values[10] isn't defined.

So, to fix this, you need to make a change to the limits of i so that you don't go beyond the end of the array.

Next issue: The outer loop cycles h from 0 to n. So does the inner loop for i. This causes the sort to reprocess every element on every pass, including those that have already been sorted. I suggest a review of the class material and shorts on sorts.

As a side note, why do you have an else clause in the code? It serves no purpose and can be removed.

• Thanks Cliff, I am working on the implementations of your suggestions, which I think have the answer. As soon as I implement this I'll mark my question as answered. – Esteban Londono Jul 13 '15 at 22:18

Consider what happens, when i = n - 1.

• Thank Mikkel. But if i = n-1 this results: values[i] --> 36285 values[i+1] --> 37569 values[i+2] --> 52527 values[i+3] --> 59797 values[i+4] --> 0 values[i+5] --> 0 – Esteban Londono Jul 12 '15 at 18:12
• What @Mikkel is trying to imply is that when `i` gets to `n - 1` you are accessing memory outside of the reserved, and not only it gives you wrong numbers (0 in your example) but it could also make your program crash. – ChrisG Jul 12 '15 at 18:44
• why did you put all these printfs in the loop which will have the indexes more than n? is it your last result?( the one which you have printed) – mojtaba1 Jul 12 '15 at 19:04