ECE318 Special Reading Assignment 2025
This document is how quicksort was first presented to the world.
When I give a page number, it is the page within the pdf document, not as printed in the paper.
You only need to read as much of the document to be able to answer the questions below.
Naturally you'll have to quickly look thrugh the whole thing to see where the necessary parts are.
Make sure you understand the "Estimate of time taken" section, starting on page 2 and ending at the end of page 3.
I have added on the last page a photograph of the computer that was used for the experiments in this paper.
It might be of interest in conjunction with the timings reported on page 4.
On the next-to-last page is the actual implementation, with a little explanation after the questions.
Questions:
- When the author talks about pointers, they are not pointers in the modern sense. What are they really?
- With totally different words, phrasing, and style explain why NlogN is the best possible time for sorting.
- The author describes something he calls a "nest". What is a Nest? What is it doing?
What would we call it today? What would we use instead?
- Comparing the explanation of the use of nests with the actual implementation, what stands out as strange?
Answer those three questions and submit your answers as assignment number 6 on blackboard.
About the implementation. It is in a language called Algol-60. Algo for Algorithmic, L for language, 60 for
the year it was designed, 1960. It remained in common use for 20 years, and was the first structured
programming language I ever used.
Some things about it will not be entirely obvious. I'll outline them here.
Procedures:
A "procedure" is what we would call a void function. In a procedure definition the word "procedure"
is followed by its name and its parameters, names only, in parentheses. After that, the details of the
parameters are given. We are used to putting that inside the parentheses with the parameter names,
but sometimes that gets complicated and hard to read. Originally C followed the Algol pattern.
The statements of the procedure start at the word "begin".
Parameters:
If you don't say otherwise, parameters are passed by a weird method called "call by name",
it is sort of like a reference parameter in C++, but much more complicated. The other alternative
is "call by value", which is exactly the same as ordinary parameters in C++. The statement "value M, N;"
specifies that M and N are call by value, so A, I, and J are by name.
Also if you don't say otherwise, parameters are assumed to
be of type "real" which is what we would call
a float or a double. This means that A is an array of reals,
and I, J, M, and N are ints.
For array parameters you don't say the size or even the number
of dimensions, that is all
handled for you. The partition function could be given a three dimensional
array, but then the first
access to it would get a run-time error because it only provides one index.
Comments:
comments start with the word "comment" and continue until the
next semicolon. This caused some
very strange errors.
Blocks:
"begin" and "end" are exactly { and } in C++ and most others. Spelling things out reduces errors, and
keyboards in the 1960s never had curly brackets anyway.
Variables:
After the first "begin", "real X" and "integer F" are ordinary
local variable declarations.
Assignments:
":=" is the symbol for assignment, = is only used as a comparison.
Loops:
The only kind of loop was the "for" loop.
"for I := I step 1 until N do ..." is the first loop,
it would be to us "I = I; while (I <= N) { ...; I += 1 }, the
I := I just means we want the loop to
start with I at it's current value. "step" tells us the increment,
if the increment is positive the
while condition is <=, if it is negative the condition is >=.
Go to:
No good programmer ever uses goto statements in structured
programming languages any more,
but back then they didn't know better. In this procedure, "go to" is
always followed by a name, and
that name will always appear, followed by a colon :, somewhere in the
same procedure. "go to" means
exactly what its name suggests. Just jump immendiately to that label's :
position. You can jump out of
loops or anything, it just doesn't matter.
Exchange(a, b):
exchange is the swap function, the author didn't bother to
give its definition because it is
trivial and obvious.
End partition:
the "end" that marks the end of a procedure may be followed
by the procedure's name. This
makes it easy to fix the problem of {'s and }'s not mathcing properly.
I think that covers everything.