for (gap = n/2; gap > 0; gap /= 2) without a ";" at its end

Question

I read the following codes in "The C programming language edition 2"

/* shellsort: sort v[0] ... v[n-1] into increasing order */
void shellsort(int v[], int n) {
    int gap, i, j, temp;

    for (gap = n/2; gap > 0; gap /= 2) 
        for (i = gap; i < n; i++)
            for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {
                temp = v[j];
                v[j] = v[j+gap];
                v[j+gap] = temp;
            }

}

What confuse me is that there's no ";" at the end of "for loop line", I assume it should be

    for (gap = n/2; gap > 0; gap /= 2) ;
        for (i = gap; i < n; i++);
            for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {
                temp = v[j];
                v[j] = v[j+gap];
                v[j+gap] = temp;
            }

How could I wrap it around intuitively?

A `;` after the `for()` statement means the body of the loop is an _empty statement_. The formatting makes it assume it is a nested for loop but it is not. First the first for loop is completely executed and only then will next for loop start. — Paul Ogilvie, Oct 14 '18 at 13:23
Since no one has said it explicitly: your assumption is wrong, and the book is correct. If you place `;` characters where you propose, the code will no longer perform a shell sort, because the outer loops will run without any body and the inner loop will only run once. — Daniel Pryden, Oct 14 '18 at 13:38
Surely what you are really confused about is that there is no { after the for-statement. Lots of programmers think there should be, even though it isn't necessary. Count yourself part of that group, you wouldn't have asked the question if it were there. — Hans Passant, Oct 14 '18 at 13:41
@HansPassant Yeah, damned braces spammers ... those guys paid by #LOCs. Disgusting! — Swordfish, Oct 14 '18 at 13:44

score 2 · Answer 1 · answered Oct 14 '18 at 13:27

The statement

for (gap = n/2; gap > 0; gap /= 2) ;

is equal to

for (gap = n/2; gap > 0; gap /= 2)
    ;

which is equal to

for (gap = n/2; gap > 0; gap /= 2)
{
}

In other words, that's an empty loop that does nothing except the comparison gap > 0 and gap /= 2 (part of the loop) each iteration.

score 1 · Answer 2 · answered Oct 14 '18 at 13:24

The for loop runs the next statement in the code the appropriate number of times. Often this statement is a single statement, or a group of statements in curly brackets. If you put a semicolon instead, it's treated as a null statement, and so "nothing" is done the appropriate number of times.

If you explain what you mean when you say "How could I wrap it around intuitively?" that might make it easier to answer your question.

score 1 · Accepted Answer · answered Oct 14 '18 at 13:27

The syntax of the for loop is (simplified for clarity):

for ( ... ) <statement>

statement:
     ';'  // empty statement
      <any other statement>
     '{' ... '}'  // block of statements

So following the for statement comes one statement or a block of statement. And a single ; is a statement, namely the empty (do nothing) statement. So

for (....) ;
    for (....) ;

is not a nested for-loop. It is equivalent to:

for (....) ;
for (....) ;

or

for (....) {}
for (....) {}

for (gap = n/2; gap > 0; gap /= 2) without a ";" at its end

3 Answers3