0

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: enter image description here

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):

enter image description here

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
        {   

        }
    }   
}    
}
3

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.

If this answers your question, please accept the answer to remove your question from the unanswered question pool. Let's keep up on forum maintenance. ;-)

| improve this answer | |
  • 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
1

Consider what happens, when i = n - 1.

| improve this answer | |
  • 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .