Archives | Tumblr | Facebook | bullet-feed.pngRSS

xkcd: Ineffective Sorts - 間違ったソート関数いろいろ

  • このカテゴリでは、世界で最も人気があるウェブコミック「xkcd」の最新ナンバーをひたすら日本語に翻訳しています。
  • 過去の翻訳記事はxkcdカテゴリから。
  • 翻訳済みの秀逸なコミックについては、過去のベスト10をまとめた記事(2009年?2010年2011年2012年)からどうぞ。
  • このXKCD翻訳の目的の一つは、僕の英語スキル向上です。誤訳がありましたら、コメントなどで気軽にご指摘下さい。

ineffective_sorts.png
©xkcd.com Creative Commons Attribution-NonCommercial 2.5 License

Ineffective Sorts(役に立たないソート)

define HalfheartedMergeSort(list):
    if length(list)<2:
        return list
    pivot=int(length(list)/2)
    a=HalfheartedMergeSort(list[:pivot])
    b=HalfheartedMergeSort(list[pivot:])
    // ummmmm(うーむ)
    return [a,b] // Here. Sorry.(はいどうぞ。ごめん。)
define FastBogoSort(list):
    // An optimized BogoSort(最適化したボゴソート)
    // Runs in O(n log n)
    for n from 1 to log(length(list)):
        shuffle(list):
        if isSorted(list):
            return list
    return "Kernel Page Fault (Error code: 2)"
define JobInterviewQuicksort(list):
    OK so you choose a pivot(じゃ、ピボットを選んで)
    Then divide the list in half(リストを2分割して)
    for each half:(その片方:)
        check to see if it's sorted(ソートされているかどうか確認して。)
            no, wait, it doesn't matter(いや、まて、それはどうでもよかった)
        compare each element to the pivot(それぞれの要素をピボットと比較して。)
            the bigger ones go in a new list(より大きなものは、新しいリストへ。)
            the equal ones go into, uh(同じだったものは、えっと)
            the second list from before(前からの2番目のリストに行きます。)
        hang on, let me name the lists(待てよ。リストに名前を付けさせて。)
            this is list A(これは「リストA」)
            the new one is list B(新しいものは「リストB」)
        put the big ones into list B(大きいものはリストBに置いて)
        now take the second list(今もって2番目のリストは、えーっとA2と名づけよう。)
            call it list, uh, A2
        which one was the pivot in?(ピボットはどっちにあったけ?)
        scratch all that(全部消去。)
        it just recursively calls itself(それ自身を再帰的に呼び出す、)
        until both lists are empty(両方のリストが空になるまで。)
            right?(いいのか?)
        not empty, but you know what I mean(空じゃない。言いたいことはわかるよね。)
    am I allowed to use the standard libraries?(標準関数を使ってもいいか?)
define PanicSort(list):
    if isSorted(list):
        return list
    for n from 1 to 10000:
        pivot=random(0,length(list))
        list=list[pivot:]+list[:pivot]
        if isSorted(list):
            return list
    if isSorted(list):
        return list:
    if isSorted(list): //this can't be happening(これは起こりえない。)
        return list
    if isSorted(list): //come on come on(ほらほら!)
        return list
    // oh jeez(なんてこったい)
    // i'm gonna be in so much trouble(面倒なことになりそうだ。)
    list=[]
    system("shutdown -h +5")
    system("rm -rf ./")
    system("rm -rf ~/*")
    system("rm -rf /")
    system("rd /s /q C:\*") //portability(移植性の為)
    return [1,2,3,4,5]

補足

 Python的に書かれた、ありえないor間違ったソート関数記述いろいろ。

 HalfheartedMergeSort(list):リストを2つに分けて、それぞれをソートしようとしたが、よく分からなくなったので、分割した2つのリストをそのまま戻り値にする関数。

 FastBogoSort(list):最適化されたボゴソート

 JobInterviewQuicksort(list):ソート関数を作る、プログラマの頭の中を記述した関数。

 PanicSort(list):ランダムにソートして、ソートしたかを確認するプログラム。ソートされていなければ、パニックに陥り、関数内でシャットダウンしつつ、ファイルシステム内の全てのファイルを削除しようと試みる。

2013.3.14 追記

 コメントを参考に訳文を一部変更しました。

このエントリーをはてなブックマークに追加

関連性が高いおすすめ記事


comments powered by Disqus