42 Tokyoの「push_swap」をクリア。

昨日「push_swap」という42 Tokyoの課題をクリアした。

「push_swap」はアルゴリズムを使い、与えられた数列を小さい順に並べ替えるというものだ。

3月8日から取り組みはじめたので、20日クリアまでに13日ほど費やした。

コーディングに費やした時間は69時間で、レビューは2.5時間ほどだったので、合計で71.5時間ほど投入したことになる。

課題ごとに定められたクリアまでの目安時間が60時間なので、9時間ほどオーバーだった。

他の課題では目安時間を2倍を超えることもあったので、目安時間を意識して取り組むことの効果が出始めている。

今後も目安の時間の中でクリアできるように取り組んでいこうと思う。

「push_swap」で学んだこと

アルゴリズムは「クイックソート」を使ったので、クイックソートへの理解が深まった。

クイックソートは簡単にいうと、ある数値を「ピボット」として定め、ピボットよりも大きい数字を左から、小さい数字を右から探し、どちらともが見つかった時点で入れ変えていくというアルゴリズムだ。

また課題の要件で、受け取った数列の全ての数字を1つずつ後ろにズラし、一番後ろの数字を一番前に持ってくるという操作や、その逆回転をも実装する必要があったので、循環リストを使用した。

循環リストを使用するには構造体をしようする必要があるので、構造体の扱い方も少しずつだが慣れてきた。

さらに、後方にある数値にいち早くアクセスしたい場合があったので、循環リストのなかでも、「双方向循環リスト」と呼ばれるものを使用した。

双方循環リストについては下記のページにまとめた。

ヴィジュアルで確認することの大切さ

この課題では、オフィシャルではないがフランスの42の学生が作成したヴィジュアライザーがあった。

これを用いると、以下のように自分の作ったコードが実際にどのように数列を並べ変えていくかを視覚的に理解することができる。

これはコードを書く上で、意図した通りに並べ替えを行なっているかどうかを確認するのに役立った。

またレビューの際にも、口頭とコードだけではなく、ヴィジュアライザーを使ってまずは視覚的にアルゴリズムを説明したほうが、後ほどのコードの説明の時に理解してもらいやすかった。

このような、コードを視覚化するものを作れるように、早くなりたい。

ランダムな数列を与えられた状態。棒の長さが数字の大きさを表している

右側のスタックに大きさを大体わけてソートしていく

左のスタックに、綺麗に大きい数字から並べていく

ソート終了。右側のスタックに小さい数字からだんだんと大きい数字になるように、並べ替えが完了。