Блог

Я написал этот код, чтобы получить количество используемых инверсий merge_sort , но я не получаю правильный результат. Может кто-нибудь сказать мне, почему это дает неправильный результат?

 def merge(B,C):  # B,C are sorted
  D = list()
  count = 0
  # empty list to get the merged list
  while (B != []) and (C != []):  # breaks if any one of B or C becomes empty

    b = B[0]  # to get first element of B
    print("b",b)
    c = C[0]  # to get first element of C
    print("c",c)
    
    if b<=c:
      B.remove(b)  # if b<c remove b from B and add to D
      D.append(b)
    else:
      C.remove(c)  # if b>c remove c from C and add to D
      D.append(c)
      count  = 1
      print("count_in_merge",count)

  # now if either one of B or C has become empty so while loop is exited
  # so we can add remaining elements of B and C as it is to D as they are
  # already sorted
  if B != []:                                       
    for i in B:
      D.append(i)
  
  if C != []:
     for i in C:
      D.append(i)

  return D, count 

def sort_and_num(A):
  if len(A) == 1:
    return A,0

  m = len(A) // 2
    
  B,count_b = sort_and_num(A[0:m])
  C,count_c = sort_and_num(A[m:])
    
  A_,count = merge(B,C)
  count  = (count_b   count_c)
  
  return A_, count
 

Когда я запускаю:

 A = [ 9, 8 ,7, 3, 2, 1] 
A_,c = sort_and_num(A)
print(A_,c) 
 

На выходе получается:

 [1, 2, 3, 7, 8, 9] 9
 

Но результат должен был быть

 [1, 2, 3, 7, 8, 9] 15
 

С другой стороны, если я введу :

 A = [3,1,2,4] 
A_, count = sort_and_num(A)
print(A_, count)
 

на выходе получается:

 [1,2,3,4 ] 3 
 

что правильно. Где что-то идет не так?

В вашем коде есть некоторые проблемы:

• чтобы удалить первый элемент списка, вы должны использовать pop() , а не remove()
• количество инверсий при извлечении элемента из C равно len(B) , нет 1 .
• вы должны добавить количество инверсий из каждой половины и фазы слияния
• начальный тест также sort_and_num должен проверять наличие пустого списка и возвращать его с числом 0.

Вот модифицированная версия:

 def merge(B, count_b, C, count_c):  # B,C are sorted
   D = []
   count = count_b   count_c
   # empty list to get the merged list
   while (B != []) and (C != []):  # breaks if any one of B or C becomes empty
      if B[0] <= C[0]:
         D.append(B.pop())  # if b<=c remove b from B and add it to D
      else:
         D.append(C.pop())  # if b>c remove c from C and add it to D
         count  = len(B)    # moving c before all remaining elements of B

  # now if either one of B or C has become empty so while loop is exited
  # so we can add remaining elements of B and C as it is to D as they are
  # already sorted
  for i in B:
     D.append(i)
  
  for i in C:
     D.append(i)

  return D, count 

def sort_and_num(A):
   if len(A) <= 1:
      return A,0

   m = len(A) // 2
    
   B,count_b = sort_and_num(A[:m])
   C,count_c = sort_and_num(A[m:])
    
   return merge(B, count_b, C, count_c)
 

В этом фрагменте кода:

 else:
    C.remove(c)  # if b>c remove c from C and add to D
    D.append(c)
    count  = 1
 

вы должны обновить count по длине остальной части B списка

     count  = len(B)
 

потому что перемещение элемента из правой части может «исправить» сразу много инверсий.

Также обратите внимание, что выбранная реализация довольно неэффективна из-за мгновенного удаления элементов из списков.