Search
sorting associative arrays by value?
Aug 20, 2004
niall
Aug 21, 2004
Ben Hinkle
Aug 21, 2004
Niall FitzGibbon
Aug 21, 2004
Ben Hinkle
```This has probably been asked before, but I couldn't find anything on it in the main documentation.

Basically, I am looking for a way to sort an associative array by value, and not by key. In your wordcount example, you sort the keys and use that to print out the list of words and their frequency. Basically, I want to modify this to order the printout by frequency (obviously I don't just want to do this in the example, but this is just an illustration <g>).

Doing a foreach on array.values.sort gives you the sorted array of values, but without any way that I can see to get the key value for each of those elements. Making a copy of the array and switching the value/keys would work, but only in cases where there were new duplicate values..

Is there something I'm missing in the syntax to achieve this, or would I have to write such a sorting algorithm myself?

```
```niall wrote:

> This has probably been asked before, but I couldn't find anything on it in the main documentation.
>
> Basically, I am looking for a way to sort an associative array by value, and not by key. In your wordcount example, you sort the keys and use that to print out the list of words and their frequency. Basically, I want to modify this to order the printout by frequency (obviously I don't just want to do this in the example, but this is just an illustration <g>).
>
> Doing a foreach on array.values.sort gives you the sorted array of values, but without any way that I can see to get the key value for each of those elements. Making a copy of the array and switching the value/keys would work, but only in cases where there were new duplicate values..
>
> Is there something I'm missing in the syntax to achieve this, or would I have to write such a sorting algorithm myself?
>

One way, with keys of type A and values of type B
B[A] orig;
... fill orig ...
B[] sorted_vals = orig.values.sort;
A[][B] inverse;
foreach(A key, B val; orig) // construct the inverse
inverse[val] ~= key;
foreach(B val; sorted_vals) {
A[] keys_for_val = inverse[val];
... do whatever you want with the keys_for_val ...
}

A more efficient way to do it is to use a SortedAA from MinTL so that you don't have to sort the array of values as a separate step - they get sorted during insertion.

-Ben
```
```Ben Hinkle wrote:
> One way, with keys of type A and values of type B
> B[A] orig;
> ... fill orig ...
> B[] sorted_vals = orig.values.sort;
> A[][B] inverse;
> foreach(A key, B val; orig) // construct the inverse
>   inverse[val] ~= key;
> foreach(B val; sorted_vals) {
>   A[] keys_for_val = inverse[val];
>   ... do whatever you want with the keys_for_val ...
> }

That's a nice solution, I hadn't thought of concatenating the keys for nonunique values :)

>
> A more efficient way to do it is to use a SortedAA from MinTL so that you
> don't have to sort the array of values as a separate step - they get sorted
> during insertion.
>
> -Ben

I think I'll try the MinTL way, since I'm quite a fan of the STL in C++.

I wonder if the D specification in future might extend the sort property
for AAs in order to specify sorting by key or value, since it's quite a common operation to want to do on associative arrays?

Thanks for your help -- I'm only just starting to experiment with D, but I really like how much more logical and intuitive the language is so far  :)
```
```> I wonder if the D specification in future might extend the sort property
>   for AAs in order to specify sorting by key or value, since it's quite
> a common operation to want to do on associative arrays?

Hmm. AA's don't have a sort property. The "keys" property returns a dynamic array of all the keys and you can sort that. Similarly the "values" property returns a dynamic array of values. But those arrays contains copies of the data in the AA - so sorting them will have no effect on the AA.

> Thanks for your help -- I'm only just starting to experiment with D, but I really like how much more logical and intuitive the language is so far :)

me too - hope you enjoy D!
```