Как иметь дело с областью действия в рекурсивной функции сортировки Python

Question

Я внедряю Stooge Sort в Python и не могу понять, почему мои изменения в порядке расположения моего массива не прилипают.Другими словами, создается впечатление, что при рекурсивном просмотре ячеек происходит перестановка ячеек, но после возврата функции порядок моего массива не изменяется.Это проблема объема или какой-то другой питонизм, которого я еще не понимаю?Или мой алгоритм неверен?

import math

def StoogeSort(A):

    n = len(A)

    if (n == 2 and A[0] > A[1]):

        tmp = A[0]
        A[0] = A[1]
        A[1] = tmp 

    elif n > 2:

        m = int(math.ceil((2 * n) / 3)) 
        StoogeSort(A[0:m]) 
        StoogeSort(A[m-n:n]) 
        StoogeSort(A[0:m]) 

    return A


A = [4,2,1]
StoogeSort(A)
print "End:",A
A = [44,12,8,33,100]
StoogeSort(A)
print "End:",A

Answer 1

Проблема заключается в ваших срезах - A[0:m] и т. Д. Они не создают представление в исходном списке, а создают новые списки.

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

Answer 2

1.- Вы отправляете копии исходного массива в рекурсию, а не только части исходного массива.2.- Несмотря на то, что вы будете отправлять части исходного массива, алгоритм стоходной сортировки псевдокода не работает с частями массива, только индексы.

def StoogeSort(L, i, j):
    if L[i] > L[j]: #<-- always switching elements (not just for n=2)
        L[j],L[i]=L[i],L[j]  
    if (j - i + 1) > 2:
        t = int((j - i + 1) / 3)
        StoogeSort(L, i, j-t)  #<-- here, sending indexes.
        StoogeSort(L, i+t,j)
        StoogeSort(L, i, j-t)
    return L

>>> L = [7,8,9,5,6,4,2,1]
>>> StoogeSort(L, 0, len(L)-1)
[1, 2, 4, 5, 6, 7, 8, 9]