CODEWITHSUNDEEP
cfor-looppointersbubble-sort
bman
bman

Reputation: 19

Confused about by this nested for loop

Why does this for loop print / sort all 10 integers. It starts off with i = N - 1 which is greater than or equal to 0 so it goes on to the next for loop. Here J is 1 which is less than or equal to i so it compiles.

The issue i'm having is that the first iteration would be i=9 and j = 1, 8 and 2, 7 and 3, 6 and 4, 5 and 5 and finally 4 and 6 (stopping point),

where j is not less than or equal to i. Shouldn't it only compile for the amount of times that it runs so 5 times instead of the 10 that it does. 

#include <stdio.h>

int arr[10] = { 3,6,1,2,3,8,4,1,7,2};

void bubble(int a[], int N);

int main(void)
{
    int i;
    putchar('\n');
    for (i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    bubble(arr,10);
    putchar('\n');

    for (i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

void bubble(int a[], int N)
{
    int i, j, t;
    for (i = N-1; i >= 0; i--)
    {
        for (j = 1; j <= i; j++)
        {
            if (a[j-1] > a[j])
            {
                t = a[j-1];
                a[j-1] = a[j];
                a[j] = t;
            }
        }
    }
}

The specific code that i'm not wrapping my head around is 

for (i = N-1; i >= 0; i--)
{
    for (j = 1; j <= i; j++)
    {
        if (a[j-1] > a[j])
        {
            t = a[j-1];
            a[j-1] = a[j];
            a[j] = t;
        }
    }
}

The result is correct and returns the correct array of sorted intergers

Upvotes: 0

Views: 71

Answers (2)

Meet Maheshwari
Meet Maheshwari

Reputation: 140

In the code, you see the inner loop is always iterating one time less than before.

This is because in bubble sort, at end of each iteration, the maximum element in 0 to (N - i)th array (where N = size of array and i is the iteration number considering it varies from 1 to N) is put to its actual position

Lets take an example of array A = {2, 5, 6, 1, 9, 8}

After 1st iteration A = {2, 5, 1, 6, 8, 9}

After 2nd iteration A = {2, 1, 5, 6, 8, 9}

After 3rd iteration A = {1, 2, 5, 6, 8, 9}

After 4th iteration A = {1, 2, 5, 6, 8, 9}

After 5th iteration A = {1, 2, 5, 6, 8, 9}

As you can see, after 1st iteration, 9 - the highest element, is at its correct position Similarly in 2nd iteration 8 is, in 3rd iteration 6 is and so on.

Hope it was helpful.

Upvotes: 0

Matija8
Matija8

Reputation: 36

The 2 loops are nested. The behaviour is that for each iteration of the outer loop, the full inner loop runs. That means that for a fixed i, j takes values from 1 to i:

i = 9, j = 1;
i = 9, j = 2;
i = 9, j = 3;
...
i = 9, j = 9;

Now the execution finishes on the inner loop and goes back to the outer, decrementing i.

i = 8, j = 1;
i = 8, j = 2;
...
i = 8, j = 8;

i = 7, j = 1;
...
i = 7, j = 7

i = 6, j = 1
...
i = 6, j = 6

This goes on until you get to i = 1, j = 1. Regarding the bubble sort I think you can find some nice visualisations online, something like https://www.youtube.com/watch?v=67k3I2GxTH8

Upvotes: 1

Related Questions