使用最小元素比较对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个元素进行排序

回答

相关问题