[課題振り返り] push_swap編
はじめに
今回は42の課題の1つであるpush_swapを振り返っていきたいとおもいます。
課題概要
この課題はC言語で2つのスタックが与えられ、それらを使ってコマンドライン引数から与えられた数字をソートするという課題です。
より少ない手数ほど高い点数を得ることができます。
学んだこと
ソート方法
まずは以下のurlから飛べる「アルゴ式」というサイトを使用して一通り基本となるソート方法を学びました。
ですが、ここでそれらのソートについて解説するのは本筋とずれるので解説しません。基数ソート
筆者は今回基数ソートを選択しました。
基数ソートとは、小さい位から順に、その数字のグループに割り振った後、その位が小さい順に取る方法です。
視覚的に見るとわかりやすいので以下のurl「Algoful」のソートシュミレータを交換速度を遅めにして実行してみてください。
また、一般的なソート方法の時間計算量はO(nlogn)やO(n^2)だったりしますが、基数ソートはO(n・d)です。
(nは要素数、dは要素の桁数の最大値)
基数ソートは数値の比較自体をせずに桁ごとに分けるのでdに依存します。
基数ソートが効率的なケース
・データの桁数が少ないとき
-> 各位を見てグループ分けする回数が減る
・要素数が大きいとき
-> 計算量から見てもわかるように他のソートと比較してnに対する依存度が低い
基数ソートが非効率的なケース
・極端に大きな桁数を持つ要素を含むとき
-> 1つでも極端に大きな桁数を持つ要素があると、それに合わせてグループ分けする回数が増える
・要素数が少ないとき
-> 普通のソートをした方が早い場合がある
今回の課題で使えるのか
基数ソートは少なくとも10個のスタックが必要になってしまいます。(0~9で割り振っていく必要があるため)
今回の課題で使えるスタックは2個なので一見基数ソートは使用できないように思えます。
ですが、10個のスタックを使用しているのは各位で可能性のある数字が0~9の10通りあるからです。
もしも各位で可能性がある数字が2通りであれば2個のスタックでソートすることができます。
つまり、2進数を利用します。
PCは2進数でのビット演算にCPUで直接処理できるのでとても強いです。
具体的にどう操作するのか
2つのスタックをそれぞれA,Bと名付けます。
はじめはAに全ての要素が入っていて、
以下の1~3の操作を最下位bitから最上位bitにかけて順番のおこなっていきます。
- Aスタックの一番上の要素のbitが1ならBスタックへ移動、0ならAスタックの一番下へ移動
- 1を全ての要素に対して繰り返す
- Bスタックの要素を全てAスタックに戻す
ソート前に要素に対してindexを割り振る
今回の課題は「ソートの手数を減らす」ことに注力すれば良いです。なので今回限定で受け取った要素をはじめにソートして値の小さい順にindexを割り振ります。
こうすることで基数ソートの非効率的になるケースである「極端に大きな要素が含まれるとき」を除外できます。
また、これをすると基数ソートの計算量O(n・d)に関してn(要素数)が固定であればd(桁数)も固定されるので要素数さえ同じであれば手数が毎回一定になります。
リスト構造体
スタックの表現の仕方としていくつか方法があるのですが筆者はリスト構造体を使用しました。
配列を使用する場合ははじめに要素数を指定する必要がありますが、リスト構造体はサイズに対して柔軟に対応できます。
慣れるまではメモリの操作などが難しいですがこれは後の課題のminishellなどでも生きてきます。
参考文献・サイト
https://algo-method.com/ 「アルゴ式」
https://algoful.com/Archive/Algorithm/RadixSort 「Algoful」
Discussion