Python на месте слияния сортировки - PullRequest
Новая
       49

Python на месте слияния сортировки

0 голосов
/ 29 сентября 2019

Я пытаюсь работать над сортировкой слиянием на месте на python.Я понимаю концепцию, но нужна помощь в реализации.Я создал псевдокод, но у меня возникли проблемы с его завершением.Моя первая функция является функцией слияния, а вторая - реализацией на месте.

Вот ссылки на псевдокод, из которого я строю: 1) https://prnt.sc/pcb0ci 2) https://prnt.sc/pcb0e2

def merge(array, low, mid, high)

i,j,k = 0, mid + 1, 0

leftArray = array[0:mid]
rightArray = array[mid:high]

while i <= len(leftArray) and j <= len(rightArray):

    if leftArray[i] < rightArray[j]:
        array[k] = array[i]
        i += 1

    else: 
        array[k]  = array[j]
        j += 1

    k += 1  

    if i < len(leftArray):
        array[k:high] = leftArray[i, len(leftArray)] 

    else: 
        array[k:high] = rightArray[j, len(rightArray)]

def inplace (значение, низкий, высокий) 

if low < high
    mid = ((low+high)/2)
    inplace(low,mid)
    inplace(mid+1,high)
    merge(low,mid,high)

array = [29,3,73,82,68,96,36,71,59] inplace(array, 0, len (array)) print (array)

Одна из моих самых больших проблем - попытка интерпретировать наш исходный массив (S) в наш новый массив (U), как показано в псевдокоде.Может кто-нибудь объяснить, как приблизиться к разнице между первым и вторым массивом (например, перемещаться между S и U для оператора if-else)?Если бы кто-то мог оставить отзыв, это бы много значило.Спасибо.

Последняя строка предназначена для печати массива от минимальных до максимальных значений.

...