何にでも使えるソート関数を目指す

競技プログラミング(AtCoder)を初めて数ヶ月、まだまだ慣れないけど、どういう問題が出てくるかはなんとなくわかってきた。

C言語で挑んでいると、構造体を使うことが多い。
ソートや一般的なデータ構造が登場すると、どうしても制限時間内に構造体をはめることが難しく、実装に時間を食ったりする(C++使え)。

そこで、どんな型を使っていても適用できるような仕様が作れれば大幅な実装短縮になると思ったのでやってみる。

今回は配列ソート関数の実装を行う。
構造体なども対象にするため、配列の実装はPHPのソート関数を参考にし、引数として比較関数を与えることにした。
配列なので基本戦略はやっぱりポインタになる。ただソート関数に直接引数として型 (int)が与えられたらよかったんだけど、できないかやり方が分からなかった。
ポインタでアドレスをわたし、size_t型の引数により要素のサイズを受け取る。こうすればどのような型の配列が対象でも、(void *)型で受け取り、要素サイズに応じてアドレスを区切れば良い寸法になる。

比較後の入れ替えも型情報なしのやり方は想像がつかなかったため、比較関数と同様に関数を与えることにした。
1時間半くらいで以下のようなものができた。

実装でアドレスを生で計算してるし、ドライバではポインタキャストした上で値とったりしてるし、我ながら変態プログラムである。*(int *)なんて見たことないよ!

もし入れ替え操作をvoidポインタと要素サイズだけでこねくり回せるのなら、そっちの方が手間が減るのでありがたい。(厳しいかな?)
それから今回はBubble Sortで実装したが、高効率ソートやPriority Queueを実装したい。

だって、競プロでPriority Queueの出番多そうじゃない?

 


 

P.S. Gistの埋め込みってコミット別に対応してないんですか…

カテゴリー C

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です