Найти - Пользователи
Полная версия: Вопрос по сортировки слиянием
Начало » Python для новичков » Вопрос по сортировки слиянием
1
polsovatel
Добрый день. Написал алгоритм сортировки слиянием(псевдокод взял в Кормене). Написал на си все работает, но на python почему-то нет. Думаю дело в рекурсивном вызове. Первый раз сталкиваюсь с ним в python. Помогите решить проблему.
 def Merge(lst, p, q, r):
    Left = []
    Right = []
    n1 = q - p + 1
    n2 = r - q
    for i in range(1, n1 + 1):
        Left.append(lst[p + i - 1])
    for j in range(1, n2 + 1):
        Right.append(lst[q + j]) 
    Left.append(32000)
    Right.append(32000)
    i = 1
    j = 1
    for k in range(p, r + 1):
        if Left[i] <= Right[j]:
            lst[k] = Left[i]
            i += 1
        else:
            lst[k] = Right[j]
            j += 1
def MergeSort(lst, p, r):
    if p < r:
        q = int((p + r) / 2)
        MergeSort(lst, p, q)    
        MergeSort(lst, q + 1, r)
        Merge(lst, p, q, r)
    return lst
lst = [10, 9, 8, 7, 6]
lst = MergeSort(lst, 1, len(lst))
print(lst)
FishHook
polsovatel
но на python почему-то нет
- Доктор у меня что-то болит!
- Нате вам какую-нибудь таблетку.

Как не работает? Ошибки же какие-то есть в терминале, наверняка.
polsovatel
Не понимаю на что ругается
 Traceback (most recent call last):
  File "/Users/murza/Documents/MergeSort.py", line 31, in <module>
    lst = MergeSort(lst, 1, len(lst))
  File "/Users/murza/Documents/MergeSort.py", line 25, in MergeSort
    MergeSort(lst, p, q)
  File "/Users/murza/Documents/MergeSort.py", line 25, in MergeSort
    MergeSort(lst, p, q)
  File "/Users/murza/Documents/MergeSort.py", line 27, in MergeSort
    Merge(lst, p, q, r)
  File "/Users/murza/Documents/MergeSort.py", line 15, in Merge
    if Left[i] <= Right[j]:
IndexError: list index out of range
py.user.next
  
"""Merge sort."""
 
def merge(left, right):
    """Merge two lists in ascending order."""
    lst = []
    while left and right:
        if left[0] < right[0]:
            lst.append(left.pop(0))
        else:
            lst.append(right.pop(0))
    if left:
        lst.extend(left)
    if right:
        lst.extend(right)
    return lst
 
def mergesort(lst):
    """Sort the list by merging O(n * log n)."""
    length = len(lst)
    if length >= 2:
        mid = int(length / 2)
        lst = merge(mergesort(lst[:mid]), mergesort(lst[mid:]))
    return lst    
FishHook
polsovatel
Не понимаю на что ругается
Слушай, ну не надо же быть Вассерманом, чтобы перевести фразу
IndexError: list index out of range
Даже если не знаешь английского, гугл-транслейт тебе выдаст это
Индекс списка вне диапазона: IndexError
Что тут не понятного то? Тебе даже строку показали, в которой ошибка. В пятнадцатой строке ты обращаешься к несуществующему элементу списка. Ну что тут можно не понять?!
polsovatel
Все разобрался. спасибо
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB