Facing a difficulty in a bubble sort algorithm in C

Question

First of all I am beginner in C, so I am sorry if my question seems stupid. I was learning how to use the bubble sort algorithm in C, and I came through this code :

#include <stdio.h>

int main() {
    int ctr, inner, outer, didSwap, temp;
    int nums[10] = {
        78,
        16,
        21,
        7,
        13,
        9,
        22,
        52,
        67,
        19
    };

    //Listing the array before sorting

    for (ctr = 0; ctr < 10; ctr++) {
        printf("%d\n", nums[ctr]);
    }

    //Sorting the arrays

    for (outer = 0; outer < 9; outer++) {
        didSwap = 0;
        for (inner = outer; inner < 10; inner++) {
            if (nums[inner] < nums[outer]) {
                temp = nums[inner];
                nums[inner] = nums[outer];
                nums[outer] = temp;
                didSwap = 1;
            }
        }
        if (didSwap == 0) {
            break;
        }
    }

    //Listing the array after sorting

    printf("\n\nThis is the sorted array\n");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%d\n", nums[ctr]);
    }

    return 0;
}

The code works fine, but what I want to understand is how in the second for loop it is written inner = outer, and in the next if statement it is comparing the elements of the array were one of them has the same number as inner and the other has the same number as outer. And since we said that inner = outer, that means that we are comparing the same element. The way I think about it is, if outer = 0, and since inner = outer, then inner will be 0 too, so the next if statement will be if (nums[0] < nums[0]) and that doesn't make any sense.

I know that I am probably wrong about it because the code works fine, but what did I think wrong?

Thanks in advance.

Answer 1

The essence of your Bubble Sort is that on each scan the "bubble" is the largest value seen so far, so at the end of the scan, the largest value has "bubbled" to the top. Then you repeat from the beginning, but each time around (clearly) you have one less value you need to consider. Also, if at the end of a scan, nothing moved, then everything is in order and you can stop.

So the Bubble Sort might look like this:

    for (int n = 10 ; n > 0 ; n--)
      {
        bool no_swaps ;

        no_swaps = true ;
        for (int i = 1 ; i < n ; ++i)
          {
            if (nums[i-1] > nums[i])
              {
                int temp ;
                temp = nums[i-1];
                nums[i-1] = nums[i];
                nums[i]   = temp;
                no_swaps = false ;
              } ;
          } ;

        if (no_swaps)
          break ;
      } ;

Or:

    for (int n = 10 ; n > 0 ; n--)
      {
        bool no_swaps ;
        int bubb ;

        no_swaps = true ;
        bubb = nums[0] ;
        for (int i = 1 ; i < n ; ++i)
          {
            int this ;

            this = nums[i] ;
            if (bubb <= this)
              bubb = this ;
            else
              {
                nums[i-1] = this ;
                nums[i]   = bubb ;
                no_swaps = false;
              } ;
          } ;

        if (no_swaps)
          break ;
      } ;

which, perhaps, makes it clearer that the eponymous "bubble" (bubb) is the largest value found in the current scan (or the rightmost largest, if have seen 2 or more with that value).

If you remove the didSwap from your sort, it will work fine. Like Bubble Sort, each pass of your sort moves one item to its final destination. Your sort always does (n-1)*(n-2)/2 comparisons, which is the same as the worst case for Bubble Sort. But the Bubble Sort best case is (n-1) -- if the values are already in order !

So a real Bubble Sort has an edge over your sort. Nevertheless, Bubble Sort is also generally O(n^2) and, therefore, about as useful as a chocolate teapot except when n is small.

Answer 2

It is not stupid question. You successfully spotted an inefficiency. The inner loop first iteration is indeed pointless, but it won't cause any trouble. The right way would be to start it from outer + 1 instead of outer.