はじめに

Hello world、2024年10月入学のMoriPです。
今回生まれて初めて記事を書くので、話があっちこっちするかもしれませんが、よかったら最後まで読んでください！

今回は、レビューや友人から好評だったpush_swap（以下プッスワ）のソートアルゴリズムについて紹介させていただきます。基数ソートより簡単で、100点（本人96点）も狙えるので、初心者救済のソートとして多くの人に知ってもらえると嬉しいです！

その名も「MoriP Sort」です！

MoriP Sortとは

チャンク（塊）に分けて処理を行うソートアルゴリズムです。

アルゴリズムの概要

データをチャンクに分割
チャンクの範囲内の要素を探して送る
そのチャンクに該当する要素がなくなったら次のチャンクへ
これを要素がなくなるまで繰り返す

具体例

以下の説明は座標圧縮後の値で進めます
座標圧縮はこちらから

例えば、ランダムに100個並んだ配列を5つのチャンクに分ける場合：

チャンクサイズ：各20個
範囲区分：
- チャンク1：1〜20
- チャンク2：21〜40
- チャンク3：41〜60
- チャンク4：61〜80
- チャンク5：81〜100

処理の流れ：

スタックAから最初のチャンク(1〜20)に該当する要素を探す
見つかった要素をスタックBにプッシュ
最初のチャンクの要素がなくなったら次のチャンク(21〜40)へ移動
これを最後まで繰り返す

処理フロー前半

処理フローの前半

実装の流れ

1. 構造体の初期化

スタックA
スタックB
コマンド出力用リスト

2. 引数のエラー処理

数字と文字の混合チェック
記号のみの引数チェック
その他無効な入力の検証

3. 座標圧縮

引数の値を0から始まる連続した数値に変換します。

4. ソート処理

3〜5個の引数：最適化されたソート
6個以上：MoriP Sortを実行

5. コマンド出力

コマンド実行時にリストを作成
実行した各コマンド（raなど）をデータとしてリストに保存
最後にraやrbが続いていたらそれらのコマンドを圧縮して出力

6. メモリの解放

mallocで確保したメモリを適切にfree
いろんな入力パターンでメモリリークをチェック

まずはソートできる関数を作る

スタックAからスタックBへ
スタックAの最小値を持つインデックスを探し、スタックの真ん中より上か下にあるかどうかでra, rraをしスタックA[0]に移動させる
　
スタックBからスタックAへ
スタックAとは逆に、最大値を持つインデックスを探し、同じくスタックB[0]に移動させる

スタックA、Bを往復するソートができます。
このままだと操作回数がどえらいことになりますが、これにさっき話したチャンクのロジックを追加すればMoriP Sortになります。
最大値、最小値を探す関数を作るのがキモです。

テスト結果

引数サイズ: 100

❯ python3 push_swap_tester.py -l 100 -c 100
Test 100 cases: arg_length=100 range=(-2147483648, 2147483647)
....................................................................................................
---- Result ----
max   : 661
median: 622
min   : 577
See result.log for details

引数サイズ: 500

❯ python3 push_swap_tester.py -l 500 -c 100
Test 100 cases: arg_length=500 range=(-2147483648, 2147483647)
....................................................................................................
---- Result ----
max   : 5773
median: 5574
min   : 5360

引数が500のときはあと少し最適化すれば5500を切って満点でしたが、先に課題を進めるために一旦スキップして提出しました。
工夫した点としては、pbするときにその値がそのチャンクの中央値より大きいか小さいかでpbした後raするかどうか判定していました。またpaするときにの最大値と最大値 −１を探して近い方をpaすることでコマンドの実行回数を減らせるようにしました。
Visualizerしたやつです。

MoriP Sortの背景

現在巷では、プッスワの課題を基数ソートが推奨されていますが、84点程度しか取れないとのこと。アルゴリズム未経験の私は「リスト？配列っしょ！」と思いながら、100点を取ってやる！と心の中で叫びながら取り組みました。

今回の実装では配列を使用しましたが（コマンド出力にリストを使用）、友人は双方向循環リストで100点を獲得しました。つまり、配列・リストどちらでも高得点が可能です！

最後に

うまく説明できたかわかりませんが、ここで言語化された説明をコードで書けるあなたは何も問題ないでしょう！
よくわかっていない、そこのあなた！もっと詳しく聞きたかったらMoriPを探して42を駆け回ってください。丁寧に説明します！
それか強強の友だちにたくさん聞きましょう！
42の課題もまだまだ序盤です。これからも一緒に頑張っていきましょう！！

tester || visualizer