Mergesort больше не в порядке

Question

Я не начинающий кодер python, но я тоже не продвинутый. Проблема будет легче объяснить, если вы можете посмотреть, что я описываю. Вот код, я вижу проблему в:

import operator 

def mergeSort(L, compare = operator.lt): 
    if len(L) < 2: 
     return L[:] 
    else: 
     middle = int(len(L)/2) 
     left = mergeSort(L[:middle], compare) 
     right = mergeSort(L[middle:], compare) 
     return merge(left, right, compare) 

def merge(left, right, compare): 
    result = [] 
    i,j = 0, 0 
    while i < len(left) and j < len(right): 
     if compare(left[i], right[j]): 
      result.append(left[i]) 
      i += 1 
     else: 
      result.append(right[j]) 
      j += 1 
    while (i < len(left)): 
     result.append(left[i]) 
     i += 1 
    while (j < len(right)): 
     result.append(right[j]) 
     j += 1 
    return result 

Функция слияния работает. Конечный результат возврата всегда в порядке. Проблема заключается в том, что если вы сделаете один шаг вперед от конечного результата возврата, возвращаясь к объединению возврата (слева, справа, сравните) в mergesort, возвращенный список L больше не в порядке, а затем этот плохо упорядоченный список возвращается которая называется mergesort. Я даже не понимаю, почему это происходит. Что может произойти в обратном пути из результата возврата, чтобы возвратить слияние (слева, справа, сравнить)? Возвращенный список не является рандомизированным списком, он выглядит как частично отсортированный список, но он был полностью отсортирован по окончательному результату возврата, и этот результат не был возвращен в mergesort.

Я использовал это объединение без проблем, поэтому проблема может быть в данных, которые я сортирую. L - список списков, и каждый элемент списка представляет собой список строк, все одинаковой длины, которые будут экспортированы в csv и в конечном итоге в Excel. Мои данные - таблица с названиями веб-сайтов в первом столбце и URL-адресами во втором столбце, и я сортирую их для идентификации дубликатов. В полной таблице есть несколько других полей, но я вижу эту проблему только с столбцами заголовка и URL-адреса, что было упрощено, поэтому я мог попытаться понять, что происходит не так. Я не был уверен, может ли mergesort обрабатывать эту структуру данных, но конечный результат возврата в слияние определенно указывает на то, что он может. Но что-то таинственное происходит в конечном возвращении.

Answer 1

Я закончил тем, что писал the python.org list об этой проблеме, и первый ответ, который я получил удар ноготь на голове:

чт, 22 декабря 2016 г. в 11:55, Deborah Свенсон писал:

проблема заключается в том, что в то время как слияние помещает список Ls в идеальном порядке, , которые я могу видеть, глядя на результате на окончательном возвращении Merge к слиянию, а слева и справа один раз обратно в mergeSort. Оба - левая половина и правая половина - в порядке. Но список L по-прежнему в оригинальном порядке, и после того, как mergeSort завершает работу, ls все еще находится в его первоначальный заказ. Может быть, есть некоторая ошибка в кости, вызывающая это, , но я просто не вижу этого.

Ваш анализ превосходный. Вот что происходит: При слиянии-то, вы всегда возвращает новый список (или «возвращение L [:]» или «результат = []»), но тогда вы называете это так:

# sort: Description only, to make hyperelinks & find duplicates 
mergeSort(ls) 

Это вызывает mergeSort, а затем отбрасывает вновь отсортированный список на полу. Вместо этого попробуйте: «ls = mergeSort (ls)».

Благодарим за то, что вы сделали это так легко!

Хриза

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

Answer 2

Похоже, что результат слияния не был сохранен. Вот исправление:

def mergeSort(L, compare = operator.lt): 
    if len(L) < 2: 
     return L[:] 
    else: 
     middle = int(len(L)/2) 
     left = mergeSort(L[:middle], compare) 
     right = mergeSort(L[middle:], compare) 
     L[:] = merge(left, right, compare) 
    return L