Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Sort it with one array and some tmp files

Reply
Thread Tools

Sort it with one array and some tmp files

 
 
jason735@gmail.com
Guest
Posts: n/a
 
      10-29-2006
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

 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      10-29-2006
http://www.velocityreviews.com/forums/(E-Mail 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.

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


 
Reply With Quote
 
 
 
 
Flash Gordon
Guest
Posts: n/a
 
      10-29-2006
(E-Mail Removed) 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.
 
Reply With Quote
 
Walter Roberson
Guest
Posts: n/a
 
      10-29-2006
In article <(E-Mail Removed)>,
CBFalconer <(E-Mail Removed)> wrote:
>(E-Mail 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.
--
Prototypes are supertypes of their clones. -- maplesoft
 
Reply With Quote
 
jason735@gmail.com
Guest
Posts: n/a
 
      10-29-2006

Walter Roberson wrote:
> In article <(E-Mail Removed)>,
> CBFalconer <(E-Mail Removed)> wrote:
> >(E-Mail 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

 
Reply With Quote
 
Julian V. Noble
Guest
Posts: n/a
 
      10-29-2006
(E-Mail Removed) 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Changing dir for tmp files Ed Mullen Firefox 0 03-06-2004 03:52 AM
Ado sort error-Ado Sort -Relate, Compute By, or Sort operations cannot be done on column(s) whose key length is unknown or exceeds 10 KB. Navin ASP General 1 09-09-2003 07:16 AM
TMP files huck Computer Support 1 07-26-2003 07:38 PM
Re: Windows XP TMP Files riz Computer Support 0 07-26-2003 12:02 PM
Re: TMP files Bebop & Rocksteady Computer Support 0 07-25-2003 10:24 AM



Advertisments