Sort it with one array and some tmp files

Discussion in 'C Programming' started by jason735@gmail.com, Oct 29, 2006.

  1. Guest

    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, 2006
    #1
    1. Advertising

  2. CBFalconer Guest

    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>
    CBFalconer, Oct 29, 2006
    #2
    1. Advertising

  3. Flash Gordon Guest

    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.
    Flash Gordon, Oct 29, 2006
    #3
  4. In article <>,
    CBFalconer <> wrote:
    > 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
    Walter Roberson, Oct 29, 2006
    #4
  5. Guest

    Walter Roberson wrote:
    > In article <>,
    > CBFalconer <> wrote:
    > > 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, 2006
    #5
  6. 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
    Julian V. Noble, Oct 29, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jeff
    Replies:
    3
    Views:
    435
    Juan T. Llibre
    Oct 17, 2006
  2. mc
    Replies:
    2
    Views:
    630
  3. Navin
    Replies:
    1
    Views:
    685
    Ken Schaefer
    Sep 9, 2003
  4. Timasmith

    Getting rid of tmp files

    Timasmith, Jan 24, 2007, in forum: Ruby
    Replies:
    1
    Views:
    93
    Eric Hodel
    Jan 24, 2007
  5. Jo Oberman

    Deleting tmp-files of CGI.pm upload()

    Jo Oberman, Nov 30, 2003, in forum: Perl Misc
    Replies:
    8
    Views:
    439
    Randy Kobes
    Dec 1, 2003
Loading...

Share This Page