Bug in quicksort example (K&R C book)?

Question

This quicksort is supposed to sort "v[left]...v[right] into increasing order"; copied (without comments) from The C Programming Language by K&R (Second Edition):

void qsort(int v[], int left, int right)
{
    int i, last;
    void swap(int v[], int i, int j);

    if (left >= right)
        return;
    swap(v, left, (left + right) / 2);
    last = left;
    for (i = left+1; i <= right; i++)
        if (v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

I think there's a bug at

(left + right) / 2

Suppose left = INT_MAX - 1 and right = INT_MAX. Wouldn't this result in undefined behavior due to integer overflow?

It was probably programmed with the assumption that an array wouldn't be that large at runtime. :) — sarnold, Jun 26 '11 at 21:49
That's a very good assumption since you wouldn't have space in memory for your quicksort program — Karoly Horvath, Jun 26 '11 at 21:50
See also: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html — Pascal Cuoq, Jun 26 '11 at 22:24
@functionptr can you please answer this question? http://stackoverflow.com/questions/24534487/quick-sort-programmed-in-c — HELP PLZ, Jul 02 '14 at 15:52

score 7 · Accepted Answer · answered Jun 26 '11 at 21:47

7

Yes, you're right. You can use left - (left - right) / 2 to avoid overflows.

answered Jun 26 '11 at 21:47

Artefact2

7,516
3
30
38

@Jerry / Paul: Which, since `(right - left) == - (left - right)`, is the same as this answer's formulation. – caf Jun 26 '11 at 22:39
@caf: Ah, I hadn't thought of it that way, but you're right. I rescind my original comment, and apologize for being obtuse. – Jerry Coffin Jun 26 '11 at 22:52

score 2 · Answer 2 · answered Jun 26 '11 at 21:47

2

You aren't imagining an array with INT_MAX number of elements, are you?

answered Jun 26 '11 at 21:47

Armen Tsirunyan

130,161
59
324
434

2

That's just under 8 gigabytes of address space, assuming 32-bit integers. More than doable on modern hardware. :) – sarnold Jun 26 '11 at 21:51
2

We would probably have to excuse K&R for not considering memory growing from kB to GB. And "640k should be enough for everyone"? – Bo Persson Jun 26 '11 at 22:17
@Bo there are platforms with 16-bit `int`s, you know, and I'm pretty sure some of them have more than 64Kb of memory. `int` != `intptr_t`. – Karl Knechtel Jun 27 '11 at 01:05

score 1 · Answer 3 · answered Jun 26 '11 at 21:49

1

Yes, you're right, although it's possibly just written that way for simplicity -- it's an example after all, not production code.

answered Jun 26 '11 at 21:49

Peter Alexander

53,344
14
119
168

score 1 · Answer 4 · answered Jun 26 '11 at 22:30

1

K&R was always a bit sloppy with their use of unsigned vs signed arguments. Side effect of working with a PDP that had only 16 kilobytes of memory I suppose. That's been fixed a while ago. The current definition of qsort is

void qsort(
   void *base,
   size_t num,
   size_t width,
   int (__cdecl *compare )(const void *, const void *) 
);

Note the use of size_t instead of int. And of course void* base since you don't know what kind of type you are sorting.

answered Jun 26 '11 at 22:30

Hans Passant

922,412
146
1,693
2,536

1

The `__cdecl` wart isn't a part of the standard definition. – caf Jun 26 '11 at 22:50
I'm sure that's true, they probably had only *one* calling convention back then. And a lot less keywords that started with *two* underscores. Leave it up to the vendors to make it complicated. Necessarily so, the standard kinda sux. – Hans Passant Jun 26 '11 at 22:54

Bug in quicksort example (K&R C book)?

4 Answers4

Linked