Проблемы с сортировкой слияния - Python

Question

Что случилось с моим кодом? Он печатает только часть значений vect. Кажется, что цикл while прерывается в какой-то момент. Я не понимаю, почему.

def print_list(vect): 
    for i in range(0, len(vect)): 
     print(vect[i]) 

def merge_sort(vect): 
    left = [] 
    right = []  
    result = [] 

    for i in range(0, int(len(vect)/2)): 
     left.append(vect[i]) 
    for i in range(int(len(vect)/2), len(vect)): 
     right.append(vect[i]) 

    left.sort() 
    right.sort() 
    i = 0 
    j = 0 

    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 

    print(len(result)) 
    return result 

vect = [3, 1, 5, 7, 10, 2, 0] 

vect = merge_sort(vect) 

Answer 1

Ну, ваша ошибка в том, что после цикла в то время как

while i < len(left) and j < len(right): 
    ... 

это может быть (и, скорее всего, будет), что либо i < len(left) или j < len(right), поэтому вам необходимо добавить суффикс соответствующей части к ответу , Это легко сделать с помощью

result += left[i:] 
result += right[j:] 

Пояснение:

Представьте процедуру слияния: у вас есть я и J на ​​0 при старте, и на каждом шагу вы переместите один из них вперед. Когда вы остановитесь? Когда один из них достигает конца. Допустим, я дошел до конца. Таким образом, вы добавили всю левую часть к результату, но все еще есть некоторые элементы справа от j и len (справа), поэтому вам также нужно добавить их в ответ.

Оффтоп:

Вы реализуете сортировка слиянием, поэтому, пожалуйста,

left = merge_sort(left) 
right = merge_sort(right) 

вместо

left.sort() 
right.sort() 

Внимание: вы должны добавить следующую проверку на ваш код в начале функции слияния, чтобы избежать бесконечной рекурсии:

if len(vect) == 1: 
    return vect 

Также в вашем print_list функции вы можете просто использовать

print vect 

или по крайней мере

for x in vect 
print x 

Answer 2

Петля в то время как выход, как только влево или вправо будет исчерпан. Это оставляет все элементы, оставшиеся в неисчерпаемом списке, не моргнуты.

Измените код следующим образом:

def print_list(vect): 
    for i in range(0, len(vect)): 
     print(vect[i]) 

def merge_sort(vect): 
    left = [] 
    right = [] 

    result = [] 
    for i in range(0, int(len(vect)/2)): 
     left.append(vect[i]) 
    for i in range(int(len(vect)/2), len(vect)): 
     right.append(vect[i]) 

    left.sort(); 
    right.sort(); 
    i = 0 
    j = 0 

    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 

    if i < len(left): 
     result.extend(left[i:]) 
    else: 
     result.extend(right[j:]) 

    print(len(result)) 
    return result 

vect = [3, 1, 5, 7, 10, 2, 0] 

vect = merge_sort(vect) 
print vect 

Если вы используете метод сортировки слева и справа, я немного запутался, почему вы не просто использовать его в списке как целое. Но, полагаю, у вас есть причины. :)

Редактировать: Я разместил здесь весь блок кода, чтобы вы могли его увидеть. Когда я запускаю это, он печатает [0, 1, 2, 3, 5, 7, 10], что является правильным.