5要素を最小要素比較で並べ替える

Question

要素間の最小限の比較数を使って、5要素のリストをPythonでソートする実行計画をモデル化する必要があります。それ以外は、複雑さは無関係です。

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

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

7つの比較で5つの要素をソートし、並べ替えのための「実行計画」を作成するにはどうすればよいですか？

PD：なし宿題。

Answer 1

これは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) 

これが最も効率的ではありませんが、非常に少数の比較を使用しSelection Sortを使用しています。

この

はに短縮することができます。いずれの場合も

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によっていくつかのコンパレータで引用されており、それはhereです。

編集

insertion sortも適しています：

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 

Answer 2

まあ、要素がどのように順序付けできるかは、5！= 120通りあります。それぞれの比較で1ビットの情報が得られますので、2^k> = 120で少なくともk回の比較が必要です.2^7 = 128をチェックすることができるので、実行する必要がある比較の数は最小です。

Answer 3

私はソートを中断し、徐々に実行を構築するカスタム比較演算子と定期的なソートアルゴリズム（挿入ソート）を使用して終了プロセスの再開または再現を計画する。

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

HTTPリクエストのスパンでソートが試行されるため、パフォーマンスは私にとって問題ではありません。