Python MergeSort - PullRequest
Новая
       23

Python MergeSort

0 голосов
/ 13 декабря 2018

Я пытаюсь реализовать сортировку слиянием Python, но мне не удается в некоторых моментах.псевдокод, который у меня есть, точен, но выглядит так, как будто он создан для другого языка.

Псевдо требует следующего
/ Объявление температуры массива размера входного массива

Я не уверен, как это возможно в Python.Во всяком случае, код ниже.Вся идея в том, что мне нужно отсортировать массив / список и вернуть отсортированный.

На данный момент, это не удается со следующим сообщением.Я бы сказал, что это из-за нового временного массива / списка, но я не уверен 

Traceback (most recent call last):  
  File "./mergesort", line 56, in <module>  
    main()  
  File "./mergesort", line 52, in main  
    mergesortbase(array)  
  File "./mergesort", line 4, in mergesortbase  
    mergesort(num, 0, len(num)-1)  
  File "./mergesort", line 10, in mergesort  
    mergesort(num, low, mid)  
  File "./mergesort", line 10, in mergesort  
    mergesort(num, low, mid)  
  File "./mergesort", line 12, in mergesort  
    merge(num, low, mid, mid+1, high)  
  File "./mergesort", line 27, in merge  
    temp[k] = a[j]  
IndexError: list assignment index out of range

Примечание: полная модернизация кода не помогает, так как мне нужно будет использовать это точное псевдокод. 

#!/usr/bin/python3.6

def mergesortbase(num):
    mergesort(num, 0, len(num)-1)


def mergesort(num, low, high):
    if low < high:
      mid = (low + high) // 2
      mergesort(num, low, mid)
      mergesort(num, mid+1, high)
      merge(num, low, mid, mid+1, high)

def merge(a, l1, u1, l2, u2):
# declare array temp of size of input array a
# Comment -- Not doable in Python to create array/list with specific size
    temp = []
    i = l1
    j = l2
    k = l1

    while (i <= u1 and j <= u2):
      if (a[i] <= a[j]):
         temp[k] = a[i]
         i = i + 1
      else:
         temp[k] = a[j]
         j = j + 1

      k = k + 1

    while ( i <= u2 ):
       temp[k] = a[i]
       k = k + 1
       i = i + 1

    while ( j <= u2 ):
       temp[k] = a[j]
       k = k + 1
       i = i + 1

    h = l1

    while ( h <= u2 ):
       a[h] = temp[h]
       h = h + 1


def main():
   array = [8, 5, 7, 1, 9, 3]
   mergesortbase(array)


if __name__ == "__main__":
  main()

Ответы [ 4 ]

0 голосов
/ 13 декабря 2018

взгляните на это и сможете получить ответы, необходимые для понимания mergesort

MergeSort

0 голосов
/ 13 декабря 2018

Мне любопытно, почему вы не просто используете встроенные средства сортировки Python, либо sort или sorted в зависимости от ваших потребностей.Вероятно, это будет более эффективно, чем то, что вы делаете сами (если вы не используете конкретную дополнительную информацию о наборе данных, что, похоже, здесь не так). может быть тем, что вы делаете это в образовательных целях, и в этом случае не стесняйтесь игнорировать этот парагаф, но я был бы упущен, не упоминая встроенный материал, если ваше намерение состоит только в сортировкенекоторые данные.

В любом случае, ваш конкретный вопрос, по-видимому, заключается в том, как "объявить темп массива размера входного массива a".

Это легко сделать с помощью оператора: 

temp = [0] * len(a)

Следующая транскрипция показывает это: 

>>> a = [1,2,3]
>>> temp = [0] * len(a)
>>> temp
[0, 0, 0]

На данный момент у вас есть: 

temp = []

, который создает список нулевого размера, за которым следует: 

temp[k] = a[i]

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

Кроме того, ваше фактическое слияние имеет недостаткив том, что вы используете неправильные переменные для обработки массивов.Вы вполне логически связали определенные элементы, такие как i с первым разделом массива и j со вторым, но затем нарушите это: 

while ( i <= u2 ):  # i and u1 should be associated: while i <= u1:
   temp[k] = a[i]   # (no need for '()' in Python conditions by the way).
   k = k + 1
   i = i + 1

while ( j <= u2 ):
   temp[k] = a[j]
   k = k + 1
   i = i + 1        # j and u2 should be associated: j = j + 1

Даже после того, как вы исправите массивсоздание, вполне вероятно, что второй цикл выше вызовет проблему.Он будет работать вечно (или до исключения, в зависимости от того, что наступит раньше), потому что вы проверяете j, но никогда не меняете его.Однако оба элемента , указанные выше, неверны, поэтому их следует исправить.

Как только я сделаю массив правильного размера, внесу эти два изменения и распечатаю массив до и после сортировки, кажется,немного лучше: 

[8, 5, 7, 1, 9, 3]
[1, 3, 5, 7, 8, 9]
0 голосов
/ 13 декабря 2018

Три ошибки в вашем коде

  1. temp не инициализируется ни к какому размеру, поэтому k всегда дает list assignment index out of range

  2. Второй цикл while длядобавление оставшихся элементов l1 к u1 должно выполняться только до тех пор, пока u1 не станет u2:

  3. В третьем цикле для добавления оставшихся элементов от l2 к u2 необходимо увеличить j вместо i. 

    def merge(a, l1, u1, l2, u2):
    temp = [0]*len(a)
    i = l1
    j = l2
    k = l1
    while (i <= u1 and j <= u2):
        if (a[i] <= a[j]):
            temp[k] = a[i]
            i = i + 1
        else:
            temp[k] = a[j]
            j = j + 1

        k = k + 1
    while ( i <= u1 ):
        temp[k] = a[i]
        k = k + 1
        i = i + 1
    while ( j <= u2 ):
        temp[k] = a[j]
        k = k + 1
        j = j + 1

    h = l1

    while ( h <= u2 ):  
        a[h] = temp[h]
        h = h + 1
0 голосов
/ 13 декабря 2018

Вы можете просто сделать копию входного массива?

temp = a.copy ()

Это будет тот же самый размер.

Если вы хотите инициализировать некоторыеоцените все элементы в temp, используйте что-то вроде:

temp = [0] * len (a)

...