Bottom Up MergeSort с использованием Python

Question

Я потратил бесчисленные часы, пытаясь это сделать. Может ли кто-нибудь указать на мою ошибку?

a это просто список, tmp является пустым списком размера len(a)

z в основном len(a)

a = [6,5,4,3,2,1] print 'unsorted:',a z = len(a) tmp = range(len(a))

Вот мой род функции:

def sort(a,tmp): 
     width=1 
     while(width<z): 
       p=0 
       while(p<z): 
         left =p 
         middle = p+width 
         right = p+2*width 
         merge(a,left,middle,right,tmp) 
         p = p+2*width 
       t=0   
       while(t<z): 
        a[t]=tmp[t] 
        t=t+1 
       width=width*2 
       print '\n' 

и здесь сливаются функция:

def merge(a,iLeft,iMiddle,iRight,tmp): 
     i = iLeft 
     j = iMiddle 
     k = iLeft 
     print iLeft,iMiddle,iRight,'[',i,j,k,']' 
     #print i ,j, k,'\n\n' 

     while(i<iMiddle or j<iRight): 
       if(i<iMiddle and j<iRight): 
         if(a[i]<a[j]): 
           tmp[k]=a[i] 
           i += 1 
           k += 1 
         else: 
           tmp[k]=a[j] 
           j += 1 
           k += 1 

       elif (i==iMiddle): 
         tmp[k] = a[j] 
         j += 1 
         k += 1 
       elif (j==iRight): 
         tmp[k]= a[i] 
         i += 1 
         k += 1 

[Эта визуализация] может помочь. Я до сих пор не знаю, почему это так.

Я не уверен, где я ошибаюсь? Это отступы или цикл?

Output :: 
unsorted: [6, 5, 4, 3, 2, 1] 
0 1 2 [ 0 1 0 ] 
2 3 4 [ 2 3 2 ] 
4 5 6 [ 4 5 4 ] 


0 2 4 [ 0 2 0 ] 
4 6 8 [ 4 6 4 ] 
Traceback (most recent call last): 
    File "BUmer.py", line 45, in <module> 
    sort(a,tmp) 
    File "BUmer.py", line 14, in sort 
    merge(a,left,middle,right,tmp) 
    File "BUmer.py", line 27, in merge 
    if(a[i]<a[j]): 
IndexError: list index out of range 

This visualization может помочь. Я до сих пор не знаю, почему это происходит.

Answer 1

Хотя это был доблестным усилие основной ошибки вы сделали был с подходом управления потоком вложенным - человеческий разум может обрабатывать только так много вложенных while -loops. Кроме того, тот факт, что функция слияния изменяет aна месте, затрудняет выяснение того, что происходит. Даже если у вас есть удивительный ум, который может отслеживать все эти действия, сохранить энергию мозга для решения проблемы, а не контроля потока!

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

Вот еще один подход к сортировке слиянием, который пытается сохранить вещи более плоские и четко:

def merge(merged, a, b): 

    if a and b: 
     return merge(merged + [min(a[0], b[0])], 
        a[1:] if min(a[0], b[0]) == a[0] else a, 
        b[1:] if min(a[0], b[0]) == b[0] and not a[0] == b[0] else b 
        ) 

    elif a and not b and len(a) > 1: 
     return merged + merge([], a[:len(a)/2], a[len(a)/2:]) 
    elif a and not b: 
     return merged + a 
    elif b and not a and len(b) > 1: 
     return merged + merge([], b[:len(b)/2], b[len(b)/2:]) 
    elif b and not a: 
     return merged + b 
    else: 
     return merged 

def mergesort(lst): 

    if not lst: 
     return [] 
    elif len(lst) == 2: 
     return [min(lst), max(lst)] 
    elif len(lst) == 1: 
     return lst 
    else: 
     return merge([], mergesort(lst[:len(lst)/2]), mergesort(lst[len(lst)/2:])) 

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

http://www.oreilly.com/programming/free/files/functional-programming-python.pdf

Реализовать это может быть не точный ответ, который вы ищете, но я надеюсь, что это помогает.

Answer 2

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

Программа отлично работает для массивов, длина которых равна = 0. Все остальное дает массив из исключения индекса. Я должен был реализовать блок try-except для обработки этих вещей.

В любом случае, теперь я знаю.Благодаря snakes_on_a_keyboard для руководства по функциональному программированию.

Причина, по которой я не раскрываю никаких подробностей этой проблемы, заключается в том, что snakes_on_a_keyboard уже предоставила гораздо лучшее и элегантное решение.