How do "inner" and "outer" work in this bubble sort code?-CodePudding

I am trying to learn the bubble sort algorithm in a book for C. I can't seem to understand in the code below how int outer and int inner link to which element of the nums array. Like how does inner become nums[0] while outer becomes nums[1] (if I'm correct), then progresses through the loop?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    int ctr, inner, outer, didSwap, temp;
    int nums[10];
    time_t t;

    srand(time(&t));

    for (ctr = 0; ctr < 10; ctr  )
    {
        nums[ctr] = (rand() % 99)   1;
    }

    puts("\n Here is the list before the sort: ");
    for (ctr = 0; ctr < 10; ctr  )
    {
        printf("%i\n", nums[ctr]);
    }

    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;
        }
    }

    puts("\n Here is the list after the sort: ");
    for ( ctr = 0; ctr < 10; ctr  )
    {
        printf("%i\n", nums[ctr]);
    }

    return 0;
}

CodePudding user response：

inner never becomes nums[0]. inner and outer are array indexes, so when inner is 0, nums[inner] is nums[0].

The code that performs the comparison and swapping never does that with inner and outer, it uses nums[inner] and nums[outer].

        if (nums[inner] < nums[outer])
        {
            temp = nums[inner];
            nums[inner] = nums[outer];
            nums[outer] = temp;
            didSwap = 1;
        }

CodePudding user response：

I am trying to learn the bubble sort algorithm in a book for C.

For starters if the presented code is indeed from a book then I advice to stop reading the book because it seems the author of the book is a low-qualified programmer.

The presented method is not the bubble sort method.

It looks like the selection sort method with redundant swaps. And moreover the code contains a serious bug.

For example take an array like

int nums[] = { 0, 9, 8, 7, 6, 5, 4, 3, 2, 1 };

and the array will not be sorted!

What is the inner loop doing?

It travers the array after the current element nums[outer] and if it finds an element nums[inner] that is less than nums[outer] it swaps the elements and sets the flag didSwap to 1 (the flag means that some elements were swapped and the outer loop shall continue its iterations)

        if (nums[inner] < nums[outer])
        {
            temp = nums[inner];
            nums[inner] = nums[outer];
            nums[outer] = temp;
            didSwap = 1;
        }
    }

Otherwise if there are no swaps then the control exits the outer loop

    if (didSwap == 0)
    {
        break;
    }

However the selection sort method must continue its iteration even if for the current nums[outer] there was not found an element nums[inner] less than nums[outer].

Here is a demonstration program that shows that the presented sort method (that is not the bubble sort method) does not work.

#include <stdio.h>

int main( void )
{
    int ctr, inner, outer, didSwap, temp;
    int nums[3] = { 1, 3, 2 };

    for (outer = 0; outer < 2; outer  )
    {
        didSwap = 0;
        for (inner = outer; inner < 3; inner  )
        {
            if (nums[inner] < nums[outer])
            {
                temp = nums[inner];
                nums[inner] = nums[outer];
                nums[outer] = temp;
                didSwap = 1;
            }
        }
        if (didSwap == 0)
        {
            break;
        }
    }

    puts("\n Here is the list after the sort: ");
    for ( ctr = 0; ctr < 3; ctr  )
    {
        printf("%i\n", nums[ctr]);
    }
}

The program output is

 Here is the list after the sort: 
1
3
2

As you can see the array was not sorted.:)