Sorting array or AssocArrays by value.

[Derek Parnell]

On Sun, 4 May 2008 13:52:42 +0000 (UTC), Me Here wrote:

> Derek Parnell wrote:
>> The trick I use for this is to have two AAs. When the set is small,
>> performance isn't really an issue.
> 
> Problem: That works fine if the values in the origianl array are unique.

Doh! Of course that's an issue. My bad ... just come off playing a couple
of hours of COD4  :-)

I'm still a huge fan of variable-length arrays and AAs ( I also code in the
Euphoria language where V/L arrays are the lifeblood). So here is a better
solution to this sort of problem using those built-in features of D.

import std.stdio;

void main()
{
    uint[int] SampleData;
    
    // NB: Has non-sequential indexes and duplicate values.
    SampleData[ 20] = 30;
    SampleData[  1] = 10;
    SampleData[  2] = 30;
    SampleData[243] = 60;
    SampleData[  4] = 90;
    SampleData[ 75] = 90;
    SampleData[  6] = 120;
    SampleData[ 17] = 50;
    SampleData[ -8] = 20;
    SampleData[  9] = 30;
    SampleData[ 10] = 30;
    SampleData[211] = 10;
    SampleData[-12] = 30;
    SampleData[ 13] = 60;
    SampleData[114] = 90;
    SampleData[315] = 90;
    SampleData[126] = 20;
    SampleData[ 17] = 50;
    SampleData[418] = 20;
    SampleData[ 19] = 30;
    SampleData[120] = 30;
    SampleData[ 21] = 10;
    SampleData[-22] = 30;
    SampleData[223] = 60;
    SampleData[ 24] = 90;
    SampleData[425] = 90;
    SampleData[126] = 20;
    SampleData[-27] = 50;
    SampleData[278] = 20;
    SampleData[292] = 30;

    auto SSD = SortVals(SampleData);
    
   // Publish the results
   writefln("%6s: %s", "Value", "Occurs at ...");
   foreach(i; SSD.keys.sort)
   {
       writef("%6s: ", i);
       auto vals = SSD[i];
       foreach( j, v; vals)
       {
            if (j == vals.length - 1)
            {
                writefln("%s", v);
            }
            else
            {
                writef("%s, ", v);
            }
        }
   }
       
    
}

Kt[][Vt] SortVals(Kt, Vt)(Vt[Kt] theArray)
{
   
    // Reverse index array. 
    // nb: The original keys are stored in a V/L array.
    Kt[][Vt] altArray;
   
    // Setup the reverse index array.
    foreach(i; theArray.keys.sort)
    {
        altArray[ theArray[i] ] ~= i;
    }
   
    return altArray;
}


This produces the output ...

 Value: Occurs at ...
    10: 1, 21, 211
    20: -8, 126, 278, 418
    30: -22, -12, 2, 9, 10, 19, 20, 120, 292
    50: -27, 17
    60: 13, 223, 243
    90: 4, 24, 75, 114, 315, 425
   120: 6
-- 
Derek Parnell
Melbourne, Australia
skype: derek.j.parnell