न्यूनतम तत्व तुलना के साथ 5 तत्वों को क्रमबद्ध करना

Question

मुझे तत्वों के बीच तुलना की न्यूनतम संख्या का उपयोग करके पाइथन में 5 तत्वों की सूची क्रमबद्ध करने की निष्पादन योजना का मॉडल करना होगा। इसके अलावा, जटिलता अप्रासंगिक है।

परिणाम परिणाम की सूची को किसी अन्य समय क्रमबद्ध करने के लिए आवश्यक तुलनाओं का प्रतिनिधित्व करने वाले जोड़े की एक सूची है।

मुझे पता है कि एक एल्गोरिदम है जो 7 तुलनाओं में (तत्वों के बीच, हमेशा जटिलता के अनुसार नहीं) करता है, लेकिन मुझे एक पठनीय (मेरे लिए) संस्करण नहीं मिल रहा है।

मैं 7 तुलनाओं में 5 तत्वों को कैसे क्रमबद्ध कर सकता हूं, और इस तरह के लिए "निष्पादन योजना" का निर्माण कैसे कर सकता हूं?

पीडी: होमवर्क नहीं।

Answer 1

यह 5 elements in 7 comparisons छँटाई के अपने विवरण फिट बैठता है।

यह करने के लिए छोटा किया जा सकता:

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] 

पर्ल एक सुंदर मॉड्यूल है कि आप इन के साथ खेलने की अनुमति देता Algorithm::Networksort कहा जाता है। बोस-नेल्सन एल्गोरिदम को कुछ तुलनित्रों के लिए 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 तरीके तत्वों का आदेश कैसे दिया जा सकता है। प्रत्येक तुलना आपको एक छोटी सी जानकारी देती है, इसलिए आपको कम से कम के तुलना की आवश्यकता होती है, जहां 2^के> = 120. आप 2^7 = 128 की जांच कर सकते हैं, इसलिए 7 कम से कम तुलना करने की तुलना में आपको तुलना करने की आवश्यकता है।

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 जो सबसे कारगर नहीं है का उपयोग करता है, लेकिन बहुत कम की तुलना का उपयोग करता है:

Answer 3

मैं एक निष्पादन बनाता है एक कस्टम तुलना ऑपरेटर कि छंटाई व्यवधान और उत्तरोत्तर के साथ एक नियमित सॉर्टिंग एल्गोरिथ्म (प्रविष्टि प्रकार) का उपयोग कर समाप्त हो गया प्रक्रिया को फिर से शुरू करने या पुन: उत्पन्न करने की योजना है।

यह बदसूरत था: इस कार्य ने सॉर्टिंग जारी रखने के लिए आवश्यक जानकारी को एक अपवाद उठाया। फिर सॉर्टिंग को नई जानकारी के साथ पुनः प्रयास किया जा सकता है, शायद इसे फिर से छोड़ा जा सकता है।

जैसे कि http अनुरोधों के दौरान सॉर्टिंग प्रयास होते हैं, प्रदर्शन मेरे लिए कोई मुद्दा नहीं है।