push swapとは何だったのか

### プロローグ
小耳に挟んだ馴染みのない◯◯ソートを実装したら簡単に通ってしまった。
なんとなくで通ってしまった、あの課題。
あれは一体何だったのか。

※解法を含むので一度自力で何も見ずにアルゴリズムを考えてから読むorそもそも読まないことをお勧めします。

42の他の課題として[philosopher](https://qiita.com/42yliu/items/86d16cdbc584c250ca6e)もよかったらどうぞ。

### 問題提起
- 提出したソートアルゴリズムを学ぶ過程で得た知識は業務で活かせるだろうか
- そのソートアルゴリズムが適する場面、適さない場面を見極めることはできるだろうか
- （もっと問題意識を広げて、）課題によって任意の適したソートアルゴリズムを見極める力はついただろうか
### 奇抜な問題設定について
- 応用問題をその問題単体とみなして解いても応用力は養われない
- 現実の応用問題はさらに多様でそれぞれ異なる
    - よって応用問題ごとに対処しても意味は薄い
- 一見変則的な問題が与えられたとして、必ずしも奇抜な応用力を発揮して解く必要があるとは限らない
- 基礎知識からの応用という位置付けで問題を捉えられるかが大事
> ソフトウェアエンジニアリングとは、**ある規則を未知の事例に応用する知的技能**である。 
>
> [出典：ソフトウェアエンジニアリングの性質を考慮した学習方法について](https://nop42.medium.com/%E3%82%BD%E3%83%95%E3%83%88%E3%82%A6%E3%82%A7%E3%82%A2%E3%82%A8%E3%83%B3%E3%82%B8%E3%83%8B%E3%82%A2%E3%83%AA%E3%83%B3%E3%82%B0%E3%81%AE%E6%80%A7%E8%B3%AA%E3%82%92%E8%80%83%E6%85%AE%E3%81%97%E3%81%9F%E5%AD%A6%E7%BF%92%E6%96%B9%E6%B3%95%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6-602c44976589 "ソフトウェアエンジニアリングの性質を考慮した学習方法について")

### ソートは簡単。簡単？
「ソートなんて簡単」
「ググればすぐ出てくる話」
「世の中アルゴリズムなんていくらでもあるので他のアルゴリズムではなくソートを特別視する意味はない」
そんな声が聞こえてきそう(聞こえてきた）。

世界ランキング1位のMIT（マサチューセッツ工科大学）の標準教科書と言われるアルゴリズムイントロダクションにはこう書かれている。

> ソートの目的
アルゴリズムを学ぶときに最も基本的な問題はソートであると、多数の計算機科学者は考えている。それにはいくつか理由がある。
・情報をソートすることが本質的に必要な多くの応用事例が存在する。...（略）...
・ソートを重要なサブルーチンとして用いるアルゴリズムが多い。...（略）...
・...（略）...ソーティングアルゴリズムは長年にわたって研究が続けられてきたが、そこから多数の重要なアルゴリズム設計技法が派生してきた。このようにソートは歴史的に興味深い問題でもある。

ソートをきちんと学ぶのには十分な理由がありそうだ。

### ソートの分類
> 「分けることは、分かることへの第一歩」
> 
> 出典：数学ガール

[基本情報技術者試験](https://www.ipa.go.jp/shiken/kubun/fe.html)の参考書を見るとこのような分類表[^1]が記載されている。
- 交換法
    - 基本法
        - バブルソート
    - 改良法
        - クイックソートetc
- 選択法
    - 基本法
        - 選択ソート
    - 改良法
        - ヒープソートetc
- 挿入法
    - 基本法
        - 挿入ソート
    - 改良法
        - シェルソートetc
　
- ソートの基本形は、「交換法」「選択法」「挿入法」の３つしかない
- この世に存在する数十以上ものソートアルゴリズムがほとんど全てこの３つに集約される
- であればどんな奇抜な設定のソート問題であれ、基本の３つをベースに考えていけば解けるのではないか


ここまで調べた段階（１ヶ月）でpush swapの見通しがよくなった。
もちろん、ソートアルゴリズムの区分けの視点として、安定の有無や外部メモリの有無、比較・非比較ソート、オンラインクエリなどたくさんあることを知ったが、ソートの本質はその操作方法にあり、そしてその操作方法は大きく３つに大別されることを理解するのが大事だというのが個人的な考えだ。

### 大胆に比較ソートを分ける
３つの基本法について「動き」に注目して分けてみる。
- 交換法
    - 未ソート領域で２要素を比較し、必要に応じて交換する
- 挿入法
    - 未ソート領域から一つ要素を$O(1)$で取り出しソート済み領域の適切な位置に入れる
- 選択法
    - 未ソート領域から一つ要素を適切に取り出しソート済み領域に$O(1)$で入れる

挿入法と選択法には少なからず対称性[^2]があるとここで感じた。

    選択法は選択時に計算コストがかかる。挿入法は挿入時に計算コストがかかる

### 基礎スキルを持って改めて応用問題を観察する（フレームワーク思考）
何かと評価の低いバブルソートに代表される交換法は最もシンプルな考え方だ。実装が一番簡単だとよく紹介されもする。よってまずは交換法でpush swapが解けないか考えてみる。
配列へのランダムアクセスは許可されていない。要素の交換操作はtopとsecondでしかできない。ソートには全ての要素に少なくとも交換操作が適用されるはずだ。これだけではうまくいかない。
データへの可能な操作一覧から他に使えそうなものを探す。ちょうど配列のrotate操作がある。これを使えば全要素に対して交換操作を適用できそうだ。
```c
//　解法１　交換法
while(!is_array_sorted)
    if (need_swap)
        swap_top_second();
    rotate();
```
外部メモリも使う必要なく、２つの操作のみで解くことができた。

### ”終わりに”
- 交換法の基本法であるバブルソートをもとにしたこのアルゴリズムの計算ステップ数は**少しだけ**遅い
    - １００要素のソートで１万ステップぐらい
- しかし、一度問題自体から離れ、ソートの基本を抑えたことで改良の道筋が見えるようになった
    - ステップ数の良し悪しではなく、思考プロセスの道筋の良し悪しが重要に感じる
    - 誤解を恐れずにいうとpush swapの課題においてこの交換法の解法を想起することが一番大事なことかもしれないとさえ思う
- ここで終わったほうがより主旨を伝えやすいので”終わりに”が唐突に設置されている
    - 実際は記事をn分割した名残り
- 残りの二つの基本法である選択法と挿入法を用いるとどうなるのだろう

- - -
### 続き

前回までは３つの基本法のうち１つから思考を繋げていったが、今回は残りの２つから問題にアプローチしてみる。

前回の復習だが、選択法と挿入法はコインの両表のような特徴がある。

    選択法は選択時に計算コストがかかる。挿入法は挿入時に計算コストがかかる

そして、整理済み領域と未整理領域の２つを必要としている。
改めて問題を見返すと、２つの領域が提供されているのでこれが使えそう。
元の配列をA、予備の配列をBとする。
Aを未ソート領域、Bをソート済み領域として使うのが自然だろう。

- 対称性により、どちらの解法も同等の計算コストC（＋BからAに全て移す）がかかる
```c
//解法2-1 選択法
while(is_A_not_empty)
    find_smallest_element();
    select_the_element();
    move_the_element_to_top_of_B();// cost C
push_back_to_a();
```
```c
//解法2-2 挿入法
while(is_A_not_empty)
    select_top_element();
    find_proper_location_at_B();
    insert_to_the_location();// cost C
push_back_to_a();
```
### 挿入法、選択法をベースに計算コストについて考える
- ソートにおいて発生する計算コスト[^3]の構成要素
    - 要素の移動
        - →移動コストと便宜上呼ぶ
    - 条件をもとにした要素の移動場所の決定or移動要素の決定
        - →決定コストと便宜上呼ぶ

- コストの種類の観点から
    - 普通のソートの問題
        - 決定コストの最適化
        - 移動コストなし
    - push swap
        - 決定コストなし
        - 移動コストの最適化

まずは通常のソート。

    選択法は選択時に計算コストがかかる。挿入法は挿入時に計算コストがかかる

より具体的に

    選択法は選択時に（移動要素の）決定コストがかかる。挿入法は挿入時に（挿入場所の）決定コストがかかる

といえる。長くなってきたので~~かっこつけたいから~~数式で書いていく

```math
\begin{align}
選択法の1要素の計算量&=\text{（移動要素の）決定コスト} + 移動コスト0 + \text{（挿入場所の）決定コスト}0\\
挿入法の1要素の計算量&=\text{（移動要素の）決定コスト}0 + 移動コスト0 + \text{（挿入場所の）決定コスト}\\
\\
\\
整理すると　    　　　　　　　　　&\\
\\
\\
選択法の1要素の計算量&=\text{（移動要素の）決定コスト}\\
挿入法の1要素の計算量&=\text{（挿入場所の）決定コスト}\\
\\\\
一方、　　　　     　　　　　　　　&\\
\\\\
\text{push_swap}の1要素の計算量&=決定コスト0 + \text{(未ソート領域での)移動コスト}function_{cost} + \text{(ソート済み領域での)移動コスト}function_{cost} + 決定コスト0\\
&=\text{(未ソート領域での)移動コスト}function_{cost} + \text{(ソート済み領域での)移動コスト}function_{cost}\\
\\\\
により要素iの配列a,bでの移動&コスト関数をそれぞれf_a(i),f_b(i)とすると　　\\
\\\\
\text{push_swap}の要素iの計算量&=\text{(未ソート領域での)移動コスト}f_a(i) + \text{(ソート済み領域での)移動コスト}f_b(i)\\
\\\\
よってAに残る全要素の中でコス&ト関数が最小になるような要素を動かすのは解法2-1,2-2に比べて効率がいいので\\
\\\\
移動するべき要素の\text{index} &= arg\min_{i∈[0,n)}\{f_a(i)+f_b(i)\}\\　　　where　　　　　　　　　\\
f_{array}(element) &= \min(idx_{element},\ length(array) - idx_{element})\\
n &= \text{number of elements in an array}
\end{align}
```

擬似コード（選択＋挿入法）

```c
// 解法3 選択＋挿入法
while(is_A_not_empty)
    while(there_is_element_left_for_evaluate_cost)
        evaluate_cost_of_select();
        evaluate_cost_of_insert();
        add_2_costs_to_return_total_cost_of_move();
    move_cheapest_cost_element();//cost C'
push_back_to_a();
```

### より効率的に
- 明らかに`rr`,`rrr`を用いれば少しマシになる。

この段階で100要素では600程度だが500要素では5500程度になる。
### さらに効率的に

- 基本法の発想だけで誘導通りに素直に進んできた
- 100要素で最高得点になるが500要素では達しないのも課題の誘導に見えてくる
- 次は改良法を取り入れる。改良法だと500要素のスコアが向上し最高得点に到達するとしたらそれは何故だろう

```c:最終結果
Test 200 cases: arg_length=100 range=(-2147483648, 2147483647)
---- Result ----
max   : 650
median: 585
min   : 526
Test 200 cases: arg_length=500 range=(-2147483648, 2147483647)
---- Result ----
max   : 4179
median: 3975
min   : 3774
```
- discordのランキングを見る限り、500要素だと東京キャンパス3位（2025/1時点）
    - 1,2位の方は混合アルゴリズムでアドホックに問題特化されているようだった
    - 一方自分の解法はチューニングを施さずにかなりシンプルな出来上がりとなったことを踏まえるとまずまずの結果ではないだろうか
- 荒削りな分、改善の余地も多分に含まれている
    - このスコアはスタート地点に過ぎない
    - よりよいスコアを求めていいアルゴリズムができたらぜひ教えてほしい

### Q&A
- Q.双方向循環リスト？配列？
    - どちらでも良い
    - 双方向循環リストを自作してみるほうが自分の為になるし教育的なのでは 
- Q.座標圧縮必要？したほうがいい？
    - 必要or不必要かといえば不必要
    - 座標圧縮自体、データの前処理として典型的な作業
       - やらないよりやったほうが自分の為になるし教育的なのでは
- Q. 計算「ステップ」？計算量O(n)じゃないの？
    - 計算量の議論をするにはこの条件下で用いる"計算量"の定義が必要
    - 数弱なのでパス
- Q.基数ソートは...?
    - [ソートの分類](#ソートの分類)と注釈[^1]を参照
- Q."Turk Algorithm"は...?
    - 車輪の再発明
    - [ソートの分類](#ソートの分類)と注釈[^1]を参照
- Q.ヒューリスティックや解探索を取り入れればもっと速くなる余地がある
    - それはそう
    - 本記事の主旨ではない
    - ぜひこの記事よりもよいスコアを叩き出していって欲しい
- Q.この記事の内容は本質ではない、本質は別にある
    - 我以外皆我師也
    - ぜひ記事を書いてください

### 終わりに
- 基本に立ち返るのが大事だと感じた
    - 聞いたことのないソートに出会った時、どの基本法のソートに帰着できるか、という視点を持てるようになった
- 自作の新種ソートが溢れていることに関して
    - 科学的に新しい発見というのは実際には既に存在している概念であることが多い
    - 科学的態度とは一見新発見に見えるものが実は既存の知識の再発見であることに快感と内省を覚えることではないだろうか
    - 『真理というものはたえず反復して取り上げられねばならないのだ。 誤謬が、私たちのまわりで、たえず語られているからだ』
- この課題は普段ソートに限らず計算量を考える際に無視できる部分のコストにスポットライトをあて、テーマにしていると感じた
    - あるシステムに対峙する時、純粋な古典的アルゴリズムの計算量のような分かりやすい話において無視されるような側面にもソフトウェアエンジアリングを行う設計者として大局的に注意を払うように、というようなメッセージを受け取った
- ４２の題材はどれも面白い
    - 今回の課題は今までと違い様々な条件が構築された課題設定
    - この課題はよくつくられてるなと感じた

### 追記予定（）
- push swap　改良法編
<details><summary>予告（＝ネタバレ）</summary>
決定コストO(1)により、選択アルゴリズムを使うことと、クイックソート等の背景にある分割統治法が有利な問題構造になっている</div></details>

[^1]:非比較ソート(基数ソート、カウントソート、計数ソートなど)は比較演算以外の情報の利用が許されるソートに分類され、比較ソートとは違った特徴を持つ。データが狭い整数範囲に分布していたり、重複要素が多数あるなど限局された特徴に対してソートアルゴリズムとして選択するモチベーションが出てくる。今回はそういった条件にしっくりと当てはまらない。

[^2]:実は交換法と挿入法や選択法の間にも数学的関係がある。これらの関係性を双対という概念で抽象化してまとめあげることができるらしい。

[^3]:計算コストって移動コスト、決定コスト以外にもあるのでは？その他のコストは？→鋭い。その他のコストがテーマになる課題もちゃんと先の方で用意しているのが４２のカリキュラム。