残念ながら前回の記事は思いっきりダダかぶりをしていたためにゴミと化した。
ここは再起をかけてもう一度ソートとはなんなのかの哲学を提示し、あらためて新しいネタソートを提案したい。
最低限「ソートされている」と言い張るための条件
「自称ソーティングアルゴリズム」あるいは「スターリンソートらの集団」などと呼称されるアルゴリズムたちは一様に「ソートできた」と主張しているので、おそらく結果が「昇順に並んで」されてさえいればソートされていると言っていいのだろう。 ソートってなんだよ(哲学)(タイトル回収)
念の為テストメソッドを用意してみたが、嫌になるくらい「正しくソート」されている。 クソが
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が返却されているということである。
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
これが最後のチャンスだ。
銃口ソート
以下、私が提案する「銃口ソート」だ。
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)
正しくソートされているよね? 