6

要素間の比較の最小数を使用して、Pythonで5つの要素のリストを並べ替える実行プランをモデル化する必要があります。それ以外は、複雑さは関係ありません。

結果は、別のときにリストをソートするために必要な比較を表すペアのリストです。

7つの比較（要素間、常に、複雑さに関してではない）でこれを行うアルゴリズムがあることは知っていますが、読み取り可能な（私にとって）バージョンを見つけることができません。

7つの比較で5つの要素を並べ替え、その並べ替えの「実行プラン」を作成するにはどうすればよいですか。

PD：宿題ではありません。

4

3 に答える 3

3

さて、要素を並べ替える方法は 5!=120 通りあります。比較ごとに 1 ビットの情報が得られるため、少なくとも k 回の比較が必要です。ここで、2^k >= 120 です。2^7 = 128 を確認できるため、実行する必要がある比較の最小回数は 7 回です。

于 2012-07-29T04:09:48.847 に答える
2

これは、ソートの説明に適合します5 elements in 7 comparisons：

import random

n=5
ran=[int(n*random.random()) for i in xrange(n)]
print ran

def selection_sort(li):  
    l=li[:]                  
    sl=[]        
    i=1         
    while len(l):              
        lowest=l[0]            
        for x in l:            
            if x<lowest:      
                lowest=x  
        sl.append(lowest)  
        l.remove(lowest)     
        print i  
        i+=1
    return sl

print selection_sort(ran)

これは、最も効率的ではない選択ソートを使用しますが、比較はほとんど使用しません。

これは次のように短縮できます。

def ss(li):  
    l=li[:]                  
    sl=[]                 
    while len(l):              
        sl.append(l.pop(l.index(min(l))))       
    return sl

いずれの場合も、次のように出力します。

[0, 2, 1, 1, 4]
1
2
3
4
5
[0, 1, 1, 2, 4]

Perl にはAlgorithm::Networksortという素敵なモジュールがあり、これらを使って遊ぶことができます。Bose-Nelson アルゴリズムは、Knuth によっていくつかのコンパレーターとして引用されており、ここで確認できます。

編集

挿入ソートもうまく機能します。

def InsertionSort(l):
    """ sorts l in place using an insertion sort """
    for j in range(1, len(l)):
        key = l[j]
        i = j - 1
        while (i >=0) and (l[i] > key):
            l[i+1] = l[i]
            i = i - 1

        l[i+1] = key
于 2012-07-29T06:28:52.060 に答える
0

最終的に、並べ替えを中断し、プロセスを再開または再現するための実行計画を段階的に構築するカスタム比較演算子を使用して、通常の並べ替えアルゴリズム (挿入並べ替え) を使用しました。

醜いものでした: 関数は、ソートを続行するために必要な情報をカプセル化する例外を発生させました。次に、新しい情報で並べ替えを再試行すると、おそらく再び中止される可能性があります。

並べ替えの試行は http リクエストのスパンで発生するため、パフォーマンスは問題になりません。

于 2012-07-29T12:59:19.290 に答える