Hewlaの競プロ記

競プロ記です。

元の並び順を覚えたままソート

B - Guidebook
こういう問題が出たときに、


こういう方法をとれますが(てんぷらさんありがとうございます)、何も頭を使わずに書いてると頻繁にバグらせたので、このソートでなにがどうなるのか備忘録的に書いておきます。

そもそもどういうソート?

 数列3, 4, 1, 2, 5をソートすると1, 2, 3, 4, 5となりますが、もともと3が何番目にあったのかを思い出すことができません。思い出したいときによく考えるのは
(3, 0), (4, 1), (1, 2), (2, 3), (5, 4)
というstd::pairの配列を作ってソートすることで、これだと
(1, 2), (2, 3), (3, 0), (4, 1), (5, 4)
となって、無事3がソート前は0番目だったことを覚えたままソートできています。これが「覚えたまま」の意味です(わかりにくくてすみません)。
 で、これだとfirst.secondやらsecond.firstやら出てきがちで嫌な気分になるので、もっとシンプルにやろうというのが前述のてんぷらさんのツイートにあったソート方法です。

どうなるの?

f:id:hewla:20200119194536p:plain
数列本体は入れ替えず、ordが入れ替わります。

ソート後の数列のi番目はnum[ord[i]]になり、
もともとord[i]番目にいたやつがi番目にやってきたことになります。

複雑にソートやらなんやらかんやらを繰り返すときも、数列そのものは絶対入れ替えない方針で実装するとたぶん見通しが良くなるんだと思います(それはそう)。

おわりに

全然整理できてない雑な備忘録で申し訳ないです。
また、他のところでもこの方法が紹介されていたりとか、もっといいほうがあったりとか、この記事に誤りが含まれていたりとかしたら教えていただけると嬉しいです。