Re: Ranking Without Sorting

From: Richard Harter (cri_at_tiac.net)
Date: 07/26/04 

Date: Mon, 26 Jul 2004 18:42:49 GMT

On Mon, 26 Jul 2004 05:06:10 -0700, "Ricardo Gibert"
<nospamgibert@cox.net> wrote:

>
[snip code]

Congratulations, you have just reinvented the rank sort. Knuth
doesn't index it, although it may be buried somewhere in the problem
sets. It's mostly used in parallel processing AFAIK.
  
>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).
>
>The indices point to the corresponding element in the original array. They are not the same as the rank information I'm after. To
>make this work, you must maintain a counter (initialized to zero) where its value is stored into the rank array just before
>incrementing it with each DeleteMin operation. The indices you wanted to store into the rank array actually get discarded one at a
>time with each DeleteMin operation.
>
>At no time during your adaptation of heap sort will the array actually get sorted, e.g. to find the i-th element of a[], you will
>need O(n) operations to find it in the rank array rather than O(1) operations if a[] were really sorted.

This is incorrect. (I'm not sure where your confusion is so bear with
me.) In Ian's scheme there are two auxillary arrays involved along
with the data array. Let the data array be a[], the array of indices
be x[], and the array of ranks be r[]. No data is moved in a[]. x[]
is an array of indices. During the heapsort it is rearranged so that
the successive indices in x[] correspond to a sort of a[]. Since a
heap sort produces the sorted elements one at a time, one can fill in
the rank array r[] one element at a time. The cost of filling in the
rank array is O(1) per item or O(n) total.

By the way, can you do something about the line lengths in your
posting? They are much too long.

 
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Whoever said money can't buy happiness
didn't know where to shop.

Relevant Pages

  • Re: Ranking Without Sorting
    ... >> contradicted in my first post where I gave an example of how to rank ... > It seems quite clear to me that your 'ranking' array contains the exact ... The ranking array is completed from left to right as it might in a selection sort and unlike insertion sort. ...
    (comp.programming)
  • Re: Is it possible to mix up a list of numbers
    ... Sort is hard-wired to use the first element of each Row, ... To sort a 2-dim array on something else, you supply Sort with a custom ... One technique is to use Ordering, similar in concept to Excel’s Rank. ... Anyway, I was curious to use Excel vba and Rank at the time, and wanted to ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Ranking Without Sorting
    ... >> contradicted in my first post where I gave an example of how to rank ... > It seems quite clear to me that your 'ranking' array contains the exact ... An unsorted array contains the same information as the same array after sorting. ... > the same operation as the insertion loop in insertion sort... ...
    (comp.programming)
  • Re: "Sorting" assignment
    ... And many others prefer to call partition exchange because "quicksort" ... bin B depending on whether it is greater than, ... If the array is already sorted, this means that you end up ... attempt to sort them. ...
    (comp.programming)
  • 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)