読者です 読者をやめる 読者になる 読者になる

挿入ソートを復習

memo

 今日は暇つぶしにAIZU ONLINE JUDGE: Programming Challengeの問題を最初の方から片付けていて、挿入ソート | アルゴリズムとデータ構造 | Aizu Online JudgeRubyで解いたりした。

 アルゴリズム自体はもう問題に擬似プログラミング言語で書いてあるので解くだけなら悩むことはないけれど、理解しようとしてそこそこ考えた。

 例えば、6行目と8行目でA[j+1]にA[j]とvを代入しているけれど、これって後者だけが有効で意味なくね?とか思ってしまったのだ。

 でもよく見てみれば、7行めでj--がされているので、8行目のA[j+1]は6行目のA[j+1]とは別のものなんだよね。

 で、更にwhileループの中で、A[j+1] = A[j]をしているのが配列の中の数字を右に一つずらしている作業で、なんでずらしているかっていうとA[i]がその位置より左にあるものより小さかった時、正しい並び順の位置に移動させるためにやっているのであって、whileループの初回のA[j+1]っていうのはA[i]と同じものだったということに気がついたりもした。

 そして、A[i]がその位置より左にあるものより小さかった時、っていう条件を、if文でやらずにwhileの条件でまとめられているのがまたいいなぁ、とか。

 そういう小さな気づきが重なるのが楽しい。

 え、お前そのくらい大学で勉強しただろって?したけど忘れてしまっていたよ…。