Pythonの変数のスコープについて

Pythonでマージソートのプログラムを作成しているのですが、まったくソートがされずに結果が出力されてしまいます。実行結果から変数のスコープの問題のような気がするのですが、よくわからないです。

※クラス化せずに書いたときは問題なくソートされていました。

##ソースコード

Python
1
2class mergeSortClass:
3    
4    def __init__(self,mylist):
5        self.list = mylist
6        self.left = 0
7        self.right = 0
8        self.mid = 0
9       
10    def merge(self):
11
12        INF = 1000000007
13        n1 = self.mid - self.left 
14        n2 = self.right - self.mid
15        L = [0] * (n1+1)
16        R = [0] * (n2+1)
17
18        print('n1:{}, n2:{}'.format(n1,n2))
19
20        for i in range(0,n1):
21            
22            L[i] = self.list[self.left + i]
23        
24        for i in range(0,n2):
25            print("i:{},mid:{}".format(i,self.mid))
26            R[i] = self.list[self.mid + i]
27
28        L[n1] = INF
29        R[n2] = INF
30
31        i = 0
32        j = 0
33
34        for k in range(self.left,self.right):
35            
36            if L[i] <= R[j] :
37                self.list[k] = L[i]
38                i = i + 1
39            else:
40                self.list[k] = R[j]
41                j = j + 1
42
43
44    def mergeSort(self ,left ,right):
45        self.left = left
46        self.right = right
47        self.mid = (self.left + self.right) // 2
48        print("left: {}, right: {}, mid: {}".format(self.left,self.right,self.mid))
49        if self.left + 1 < self.right:
50            self.mergeSort(self.left, self.mid)
51            self.mergeSort(self.mid , self.right)
52            self.merge()
53
54if __name__ == '__main__':
55
56    A = [7675,8,678,9,87,84,645,3,46456,24,423,4,3]
57
58    obj = mergeSortClass(A)
59    obj.mergeSort(0, len(A))
60
61    print(A)
62

実行結果

left: 0, right: 13, mid: 6
left: 0, right: 6, mid: 3
left: 0, right: 3, mid: 1
left: 0, right: 1, mid: 0
left: 0, right: 1, mid: 0
n1:0, n2:1
i:0,mid:0
left: 0, right: 1, mid: 0
n1:0, n2:1
i:0,mid:0
left: 0, right: 1, mid: 0
n1:0, n2:1
i:0,mid:0
[7675, 8, 678, 9, 87, 84, 645, 3, 46456, 24, 423, 4, 3]

shiracamus

2019/12/23 16:30 編集

回答に直接関係ないですが、クラスにする必要性ありましたか？

patama

2019/12/23 17:08

アルゴリズムをまとめたGUIアプリを作成中なので、クラスにしたほうがいいかなあと思いました。今後のためにクラスの書き方に慣れておきたいというのもありますが…

shiracamus

2019/12/23 17:18

それならば、クラスにするより、ファイルを分けてモジュールにし、importして使う方がいいと思います。

patama

2019/12/23 17:31

言われてみれば確かにただソートするだけですし、わざわざクラスにする必要なかったですね。

行動規範の内容に同意します

回答1件

ベストアンサー

再帰呼び出ししている間に self.left, self.right, self.mid がどんどん書き換えられてしまいます。
再帰中に変化してしまう情報はローカル変数に退避しておくか、引数で渡すようにしましょう。
なおしてみました。

py
1class MargeSort:
2    def __init__(self, data):
3        self.data = data;
4
5    def merge(self, left, mid, right):
6        L = self.data[left:mid]
7        R = self.data[mid:right]
8        l = r = 0
9        for d in range(left, right):
10            if r == len(R) or l < len(L) and L[l] <= R[r]:
11                self.data[d] = L[l]
12                l += 1
13            else:
14                self.data[d] = R[r]
15                r += 1
16
17
18    def sort(self, left, right):
19        mid = (left + right) // 2
20        print(f"left: {left}, right: {right}, mid: {mid}")
21        if left + 1 < right:
22            self.sort(left, mid)
23            self.sort(mid, right)
24            self.merge(left, mid, right)
25
26
27if __name__ == '__main__':
28    A = [7675, 8, 678, 9, 87, 84, 645, 3, 46456, 24, 423, 4, 3]
29    MargeSort(A).sort(0, len(A))
30    print(A)

クラスにしない方がスッキリするのでは？

python
1def merge(data, left, mid, right):
2    L = data[left:mid]
3    R = data[mid:right]
4    l = r = 0
5    for d in range(left, right):
6        if r == len(R) or l < len(L) and L[l] <= R[r]:
7            data[d] = L[l]
8            l += 1
9        else:
10            data[d] = R[r]
11            r += 1
12
13
14def mergeSort(data, left, right):
15    mid = (left + right) // 2
16    print("left: {}, right: {}, mid: {}".format(left, right, mid))
17    if left + 1 < right:
18        mergeSort(data, left, mid)
19        mergeSort(data, mid, right)
20        merge(data, left, mid, right)
21
22
23if __name__ == '__main__':
24    A = [7675, 8, 678, 9, 87, 84, 645, 3, 46456, 24, 423, 4, 3]
25    mergeSort(A, 0, len(A))
26    print(A)

名前空間を分けたいだけなら、インスタンス化しないでクラスを使う手もあります。

python
1class MargeSort:
2
3    def merge(data, left, mid, right):
4        L = data[left:mid]
5        R = data[mid:right]
6        l = r = 0
7        for d in range(left, right):
8            if r == len(R) or l < len(L) and L[l] <= R[r]:
9                data[d] = L[l]
10                l += 1
11            else:
12                data[d] = R[r]
13                r += 1
14
15
16    def sort(data, left, right):
17        mid = (left + right) // 2
18        print(f"left: {left}, right: {right}, mid: {mid}")
19        if left + 1 < right:
20            MargeSort.sort(data, left, mid)
21            MargeSort.sort(data, mid, right)
22            MargeSort.merge(data, left, mid, right)
23
24
25if __name__ == '__main__':
26    A = [7675, 8, 678, 9, 87, 84, 645, 3, 46456, 24, 423, 4, 3]
27    MargeSort.sort(A, 0, len(A))
28    print(A)