By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,025 Members | 2,118 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,025 IT Pros & Developers. It's quick & easy.

Sort it with one array and some tmp files

P: n/a
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

Oct 29 '06 #1
Share this Question
Share on Google+
5 Replies


P: n/a
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.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
Oct 29 '06 #2

P: n/a
ja******@gmail.com wrote:
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.
--
Flash Gordon.
Oct 29 '06 #3

P: n/a
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
Oct 29 '06 #4

P: n/a

Walter Roberson wrote:
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.
--
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

Oct 29 '06 #5

P: n/a
ja******@gmail.com wrote:
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 ;-)

--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia
Oct 29 '06 #6

This discussion thread is closed

Replies have been disabled for this discussion.