Loop for inside loop for

Asked

Viewed 3,361 times

3

for(pass = 0; pass < size - 1; pass++){
    for(j = 0; j < size - 1; j++){

        if(array[j] > array[j + 1]){
            swap( &array[j], &array[j + 1]);
         }
     }
 }

I put only a piece of code where I have doubt, but the intention is to place in ascending order the numbers of a array size 10. The part I don’t understand is the usefulness of the second loop for, within the loop is external. given the array.

a = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37}

Only one loop would be enough to put in ascending order, but why is it necessary another loop?

the exercise has as comment in this loops the following:

1° loop = loop to control passes
2° loop = loop to control comparisons during each pass.
c array loop for
  • 2

    A loop is not enough. I do not know if you are stating or asking because there is no question mark.

  • the internal loop goes from 0 to 9 right, then exit and increment + 1 in the external loop that goes from 0 to 9 tbm, if only the internal loop that will make 9 attempts is not enough, it is necessary exactly 9 + 9 = 18 attempts to put in ascending order?

  • 1

    There are actually 81 iterations with nested loops.

  • 1

    Not necessarily, if you check that it is already ordered, a simple bool flag of the account of that. The worst case (reverse order) will lead to 81 interaction, because to me it appears to be a Bubble Sort.

  • 2

    Yes, in the worst case. And in the case of the question code, which has neither flag nor break. Regardless of whether or not to execute the swap, it is 81 iterations. This is irrelevant in terms of performance considering the input array of the question, which is small. I hope I’m not confusing Vitor, I’m just trying to clarify :)

  • Sorry, 81 iterations, but ( putting on paper) why I see in only the internal loop the terms getting in order?

Show 1 more comment

1 answer

4


This is more a matter of logic and mathematics.

It even has different ways of doing this, but in this example it needs two loops because the internal only compares one pair at a time and reverses if the second is the smallest, but this does not guarantee exchanges beyond the pair. The external tie will have done again to ensure that it analyses again and brings the smaller ones more and more to the beginning>

Let’s do a table test:

2, 6, 4, 8, 10, 12, 89, 68, 45, 37

Compara 2 e 6 e não faz nada
Compara 6 e 4 e inverte 2, 4, 6, 8, 10, 12, 89, 68, 45, 37
Compara 6 e 8 e não faz nada
Compara 8 e 10 e não faz nada
Compara 10 e 12 e não faz nada
Compara 12 e 89 e não faz nada
Compara 89 e 68 e inverte 2, 4, 6, 8, 10, 12, 68, 89, 45, 37
Compara 89 e 45 e inverte 2, 4, 6, 8, 10, 12, 68, 45, 89, 37
Compara 89 e 37 e inverte 2, 4, 6, 8, 10, 12, 68, 45, 37, 89

Is it ordered? No. It’s improved, but it still needs to order more:

2, 4, 6, 8, 10, 12, 68, 45, 37, 89

Compara 2 e 4 e não faz nada
Compara 4 e 6 e não faz nada
Compara 6 e 8 e não faz nada
Compara 8 e 10 e não faz nada
Compara 10 e 12 e não faz nada
Compara 12 e 68 e não faz nada
Compara 68 e 45 e inverte 2, 4, 6, 8, 10, 12, 45, 68, 37, 89
Compara 68 e 37 e inverte 2, 4, 6, 8, 10, 12, 45, 37, 68, 89
Compara 89 e 37 e inverte 2, 4, 6, 8, 10, 12, 68, 45, 37, 89

Is it ordered? No. It has improved, but it still needs to order more and so it will have to do other times until it is ordered.

It’s not the most efficient, but this code works like this. As already said in comments it is possible to mark when it is already ordered and not to do all steps. Actually it is possible not to do the exchanges where it is already ok. But there is another very different algorithm.

Let’s see how it looks:

#include <stdio.h>

void swap(int *e1, int *e2) {
    int tmp = *e1;
    *e1 = *e2;
    *e2 = tmp;
}

void imprime(int array[], int size) {
    for (int j = 0; j < size; j++) printf("%d, ",array[j]);
     printf("\n");
}
    
int main(void) {
    int array[10] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
    int size = 10;
    for (int pass = 0; pass < size - 1; pass++) {
        for (int j = 0; j < size - 1; j++) {
            if (array[j] > array[j + 1]) swap(&array[j], &array[j + 1]);
            imprime(array, size);
         }
         printf("--- Nova iteração ---\n");
     }
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

Browser other questions tagged c array loop for

You are not signed in. Login or sign up in order to post.