Sắp xếp 5 phần tử có so sánh yếu tố tối thiểu

Question

Tôi phải lập mô hình kế hoạch thực hiện sắp xếp danh sách 5 phần tử, trong python, sử dụng số so sánh tối thiểu giữa các phần tử. Khác hơn thế, sự phức tạp là không liên quan.

Kết quả là danh sách các cặp biểu thị các so sánh cần thiết để sắp xếp danh sách vào một thời điểm khác.

Tôi biết có một thuật toán thực hiện điều này trong 7 so sánh (giữa các phần tử, luôn luôn, không phức tạp), nhưng tôi không thể tìm thấy phiên bản có thể đọc được (đối với tôi).

Làm cách nào để sắp xếp 5 phần tử trong 7 so sánh và xây dựng "kế hoạch thực hiện" cho sắp xếp?

PD: không bài tập về nhà.

Answer 1

này phù hợp với mô tả của bạn phân loại 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) 

này sử dụng một Selection Sort mà KHÔNG phải là hiệu quả nhất, nhưng sử dụng rất ít so sánh.

này có thể được rút ngắn xuống còn:

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

Trong cả hai trường hợp, in một cái gì đó như thế này:

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

Perl có một module đáng yêu gọi Algorithm::Networksort cho phép bạn chơi với những. Thuật toán Bose-Nelson được trích dẫn bởi Knuth cho một vài bộ so sánh và bạn có thể thấy nó here.

Sửa

Một insertion sort cũng hoạt động tốt:

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

Vâng, có 5! = 120 cách các yếu tố có thể được đặt hàng. Mỗi so sánh cung cấp cho bạn một chút thông tin, vì vậy bạn cần ít nhất k so sánh, trong đó 2^k> = 120. Bạn có thể kiểm tra 2^7 = 128, vì vậy, 7 số ít nhất là so sánh bạn cần thực hiện.

Answer 3

tôi đã kết thúc bằng một thuật toán sắp xếp thông thường (sắp xếp chèn) với toán tử so sánh tùy chỉnh mà làm gián đoạn việc phân loại và dần dần xây dựng một thực có kế hoạch tiếp tục hoặc tái tạo quy trình.

Rất xấu: chức năng đã đưa ra một ngoại lệ bao gói thông tin cần thiết để tiếp tục sắp xếp. Sau đó phân loại có thể được thử lại với thông tin mới, có thể sẽ bị hủy bỏ một lần nữa.

Khi các nỗ lực sắp xếp xảy ra trong khoảng thời gian yêu cầu http, hiệu suất không phải là vấn đề đối với tôi.