« Re: 働いてみたいIT企業 | トップページ | [python] Python2.5 Final released »

2006/09/16

[参加者募集/ Python]君ならどう書く? -merge sort-

本家 LLRing 風にちょっとした問題で遊んでみようと思います。Python 以外の言語の参加もお待ちしています。お題は↓

任意の大きさの配列 X に対してマージソートを行い、要素を昇順に並べ替えるコード

わたしの場合はこんな感じになりました。

def prepare_divide( unsorted_list ):
    length = len( unsorted_list )
    intermediate = [ unsorted_list[: length/2 ], unsorted_list[ length/2 :]]
    intermediate.sort()
    
    return intermediate


def divide( unsorted_list ):
    intermediate = prepare_divide( unsorted_list )
    divided_list = []
    for part in intermediate :
        max_length = len( part )
        while max_length > 1:
            divided_list += prepare_divide( part )
            
            max_length    = max( [ len(x) for x in divided_list ] )
            part = divided_list.pop( [ len(x) for x in divided_list ].index( max_length ) )
        else:
            divided_list.append( part )
        
    return divided_list


def merge( merged_list, sorted_list ):
    # Two list objects are required.
    # Both are must be sorted.
    
    probable_merged = []
    x = 0; y = 0
    try:
        x = merged_list.pop(0)
        y = sorted_list.pop(0)
    except:
        pass
    
    # To break Loop, chatching exception IndexError occured by list.pop(0)
    # Because lacking elements of lists, do Not write "while( list1 or list2 )"
    while 1:
        try:
            if( x < y ):
                probable_merged .append( x )
                x = merged_list.pop(0)
            elif( y < x ):
                probable_merged .append( y )
                y = sorted_list.pop(0)
            elif( ( x == None ) or ( y == None ) ):
                notNone = lambda i, j: i or j
                probable_merged .append( notNone( x, y ) )
        except IndexError:
            # When IndexError is raised, one of lists became empty.
            # Then appending the other into probable_merged
            if x in probable_merged:
                if not( y in probable_merged ):
                    probable_merged.append(y)
            elif   not( x in probable_merged ):
                probable_merged.append(x)
            probable_merged = probable_merged + merged_list + sorted_list
            break
        except AttributeError:
            break
    
    return probable_merged


def merge_sort( unsorted_list ):
    if type( unsorted_list ) != type( [] ) :
        import sys
        print "Argument must be List."
        sys.exit()
    
    divided_list = divide( unsorted_list )
    merged_list  = divided_list.pop(0)
    sorted_list  = []
    
    while len(divided_list) > 0:
        sorted_list = divided_list.pop(0)
        merged_list = merge( merged_list, sorted_list )
    return merged_list

↑が見難い場合はこちら
再帰を使わずに書いて見ました。merge() がなんか汚いです( ´・ω・`)

prepare_divide() と divide() で配列を分割。

merge() で2つのリストを統合。やっていることは単純で、2つの配列の中から一番小さな値から順に取り出して新しい配列に並べているだけ。例外を補足した後にごちゃごちゃやっているのは、要素が重複しないようにするため。

最後の merge_sort() はインターフェイス関数。引数のチェックと他の関数 divide() と merge() への引数パスとソート済みリストの出力を担当してます。

Python には要素が重複しないオブジェクトとして set オブジェクトがあるけど、これは unordered collection なのでソートには不向き。残る方法は、とりあえず全部突っ込んでから重複した要素を取り除くか、最初から要素が重複しないようにすることだけど、後者の方が簡単だと思って上のように実装しました。

三項演算子と do-while があったらもっと綺麗になりそうだなと思いつつ書き書き。たった一文字のTYPOに気付けずにデバッグに4時間半かかりましたとさ。最強のバグは TYPO かもしれない _| ̄|○il|!

2006.09.18
バグ&コメントのTYPO修正。
型チェックのつもりのコードが同値検査になってたよ_| ̄|○il|!

|

« Re: 働いてみたいIT企業 | トップページ | [python] Python2.5 Final released »

コメント

こないだはありがとうございました。
再帰呼び出しを使わないってのが面白いので、
練習問題のページを作ってみました。
http://omake.accense.com/wiki/PythonExerciseMergeSortNonRecursive

投稿: かねもと | 2006/09/25 10時53分

コード拝見いたしました。
リストを分解するなら
[ [element] for element in unsorted_list ]
で簡単に処理できるなぁと
いまさらながら気付きました。

単純明快で素晴らしいコードだと思います。

なお、わたしが再帰を使わなかったのは
問題に「任意の長さ」と設定したからです。
再帰が含まれる場合、十分な長さを持った配列を
渡されるとオーバーフローしてしまいますから
任意の長さに対応できるとはいえません。
そこで再帰を使わない方法を考えました。

でも、わたしのコード、再帰を使ったコードを無理やり
非再帰にしたのがバレバレですね_| ̄|○il|!

投稿: Fomalhaut | 2006/09/25 18時37分

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/103108/11914467

この記事へのトラックバック一覧です: [参加者募集/ Python]君ならどう書く? -merge sort-:

« Re: 働いてみたいIT企業 | トップページ | [python] Python2.5 Final released »