Re: Ranking Without Sorting

From: Ricardo Gibert (nospamgibert_at_cox.net)
Date: 07/26/04 

Date: Sun, 25 Jul 2004 17:11:47 -0700

"Ian Woods" <newspub2@wuggyNOCAPS.org> wrote in message news:Xns95322E55BBA1newspubwuggyorg@217.32.252.50...
> "Ricardo Gibert" <nospamgibert@cox.net> wrote in
> news:MiSMc.9292$_K2.2901@lakeread02:
>
> >
> > "Ian Woods" <newspub2@wuggyNOCAPS.org> wrote in message
> > news:Xns953174E5CEE2Anewspubwuggyorg@217.32.252.50...
> >> doublea987@aol.com (Aarlo Stone Fish) wrote in
> >> news:c6894599.0407242216.bb0eee9@posting.google.com:
> >>
> >> > "Ricardo Gibert" <nospamgibert@cox.net> wrote in message
> >> > news:<tBDMc.9150$_K2.7568@lakeread02>...
> >> >> I was thinking about how one could rank the elements of an array
> >> >> without sorting the elements of the array. It's a simple program
> >> >> to do this in O(n*n), but my question is how can this be done
> >> >> better than this without sorting?
> >> >
> >> > Kind of an interesting question, how to rank things without
> >> > sorting...How about something like a bucket procedure (or a bucket
> >> > "sort," if you will), where you have an array "m" with 256 indices
> >> > (or whatever the range is of things you want to sort in array "a")
> >> > and for every index "i" into array "a", m[a[i]] = i? And then it's
> >> > O(n + p)--you have to go through array "a" to put things in their
> >> > places in array "m" and then go through array "m" to see which
> >> > elements of "a" are used... On second thought, this assumes that
> >> > all values are unique, but I guess you could use some kind of
> >> > recovery feature. So it begins to sound like a sorting issue.
> >> >
> >> > Aarlo Stone Fish
> >>
> >> It apparently must turn into a sorting issue: no matter what you do,
> >> at some point you want to use an ordering of the original array...
> >> and that's precisely what sorting provides.
> >
> > "It apparently must turn into a sorting issue...," was already
> > contradicted in my first post where I gave an example of how to rank
> > without sorting.
> >
> > ...
>
> It seems quite clear to me that your 'ranking' array contains the exact
> same information as a sorted array of references, and that your O(n*n)
> algorithm is actually performing an operation practically identical to an
> insertion sort on this information.

An unsorted array contains the same information as the same array after sorting. It just takes longer to determine what the i-th
element is.

Similarly, an unsorted array paired with a ranking array contains the same information as the same array after sorting. Again, it
just takes longer to determine what the i-th element is.

In summary, I don't know why think pointing out that they contain the same information is meaningful and implies ranking is the same
as sorting. Just saying so does not make it so.

In any case, you're intelligent enough to know what I'm after. Playing semantic games isn't interesting.

>
> If you don't believe me, list the numbers by their rank at each stage in
> the operation. You'll find that the outer 'i' loop condition has the same
> pre- and post-conditions as insertion sort, and the inner 'j' loop does
> the same operation as the insertion loop in insertion sort... albeit in a
> slightly different manner.
>
> You have, to my mind at least, done an insertion sort on an array encoded
> in a different manner to what 'normal' sorting does (the actual arrays).
>
> AFAICS, no matter what you do, no matter how you represent the sorted
> data, you're almost certainly going to perform a sort. You might as well
> pick a good sorting technique which easilly allows you to produce the
> 'rank' array you want.
>
> Doing a 'heap sort', for example, where the heap holds the index into
> your original array. When you're removing elements from the heap
> (DeleteMin operation), put the indices into your rank array in the order
> they come out. Running time? O(n log n).
>
> Ian Woods
>
> --
> There is no sig.
>

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: Ranking Without Sorting
    ... you have just reinvented the rank sort. ... >> 'rank' array you want. ... >> Doing a 'heap sort', for example, where the heap holds the index into ...
    (comp.programming)
  • Re: Sorting routine
    ... n RSHIFT shifts n bits. ... in the output array. ... This would be handy for sign sorting of 2's complement. ... So Radix/Distribution sort is about 1.4 times faster than Sedge's Sort. ...
    (comp.lang.forth)
  • Re: Efficiently Extracting Identical Values From A List/Array
    ... struct SortHelper ... Now sort that array according to NodeIndex: ... running through the data structure and sorting things out. ...
    (comp.lang.cpp)
  • Re: Dynamic Comma delimited output
    ... SELECT CustomerID, CONCAT_AGGOVER as ... SELECT OrderID, RANK() OVER as R ... found without sorting, so I think I'm still on track, but let me think ... >>gave without a sort. ...
    (microsoft.public.sqlserver.programming)