0

「インプレース」クイックソートバージョンを作成するように依頼されました。2つの内部関数を作成しました。再帰関数と「インプレースソート」関数で、ランダムピボットを選択し（質問が必要です）、リストをインプレースでソートし、ソート後にピボットのインデックスを返します。

     import random

def quicksort(lst):

    def innerfunc(lst, start=0, end=(len(lst) - 1)):   
        temporal_pivot = subfunc(lst, start, end)

        if (end - start > 1): 
            if (temporal_pivot == start or temporal_pivot == start + 1):
                innerfunc(lst, temporal_pivot + 1, end)

            elif (temporal_pivot == end or temporal_pivot == end - 1):
                innerfunc(lst, 0 , temporal_pivot - 1)

            else:
                innerfunc(lst, 0 , temporal_pivot - 1), innerfunc(lst, temporal_pivot + 1, end)


    def subfunc(l, start, end):
        i_random = random.randint(start, end)  # chooses random index!
        l[i_random], l[start] = l[start], l[i_random]

        i_pivot = start
        pivot = l[start]

        i = end
        while i > i_pivot:
            if l[i] <= pivot:
                l.insert(i_pivot, l[i])
                i_pivot += 1
                l.pop(i + 1)

            else:
                i = i - 1

        return i_pivot


    return innerfunc(lst)

問題は実行時間です-

100以上の要素を含むリストは、非常にゆっくりとソートされます。

「subfunc」アルゴリズムと私のクイックソートのパフォーマンスを改善する方法についてのアイデアはありますか？

ありがとうございました！

オレン

4

2 に答える 2

2

l.insert()問題は、とを繰り返し呼び出すことl.pop()です。これらにはそれぞれO(n)複雑さがありますが、ループの各反復をO(1).

挿入と削除を繰り返すのではなく、要素を交換することで機能するように、関数を作り直す必要があります。

Wikipediaで疑似コードを見つけることができます。

于 2012-12-16T11:58:59.167 に答える
0

subfunc は効率的ではないようです-ループして配列部分に挿入します。私は Python プログラマーではありませんが、メモリの再割り当てが発生し、O(n) 操作のコストがかかる可能性があることをお勧めします

于 2012-12-16T11:44:58.280 に答える