Combinar la clasificación para contar las inversiones divididas en Python

Estoy tratando de usar mergesort, que obtengo, para contar el número de inversiones divididas en una lista (es decir, cuando un elemento en la primera mitad de la lista sin clasificar debe aparecer después de un elemento dado en la segunda mitad de la lista). lista sin clasificar; por ejemplo, [3 2 1 4] contendría la inversión dividida (3, 1), pero no (3, 2) ya que 3 y 2 están ambos en la primera mitad). Cuando llego a la statement de impresión final, recibo la respuesta que espero, en este caso 9, pero el valor de retorno es completamente extraño ya que está devolviendo el valor de división a través de la recursión. He intentado todo tipo de combinaciones de indexación en vano. ¿Alguna ayuda? (usando Python 2.7)

(Para que quede constancia, este es un problema de la tarea de Coursera, pero estoy aprendiendo por diversión, nadie está calificando esto más que yo).

def mergesort(lst): '''Recursively divides list in halves to be sorted''' if len(lst) is 1: return lst middle = int(len(lst)/2) left = mergesort(lst[:middle]) right = mergesort(lst[middle:]) sortedlist = merge(left, right) return sortedlist def merge(left, right): '''Subroutine of mergesort to sort split lists. Also returns number of split inversions (ie, each occurence of a number from the sorted second half of the list appearing before a number from the sorted first half)''' i, j = 0, 0 splits = 0 result = [] while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 splits += len(left[i:]) result += left[i:] result += right[j:] print result, splits return result, splits print mergesort([7,2,6,4,5,1,3,8]) 

Modifique su función mergesort para ignorar las divisiones intermedias.

 def mergesort(lst): '''Recursively divides list in halves to be sorted''' if len(lst) == 1: return lst, 0 middle = len(lst)/2 left = mergesort(lst[:middle])[0] # Ignore intermediate splits right = mergesort(lst[middle:])[0] # Ignore intermediate splits sortedlist, splits = merge(left, right) return sortedlist, splits 

Hay algunas cosas mal en tu código:

  • No int() el resultado de len() / 2 . Si está usando Python3, yo usaría directamente la división de enteros con el operador // .
  • La comparación en la primera línea de mergesort() es incorrecta. En primer lugar, no usar is comparar para la igualdad. El operador solo está destinado a la identidad. Si tiene dos enteros diferentes que tienen el mismo valor, son iguales pero no idénticos. Para los enteros pequeños, creo que al menos algunos dialectos de Python integrarán el valor, por lo tanto, su comparación funciona, pero confía en algo que no está garantizado. Aún así, usar == tampoco funciona, porque olvidó el caso de la lista vacía.
  • Supongo que su problema real (“valor de retorno no deseado”) se debe al hecho de que devuelve dos valores que almacena (como una tupla) con un solo nombre y que luego pasa como parámetros a las llamadas recíprocas merge() .

Dado que, en su combinación de código devuelve un par, mergesort también debe devolver un par. Habilitar para obtener la inversión total dividida en la lista debe agregar la mitad izquierda, la mitad derecha y fusionar las inversiones divididas.

Aquí está la modificación que he hecho en su código.

 def mergesort(lst): '''Recursively divides list in halves to be sorted''' if len(lst) == 1: return lst, 0 middle = len(lst)/2 left, s1 = mergesort(lst[:middle])[0] # Ignore intermediate splits right, s2 = mergesort(lst[middle:])[0] # Ignore intermediate splits sortedlist, s3 = merge(left, right) return sortedlist, (s1+s2+s3)`