01/10/2018, 11:44

Mong mọi người giải thích cho mình 1 dòng code trong thuật toán "finding median"

def median_of_medians(A, i):

    #divide A into sublists of len 5
    sublists = [A[j:j+5] for j in range(0, len(A), 5)]
    medians = [sorted(sublist)[len(sublist)/2] for sublist in sublists]
    if len(medians) <= 5:
        pivot = sorted(medians)[len(medians)/2]
    else:
        #the pivot is the median of the medians
        pivot = median_of_medians(medians, len(medians)/2)

    #partitioning step
    low = [j for j in A if j < pivot]
    high = [j for j in A if j > pivot]

    k = len(low)
    if i < k:
        return median_of_medians(low,i)
    elif i > k:
        return median_of_medians(high,i-k-1) --- Đoạn này em không hiểu mong mn giải thích em với
    else: #pivot = k
        return pivot

#Here are some example lists you can use to see how the algorithm works
#A = [1,2,3,4,5,1000,8,9,99]
#B = [1,2,3,4,5,6]
#print median_of_medians(A, 0) #should be 1
#print median_of_medians(A,7) #should be 99
#print median_of_medians(B,4) #should be 5

Nguồn https://brilliant.org/wiki/median-finding-algorithm/

rogp10 viết 13:56 ngày 01/10/2018

Thực ra cái này chỉ là quickselect.

Mà mình thấy hình vẽ rõ ràng rồi mà, nói thêm thì nó ntn: từ i bạn tính lại chỉ số cần tìm trong high[] vừa tạo. Vì pivot đứng thứ…? nên phải trừ đi.

Bài liên quan
0