続・ソートってなんだよ(哲学)

残念ながら[前回の記事](https://qiita.com/BlueRayi/items/81722b5d72bcfce30b15)は思いっきり**ダダかぶり**をしていたためにゴミと化した。

ここは再起をかけてもう一度ソートとはなんなのかの哲学を提示し、あらためて新しい~~ネタ~~ソートを提案したい。

## 最低限「ソートされている」と言い張るための条件

「**自称ソーティングアルゴリズム**」あるいは「**スターリンソートらの集団**」などと呼称されるアルゴリズムたちは一様に「ソートできた」と主張しているので、おそらく結果が「**昇順に並んで**」されて**さえ**いればソートされていると言っていいのだろう。 **ソートってなんだよ(哲学)**(タイトル回収)

念の為テストメソッドを用意してみたが、嫌になるくらい「正しくソート」されている。 ~~クソが~~

```py:sort_check.py
import numpy as np

def is_sorted(data):
    for i in range(len(data) - 1):
        datum = data[i]
        next_datum = data[i + 1]
        if datum > next_datum:
            return False
    return True


# 実装が愚か極まりないのは私の実力不足です。 許し亭許して


def stalin_sort(data):
    new_data = data[:]
    for i in range(len(new_data) - 1):
        datum = new_data[i]
        next_datum = new_data[i + 1]
        if datum > next_datum:
            new_data.pop(i + 1)
            return stalin_sort(new_data)
    return new_data


def abe_sort(data):
    new_data = data[:]
    for i in range(len(new_data) - 1):
        datum = new_data[i]
        next_datum = new_data[i + 1]
        if datum > next_datum:
            new_data[i + 1] = datum
    return new_data


def ideal_commune_sort(data):
    return [np.average(np.array(data))] * len(data)


def real_commune_sort(data):
    new_data = ([0] * (len(data) - 1))
    new_data.append(np.sum(np.array(data)))
    return new_data


def doomsday_sort(data):
    new_data = data[:]
    new_data.clear()
    return new_data


def main():
    data = [1, 2, 1, 1, 4, 3, 9,]
    sd = stalin_sort(data)
    ad = abe_sort(data)
    icd = ideal_commune_sort(data)
    rcd = real_commune_sort(data)
    dd = doomsday_sort(data)
    print(F'       Source: {data} ({is_sorted(data)})')
    print(F'       Stalin: {sd} ({is_sorted(sd)})')
    print(F'          Abe: {ad} ({is_sorted(ad)})')
    print(F'Ideal Commune: {icd} ({is_sorted(icd)})')
    print(F' Real Commune: {rcd} ({is_sorted(rcd)})')
    print(F'     Doomsday: {dd} ({is_sorted(dd)})')


if __name__ == '__main__':
    main()
```

```
λ python sort_check.py
       Source: [1, 2, 1, 1, 4, 3, 9] (False)
       Stalin: [1, 2, 4, 9] (True)
          Abe: [1, 2, 2, 2, 4, 4, 9] (True)
Ideal Commune: [3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0] (True)
 Real Commune: [0, 0, 0, 0, 0, 0, 21] (True)
     Doomsday: [] (True)
```

## 既知ソートの問題点

昇順にソートできているのになにが問題なのかといえば、やはり**元データが変質してしまっている**ことだろう。

もちろん真面目に議論すればそれこそがこれらのソートの面白さなのでしょうがないのだが、やはり元データの変質を招くのは避けたい。

ここのところを本記事のポイントとする。

## 最終確認

もう一度確認する。

「**正しくソート**」されたというのは、**各要素が昇順に並べられている**ことである。 つまり**以下のテスト用メソッドに食わせて`True`が返却されている**ということである。

```py
def is_sorted(data):
    for i in range(len(data) - 1):
        datum = data[i]
        next_datum = data[i + 1]
        if datum > next_datum:
            return False
    return True
```

これが最後のチャンスだ。

## 銃口ソート

以下、私が提案する「**銃口ソート**」だ。

```py:muzzle.py
class RightNumber:
    next_idea = 0

    def __init__(self, eidos):
        self.eidos = eidos
        self.idea = RightNumber.next_idea
        RightNumber.next_idea += 1

    def __gt__(self, other):
        if not isinstance(other, RightNumber):
            return NotImplemented
        return self.idea > other.idea

    def __repr__(self):
        return str(self.eidos)

    @classmethod
    def reset_idea(cls):
        cls.next_idea = 0


def muzzle_sort(data):
    RightNumber.reset_idea()
    return [RightNumber(datum) for datum in data]


def main():
    data = [1, 2, 1, 1, 4, 3, 9,]
    md = muzzle_sort(data)
    print(F'Source: {data} ({is_sorted(data)})')
    print(F'Muzzle: {md} ({is_sorted(md)})')


if __name__ == '__main__':
    main()
```

```
λ python muzzle.py
Source: [1, 2, 1, 1, 4, 3, 9] (False)
Muzzle: [1, 2, 1, 1, 4, 3, 9] (True)
```

正しくソートされているよね? :gun: