Re: sorting of records with 0 and 1.



From: "c.lang.mys...@xxxxxxxxx" <c.lang.mys...@xxxxxxxxx>
we have an array of n data records to sort and that the key of
each record has the value 0 and 1.

Are the records variable-length, where each record must be
individually parsed from one end to find where the other end is, or
fixed length, with the length also given as a parameter at the very
start? If variable-length, can they also be parsed in the reverse
direction, or only in one direction not the other? If
variable-length, is there a fixed upper-bound on length of records,
or for different sets of records can the largest record be
arbitrarily large and the algorithm must continue to work just the
same as with short records?

The in place sorting algorithm must be stable and run in o(n) time.

By "in place", do you mean o(1) additional storage allowed, such as
for the algorithm/code itself as well as a fixed number of
fixed-size variables such as counters/pointers? No additional
temporary memory may be allocated?

Note: If lengths of records are unbounded, but size of pointer is
fixed, then you have Mission Impossible, because even a single
record can be larger than the entire address range expressible in
that fixed-size pointer. So you need to carefully consider your
answers to get a consistent set of conditions for stating your
question.
.



Relevant Pages

  • Re: sorting of records with 0 and 1.
    ... Are the records variable-length, ... By "in place", do you mean oadditional storage allowed, such as ... it looks like matesort probably isn't stable. ... The algorithm in the first reference doesn't satisfy the ...
    (comp.programming)
  • Re: variable- key generation
    ... > keys, such as blowfish. ... > 160-bit key via a hashing algorithm such as MD5 or RipeMD ... completely random string of bits for the key, ...
    (sci.crypt)
  • Re: sorting of records with 0 and 1.
    ... Are the records variable-length, ... arbitrarily large and the algorithm must continue to work just the ... fixed-size variables such as counters/pointers? ... that fixed-size pointer. ...
    (comp.programming)
  • variable- key generation
    ... keys from a password for algorithms which can use variable-length ... For example, my implementation of blowfish ... currently requires the user to directly specify the "key" for the ... 160-bit key via a hashing algorithm such as MD5 or RipeMD or Sha-1. ...
    (sci.crypt)