In article <45***************@yahoo.com>,
CBFalconer <cb********@maineline.netwrote:
>ja******@gmail.com wrote:
>I've got the following problem. I have to sort x*y elements which
are in one file. I can use only an array for x elements and
floor[y/4] tmp files which can be read only forward.
>Arrange the array to be a heap. Read in and heapify the first x
elements, and dump the heap (see heapsort). Repeat until 4x have
been processed. Read any remainder into the heap. Now read back
the 4 tmp files element by element (they will be sorted) and
mergesort them (and the extra data in the x array, which is
effectively a 5th temp file) and write the elements out one by one.
I don't think that will solve his assignment / exam / interview
question.
The process you describe will handle at most 5*x elements, but
he needs to be able to handle y*x elements. He is not restricted
to 4 tmp files, he is restricted to floor[y/4] tmp files, each
of indefinite size but each of which "can be read only forward".
Also, your mergesort would require at least 5 variables (one
per temp file and one for the remaining data in the array), but
the problem specification says "I can use only an array for x elements"
together with the temp files, and that could be interpreted as
indicating that those temporary variables for the mergesort are not
allowed unless they are part of that array whose total fixed
length is x (in which case at most 5*x-5 elements could be sorted.)
I'm not sure what "can be read only forward" means --
it -might- mean that each is permitted only a sequential write at
end of file, then a single rewind, then a single read through in
the forward direction. But it maybe random access writes are
acceptable as long as there is never a read of an element earlier
than one that has already been read later in the file. On the
other hand, the problem statement doesn't say that the files can't
be reused any number of times -- write data, rewind, read forward,
rewind, now you can write data again... Indeed, though I don't have
a solid algorithm in mind, I believe that the key would be to reuse
the tmp files. (Hmmm, the shadow of an algorithm I had in mind
wouldn't work with less than 2 tmp files, but if y is 2 or 3 then
*no* tmp files are allowed; if y is 1 then just sort into the array
since y*x = 1*x = x...)
Hmmm, is that even possible, to sort 2*x or 3*x elements using
only a single array of length x and no temporary files? I don't
think it is. Imagine that the inputs are exactly in reverse order,
then the first thing output must be the last thing input, but that
requires temporary storage of 2*x or 3*x pieces of information
into an array that can only hold x pieces of information. By the
Pigeon Hole Principle, this is impossible.
So, the problem is impossible to solve.
Possibly the problem would be solvable if ceiling[y/4] tmp files
were allowed instead of floor[y/4], but that would depend on
what the part about read only forward means.
--
Prototypes are supertypes of their clones. -- maplesoft
