ソートソーターソーテスト

ソートを考えてみる。

C:


#include <stdlib .h>
void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)); 


まあ、以上だな。最後の引数で比較関数へのポインタを渡してあげれば(人間)万事(塞翁が馬)OKだ。

C++:


#include <algorithm>
void std::sort(RanIt first, RanIt last, BinPred pr); 

まあ、STL使いましょうやってことでな。最後のprはなくてもいいが、比較関数を自分で用意する場合に渡してあげれば(人間)(略)。
たとえばvectorをソートするには下記のようにする。


#include <algorithm>
struct cmp { 
   bool operator()(int a, int b) const { 
      return b > a; // 昇順ソート 
      // return a > b; 降順ソート 
   } 
};

int main() { 
   std::vector< int > a; 
   a.push_back(10); 
   a.push_back(2); 
   a.push_back(5); 

   std::sort(a.begin(), a.end(), cmp()); 
   for(int i = 0; i < a.size(); i++) { 
      printf("%d\n",a[i]); 
   } 
} 

なんかしらんが、operator()をオーバーロードしたクラスを作ってインスタンスをstd::sortに渡せばいいらしい。ちなみにoperator()をオーバーロードしたクラスを関数オブジェクトって言うらしい。関数のオブジェクトだな。インスタンス名()みたいな使い方できるからな。
なんでboolなのか、なんであれで昇順なのかはしらん。
たぶん、strcmpみたいなんと同じような理屈で結果を解釈して、大きいほうの引数を後ろに配置するんだろう。関数ポインタでもいいらしい。

 
std::vector< char * >

みたいな場合は


struct cmp { 
   bool operator()(const char *a, const char *b) const { 
   for (int i = 0; a[i] != '\\0' && b[i] != '\\0'; i++) { 
      if (a[i] != b[i]) { 
         return b[i] > a[i]; 
      } 
   } 
   if (a[i] == '\\0' && b[i] != '\\0') { 
      return true; 
   } 
   return false; 
}; 

みたいな感じでいいんじゃないかと思った。

Perl:


@array = sort @array; 

まあ、こんな感じ。比較関数を定義したい場合は、


@array = sort { $a cmp $b } @array; 

見たいな感じ。
{ }の中が-1なら$aを前に、1なら$bを前にするということらしい。
→http://www.uopmu.ees.osakafu-u.ac.jp/~yabu/soft/perl.html
がとっても参考になる。今まで雰囲気で使ってた。
そういうわけで、[C++]のやつと同じような考え方でよさげ。
$aと$bは予約語みたいなもんなのか?

Java:
配列なら
Arrays.sort()
コレクションなら
Collections.sort()

まあ、これはJavadocあるし、こまるこたぁないだろう。
Comparatorを作れば好きなように比較できる

キーワード:
クイックソート,quick,sort,ファンクタ,アルゴリズム,演算子,ソート,sort,list,コンテナ,アダプタ

コスミー について

昔(?)はゲーム作ってました。 今もなんか作ろうとしています。
カテゴリー: C++, C言語, Java, Perl, PHP, Tips パーマリンク

ソートソーターソーテスト への1件のフィードバック

  1. ピンバック: Perl Sort Array

コメントを残す

メールアドレスが公開されることはありません。