Sort it with one array and some tmp files

[jason735]

Hi,
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.

Thanks for every clue.

JS

 

[CBFalconer]

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.

 

[Flash Gordon]

Hi,
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.

OK, off you go and do it then.

Thanks for every clue.

Clue 1, this is an algorithms problem not a C problem. We discuss C here
hence the name of the group.

Clue 2, read the text book that goes with the course you are doing. Try
looking in the index under sort.

Clue 3, the normal reason for only reading files forwards is that they
are on a tape.

A more appropriate group would probably be comp.programming, but read
there FAQ before posting there.

 

[Walter Roberson]

(e-mail address removed) 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.

 

[jason735]

(e-mail address removed) 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.
--

Thanks, I moved the topic to comp.programming. Please answer there.
We can write to this file at its end, then rewind it, read it through
in the forward direction, and then again - rewind, write, rewind, read
etc. Let's assume that y is greater then 4. If not enough files, let's
make it 8.
Thanks for response and I'm sorry for posting on comp.lang.c

JS

 

[Julian V. Noble]

Hi,
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.

Thanks for every clue.

JS

If _I_ were faced with this kind of problem I would look in Knuth's
"The Art of Computer Programming". I think it may be vol. I that
you want, "Sorting and Searching" (unless that's v. III ;-)