Hatena::Groupbugrammer

蟲!虫!蟲!

Esehara Profile Site (by Heroku) / Github / bookable.jp (My Service)
過去の記事一覧はこちら

なにかあったら「えせはら あっと Gmail」まで送って頂ければ幸いです。
株式会社マリーチでは、Pythonやdjango、また自然言語処理を使ったお仕事を探しています

 | 

2011-11-09

[]SleepSort、BogoSortに続く画期的なソートアルゴリズム、ErrorSortを考えた 06:45

はじめに

 凡そ実用性が皆無のネタソートアルゴリズムで有名なのは、SleepSortが有名ですね。

 常識を覆すソートアルゴリズム!その名も"sleep sort"! - Islands in the byte stream

 また、BogoSortというアルゴリズムもあります。

 ボゴソート - Wikipedia

 で、こういうネタソート、何か作れないかなーと思って考えていたら、「あっ、そうだ。エラーを使ってソートすればいいじゃないか」と思って実装してみた。

概要

 多くの言語だと、文字列配列のように取り出すように実装されていたりします。例えばPythonだと……

>>> "abc"[0]
'a'

 といったように。では、文字列の長さを超えて指定するとどうなるか。

>>> "abc"[4]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: string index out of range

 ポイントは、IndexErrorによって、その配列が「それ以上の文字列はありませんよ」というのを返してくれるわけですね。で、Pythonだと下のような記法が使えます。

>>> "a" * 5
'aaaaa'

 さらに、黒魔術を使いましょう。

>>> ("a" * 5)[1]
'a'

 ということは、文字列を掛けた数を、改めて配列操作することが可能になります。そこで、文字列を掛け算で生成し、IndexErrorを吐き出したものを順番に入れていけば、Sort出来るわけです。

実装

def ErrorSort(ar):
    result = []
    counter = 0
    while len(ar) != 0:
        for number,target in enumerate(ar):
            try:
                temp = ("a" * target)[counter]
            except IndexError:
                result.append(ar.pop(number))
                continue
        counter += 1
    return result

 そして、見事に次のようにソートされる、と。

>>> ErrorSort([1,39,3,5,92,0])
[0, 1, 3, 5, 39, 92]
 |