argsort

####################### 
###    argsort()    ### 
####################### 
 
often, you want the index list of the sorted list, as opposed to the sorted list itself. 
 
implementation is trivial. you just maintain the index list along with your data list. 
and keep track of the index of each data being shuffled. 
 
e.g. 
 
-------------------------------------------------// argsort.pl 
#!/usr/bin/perl 
 
use strict; 
 
my @arr = (12, 56, 34, 78, -40, 9); 
 
sub argsort { 
   my @data = @_; 
   my @idxArr; 
   my $size = scalar(@data); 
   my $i; 
   my $k; 
   for($i = 0; $i < $size; $i++){ 
      @idxArr[$i] = $i; 
   } 
   for($i = 0; $i < $size; $i++){ 
      for($k = $i+1; $k < $size; $k++){ 
         if($data[$i] > $data[$k]){ 
            $data[$i] = $data[$k] + $data[$i];    # this bit is just swapping 
            $data[$k] = $data[$i] - $data[$k]; 
            $data[$i] = $data[$i] - $data[$k]; 
            $idxArr[$i] = $idxArr[$k] + $idxArr[$i]; 
            $idxArr[$k] = $idxArr[$i] - $idxArr[$k]; 
            $idxArr[$i] = $idxArr[$i] - $idxArr[$k]; 
         } 
      } 
   } 
   return @idxArr; 

 
print "argsort: ".join(" ", &argsort(@arr))."\n"; 
print "sorted list: "; 
print map {$arr[$_]." "} &argsort(@arr); 
print "\n"; 
 
exit 0; 
------------------------------------------------- 
 
 
$ perl argsort.pl 
argsort: 4 5 0 2 1 3 
sorted list: -40 9 12 34 56 78 
 
 
 
note: python has numpy.argsort(), and q/kdb has iasc[] 
 
 
## 
##  complexity 
## 
 
it just follows whatever the underlying sort algo gives. 
the question is can argsort be done using non-comparison based sort algo ? 

  1. 2018-10-31 19:33:13 |
  2. Category : algo
  3. Page View:

Google Ads