identation

[dmjcunha]

Hi. The code below is exactly as it is in the book Algorithmsin c
third edition. I just would like to know if there was an error of
identation in the compexch.

#typedef int Item
#define key(A) (A)
#define less(A, B) (key(A) < key(B)
#define exch(A, B) {Item t = A; A = B; B = t;}
#define compexch(A, B) if (less(B, A)) exch(A, B)
#define M 10

void quicksort(Item a[], int l, int r)
{int i;
if(r - l <= M) return;
exch(a[(l + r) / 2], a[r - 1]);
compexch(a[l], a[r - 1];
compexch(a[l], a[r]);
compexch(a[r - 1], a[r]);
i = partition(a, l + 1, r - 1);
quicksort(a, l, i - 1)
quicksort(a, i + 1, r);
}

Also if someone could give me a clue of how to make it based on
partitioning on the median of a random sample of five elements and the
elements of the sample do not participate in partitioning instead of a
median of three algorithm I would enjoy because I don't have the
minimum idea of how to make it. I was thinking if the identation was
wrong I should put statements like
ran = rand() % (r - l);
compexch(a[l], a[ran]);

ran = rand() % (r - l);
compexch(a[l + 1], a[ran])

and so on and call
i = partition(a, l + 5, r)
but I really don't know.

 

[John Gordon]

Hi. The code below is exactly as it is in the book Algorithmsin c
third edition. I just would like to know if there was an error of
identation in the compexch.

Indentation makes no difference to the code; it is only for readability.

 

[Ben Pfaff]

Hi. The code below is exactly as it is in the book Algorithmsin c
third edition. I just would like to know if there was an error of
identation in the compexch.

There is silly indentation, but there are plenty of other
problems and questionable practices also. I would not use this
code for anything.

Here are a few problems I noticed quickly. First, there's no
"#typedef" preprocessor directive. Evidently "typedef int Item;"
is what was meant:

#typedef int Item
#define key(A) (A)
#define less(A, B) (key(A) < key(B)

The following macro expands its arguments multiple times and
fails to protect itself with do...while(0):

#define exch(A, B) {Item t = A; A = B; B = t;}
Ditto:
#define compexch(A, B) if (less(B, A)) exch(A, B)

"M" is a pretty lousy name for a macro:

#define M 10

'l' is a lousy name for a variable, especially in a function that
also uses the integer '1':

void quicksort(Item a[], int l, int r)

This indentation style is weird:

{int i;
if(r - l <= M) return;
exch(a[(l + r) / 2], a[r - 1]);

It is very unconventional to indent in the following "stair-step"
way:

compexch(a[l], a[r - 1];
compexch(a[l], a[r]);
compexch(a[r - 1], a[r]);
i = partition(a, l + 1, r - 1);
quicksort(a, l, i - 1)
quicksort(a, i + 1, r);
}

 

[Ike Naar]

#typedef int Item
#define key(A) (A)
#define less(A, B) (key(A) < key(B)

The parentheses don't match.

 

[Stefan Ram]

It is very unconventional to indent in the following "stair-step"
way:

compexch(a[l], a[r - 1];
compexch(a[l], a[r]);
compexch(a[r - 1], a[r]);

It could become more conventional by using blocks:

compexch(a[l], a[r - 1];
{ compexch(a[l], a[r]);
{ compexch(a[r - 1], a[r]); }}

But now, one can comment that it is »very unconventional« to
use blocks as above, since they are redundant.

However, redundant blocks might sometimes be used like
comments, to group or subordinate parts of the source code
for a human reader. But this might not apply, here.

 

[gwowen]

  It could become more conventional by using blocks:

compexch(a[l], a[r - 1];

Are you sure about this?

I've looked in my 2nd (1990) edition and all the sorting algorithms I
see there are just perfomed on int[], rather than some abstract keyed
datatype (which are mentioned only briefly as motivation for the
"Radix Sort" chapter). My guess would be that the macro kludge given
above were a late addition to the 3rd edition, and not tested beyond
"that looks right". (Score +1 for overloading operator< on this one).

The indentation is lot better in the earlier edition, too.

 

[James Kuyper]

� It could become more conventional by using blocks:

compexch(a[l], a[r - 1];

It seems a little peculiar to concentrate on his statement about blocks,
without also retaining the blocks that he was talking about.

Are you sure about this?

Well, the unmatched parenthesis is obviously wrong, but his comment
about using blocks was correct. However, keep in mind that "more
conventional" is also, in this particular case, still "highly
unconventional", and also "not recommended".