使用最小元素比較對5個元素進行排序

我必須使用元素間最小數量的比較來對python中5個元素列表進行排序的執行計劃進行建模。除此之外，複雜性是無關緊要的。使用最小元素比較對5個元素進行排序

結果是表示在另一次對列表進行排序所需的比較對的列表。

我知道有一個算法可以在7次比較（元素之間，總是，而不是複雜性）中做到這一點，但我找不到可讀的（對我來說）版本。

如何對7個比較中的5個元素進行排序，併爲排序構建一個「執行計劃」？

PD：不是作業。

來源

2012-07-29 slezica

最壞的情況下，最好的情況下，平均情況下？ – 2012-07-29 03:55:07

不是你在找什麼，但我很好奇，所以我只是檢查：在範圍（5）的120個排列中，內置'sorted'使用每個比較的排列數是：4： 2,6：5,7：33,8：56,9：24。 – Dougal 2012-07-29 04:01:49

只是好奇，Knuth與此有什麼關係？ – Yunchi 2012-07-29 04:15:58

這符合你的排序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一個可愛的模塊，可以讓你與這些玩。 Knuth引用了Bose-Nelson算法，但幾乎沒有比較者，您可以看到它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

來源

2012-07-29 06:28:52 dawg

那麼，有5！= 120種方式如何訂購元素。每次比較都會給你一點信息，所以你至少需要k個比較，其中2^k> = 120。你可以檢查2^7 = 128，所以7是你需要執行的最少比較次數。

來源

2012-07-29 04:09:48

美麗的數學，但這不是回答我的問題=/ – slezica 2012-07-29 05:40:19

那麼你的問題是什麼？ @ uwop-episdn – msw 2012-07-29 14:17:49

'**我怎樣才能對7個比較中的5個元素進行排序，併爲這個排序建立一個「執行計劃」？它寫在那裏= / – slezica 2012-07-31 09:30:13

我結束了使用常規的排序算法（插入排序）與中斷排序，並逐步自定義比較運營商構建一個執行計劃恢復或複製該過程。

這很醜陋：函數引發了一個異常，封裝了必要的信息以繼續排序。然後，可以重新排序新的信息，可能會再次中止。

由於排序嘗試發生在http請求的範圍內，所以性能對我來說不是問題。

來源

2012-07-29 12:59:19 slezica

使用最小元素比較對5個元素進行排序

回答

相關問題