Trying to understand bubblesort function

Question

I am fairly new to C and programming in general, and I have a question about looping in the following bubble sort function:

    void sort(int values[], int n);
    {
        int c, d, t;

        for (c = 0; c < (n - 1); c++)
        {
            for (d = 0; d < c - n - 1; d++)
            {
                if (values[d] > values[d + 1])
                {
                    t = values[d];
                    values[d] = values[d + 1];
                    values[d + 1] = t;
                }
            }
        }
    }

The part that I'm specifically trying to understand is the second for loop:

    for (d = 0; d < c - n - 1; d++)

I understand that the function is iterating through the array each time, comparing side-by-side values up until the last sorted element and bubbling the biggest element to the end of the array; however, I cannot seem to wrap my head around the meaning of:

    while d < c - n - 1;

and how it translates. When I play this out in my mind I'm imagining that on the first time looping, d < c - n - 1 equates to 0 < 0 - 10 - 1. It seems to me that since c is always going to be less than n - 1, subtracting n - 1 from c will always result in a value less than 0, and d is never less than 0 so should never execute. I know that I'm just looking at this wrong and will probably have a 'duh' moment when the answer is presented, but this is bothering me.

If I put the first for loop into words, it says: while c is less than the length of the array, execute the contents of this loop then increment c. Can someone put the second for loop into words in a similar way, explaining the meaning of d < c - n - 1?

This code doesn't work. Where did it come from? What is the basis for thinking it does work? — , Jun 18 '17 at 07:26
Yes, code doesn't work, because second loop never iterating. I think correct condition in second loop is `d < n - c - 1`. — ivan kuklin, Jun 18 '17 at 07:49

score 0 · Answer 1 · answered Jun 18 '17 at 08:13

First take a look at this QA:

How to debug my Bubble Sort code

where my functional bubble sort C++ implementations can be found with comments included.

Your first loop was supposed to loop the bubble sort each time with one less of array size because last value in array is already sorted from previous run.

So the second loop should go in range <0,n-1-c>. the if statement just selects if the sort is asc or desc and swap element if needed.

Like most of the bubble sorts out there you're forgetting to stop when sort is done (no swap occur during last run)

score 0 · Accepted Answer · answered Jun 18 '17 at 11:15

Try this code instead.

#include<stdio.h>

void sort(int values[], int n)
{
int c,d,t=n;
//if we have n elements then outer loop must iterate for n times.
for(c=0;c<n;c++)
{
    /*after every complete iteration we get a
    sorted element in last position, next iteration
     will be one less, so we assigned value of n into t
     and we will decrease it by 1 after every internal complete iteration.
     */
     for(d=0;d<t-1;d++)
        {
          if(values[d]>values[d+1])
            {
               int temp;
               temp = values[d+1];
               values[d+1] = values[d];
               values[d] = temp;
            }
        }
    //decrease the test cases in next iteration,
    //we already have last element sorted.
    t--;
  }
}
int main()
{
  int i;
  int values[]={24,12,2,4,6};
  sort(values, 5);

   for(i=0; i<5; i++)
     {
        printf("%d\n",values[i]);
     }

return 0;
}

Make Changes according to your need.

score -1 · Answer 3 · answered Jun 18 '17 at 08:12

-1

Don't make simple things complicated and also your code doesn't work try the below code.`

 void sort(int values[], int n);
        {
            int c, d, t;
// since c is intitalised to 0 u can simply use n
        for (c = 0; c < n; c++)
        {
//Assign d = c+1 instead of doing it in next step
           for (d = c+1; d < n; d++)
            {
//It is ascending sort it checks first and second value ,if greater it will swap
                if (values[c] > values[d])
                {
                    t = values[c];
                    values[c] = values[d];
                    values[d] = t;
                }
            }
        }
    }`

answered Jun 18 '17 at 08:12

Prakaash M

37
8

Hmmm Consider the only time `values[0]` is reference is once, the first time `if (values[c] > values[d])` is executed. How would the smallest values get stored in `values[0]`? Even with a simple array of 3,2,1? This "bubbles" the wrong way. – chux - Reinstate Monica Jun 18 '17 at 11:28
Smallest value would be stored in `values[0]` because loop `for (d = c+1; d < n; d++)` find smallest value in range [c; n) of array and place it in `values[c]`. – ivan kuklin Jun 19 '17 at 07:21

Trying to understand bubblesort function

3 Answers3