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