1

I just started Programming Pearls and have already gotten bent out of shape over the first question in Column 1. The problem is to sort a file with up to 10 million 7 digit elements without memory constraints. The solution is as follows:

int intcomp(int *x, int *y)
{  return *x - *y; }
int a[1000000];
int main(void)
{  int i, n=0;
   while (scanf("%d", &a[n]) != EOF)
     n++;
   qsort(a, n, sizeof(int), intcomp);
   for (i=0; i < n; i++)
     printf("%d\n", a[i]);
   return 0;
 }

My questions is, why is the integer array a only initialized to store a million, and not ten million? In the bitmap solution in section 1.4, we use a 10 million bit bitmap. Won't we run into unallocated memory space?

thank you!

2
  • 2
    Most likely it is a simple typo in the book and they meant to create a as an array of 10 million elements. Jul 13, 2016 at 9:06
  • The author specifically warns that his solutions provide little to no error checking because he is focusing on the actual workings of the solutions.
    – Guzzi2
    May 19, 2017 at 5:28

1 Answer 1

3

It's important to remember that the point of the chapter (and the book) was how to deconstruct the problem to find a solution optimized for its constraints, not how to sort arbitrary data. As such, the example using qsort is a throwaway.

However, it's very poorly written, even from the perspective of the 1970s; I'm guessing the task was handed to one of Bentley's students. Here are a few of the issues:

  • Wrong size of the array. This could have been solved by using a constant. Although see below.
  • Mixing of concerns: reading, sorting, and writing are three different things, and should be handled by three different functions. OK, this is 21st century dogma, so maybe Bentley or his student can be forgiven. It still hides the core qsort in a lot of superfluous reading and writing.
  • The comparison function will be invalid for combinations of the minimum and maximum integers. A correct comparison must pay attention to the carry bit. You might argue that the text applies a constraint of "positive integers," but in that case the function should be named posintc (I'm keeping to 7 characters because I recall this as an early *nix linker requirement; a modern programmer should use the much longer but more descriptive compare_positive_ints_by_ref).
  • No bounds-checking: the reader reads until end of file, and if you give it more than 1,000,000 entries will happily overrun the buffer. This is IMO the biggest problem.

That said, you're also injecting your own requirements. Here's the problem statement, from page 7 of the 2nd edition, 20th printing:

If memory were not scarce, how would you implement a sort in a language with libraries for representing and sorting sets?

True, the text talks about a larger file. But that's not explicitly mentioned in the problem. And IMO programmers adding what they think are requirements is a huge problem with our industry.

3
  • I see, thank you for the thorough answer! So I was mis-reading that problem as an extension/modification of the original problem, and I was mistaken to do so. In trying to solve the rest of the problems, should I also treat them as individual problems and not an extension of the problem presented in the book? Jul 13, 2016 at 16:04
  • "OK, this is 21st century dogma, so maybe Bentley or his student can be forgiven.": I don't think so: procedural or functional decomposition was well-known at the time.
    – Giorgio
    Oct 9, 2016 at 19:00
  • 1
    +1 for that last paragraph
    – mcottle
    May 19, 2017 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.