Re: New technology, old idea.... why not?

TheBigPJ wrote:
[...]
Question
- Are we there then on sorting data? At the end? Or just very close
to it?

A lot depends on how you formulate the problem. If you
sort using pairwise comparisons and you have no exploitable
prior knowledge of the existing arrangement, then it's not
hard to show that the problem is O(N log N). These are the
assumptions usually made for "general-purpose" sorting, and
one can see why: in Java, it means you can sort anything
that implements Comparable or for which you can build a
Comparator, so the sorting methods don't need information
about the nature of the objects being sorted.

But "special-purpose" sorting is another matter! For
example, if you know that the original sequence is in order
except for possibly one pair of adjacent items, the problem
shrinks down to O(N). Or if you have a way to determine the
order of items without comparing them -- that's what your
method does, more or less -- you may be able to get to an
O(N) sort.

There's even an O(1) sort, which I've always seen explained
in terms of pasta. You've got many pieces of uncooked spaghetti,
and you want to sort them by length. So you pick 'em all up in
a bundle, hold it vertically, and slam one end down on the
counter. Lo! The tallest strand now stands higher than all
the others, and the shortest strand stands lower, and so on
for all the in-betweens. They're "sorted" in just one step,
and with zero comparisons! (Of course, the task of picking
out the strands in sorted order still lies ahead ...)

Finally, big-Oh is not the end of the tale. If I offer
you several O(N logN) sorting methods, would you be expect them
all to take the same amount of time on the same inputs? If you
do, you don't understand big-Oh!

--
Eric.Sosman@xxxxxxx
.

Relevant Pages

  • Re: A Fast sorting algorithm for almost sorted data
    ... far my compressor has potential but is nowhere near ready. ... It does however make heavy use of sorting. ... which I am currently calling Run sort. ... entire selected run can be added to the sorted output array. ...
    (comp.compression)
  • Re: Solution for sorting an array alpha-numerically
    ... strings up into groups and sorting the groups seperately, ... > so that numeric and alphabetic data sort as seperate groups. ... To the same project as the web page, add the class AlphaNumCompare() ...
    (microsoft.public.dotnet.general)
  • Re: how fast can I sort on mainframe (using DFSORT)?
    ... Since I joined the team as the performance lead a couple years ago, ... Frank now defers these types of questions to me. ... I have been out of the sorting business for a while, ... Writing to sort work files should not be the problem, ...
    (bit.listserv.ibm-main)
  • Re: When random isnt random
    ... >> (and, if there is not one already, a Sorting Unit). ... TList has a Sort method. ... Try it with a TList and in the compare function ... There seems to be, sometimes, a requirement for a Shuffle that leaves ...
    (borland.public.delphi.language.objectpascal)
  • Re: except tasks from sorting
    ... position out of any sort key. ... But we will sorting subsequently. ... sort key is a Text ... hint to filtering the tasks before ...
    (microsoft.public.project)