回答編集履歴
5
理由追加
test
CHANGED
|
@@ -1,3 +1,7 @@
|
|
|
1
|
+
再帰呼び出ししている間に self.left, self.right, self.mid がどんどん書き換えられてしまいます。
|
|
2
|
+
|
|
3
|
+
再帰中に変化してしまう情報はローカル変数に退避しておくか、引数で渡すようにしましょう。
|
|
4
|
+
|
|
1
5
|
なおしてみました。
|
|
2
6
|
|
|
3
7
|
|
4
インスタンス化しない使い方を追加
test
CHANGED
|
@@ -68,7 +68,7 @@
|
|
|
68
68
|
|
|
69
69
|
|
|
70
70
|
|
|
71
|
-
クラスにしない方がスッキリ
|
|
71
|
+
クラスにしない方がスッキリするのでは？
|
|
72
72
|
|
|
73
73
|
|
|
74
74
|
|
|
@@ -127,3 +127,69 @@
|
|
|
127
127
|
print(A)
|
|
128
128
|
|
|
129
129
|
```
|
|
130
|
+
|
|
131
|
+
|
|
132
|
+
|
|
133
|
+
名前空間を分けたいだけなら、インスタンス化しないでクラスを使う手もあります。
|
|
134
|
+
|
|
135
|
+
|
|
136
|
+
|
|
137
|
+
```python
|
|
138
|
+
|
|
139
|
+
class MargeSort:
|
|
140
|
+
|
|
141
|
+
|
|
142
|
+
|
|
143
|
+
def merge(data, left, mid, right):
|
|
144
|
+
|
|
145
|
+
L = data[left:mid]
|
|
146
|
+
|
|
147
|
+
R = data[mid:right]
|
|
148
|
+
|
|
149
|
+
l = r = 0
|
|
150
|
+
|
|
151
|
+
for d in range(left, right):
|
|
152
|
+
|
|
153
|
+
if r == len(R) or l < len(L) and L[l] <= R[r]:
|
|
154
|
+
|
|
155
|
+
data[d] = L[l]
|
|
156
|
+
|
|
157
|
+
l += 1
|
|
158
|
+
|
|
159
|
+
else:
|
|
160
|
+
|
|
161
|
+
data[d] = R[r]
|
|
162
|
+
|
|
163
|
+
r += 1
|
|
164
|
+
|
|
165
|
+
|
|
166
|
+
|
|
167
|
+
|
|
168
|
+
|
|
169
|
+
def sort(data, left, right):
|
|
170
|
+
|
|
171
|
+
mid = (left + right) // 2
|
|
172
|
+
|
|
173
|
+
print(f"left: {left}, right: {right}, mid: {mid}")
|
|
174
|
+
|
|
175
|
+
if left + 1 < right:
|
|
176
|
+
|
|
177
|
+
MargeSort.sort(data, left, mid)
|
|
178
|
+
|
|
179
|
+
MargeSort.sort(data, mid, right)
|
|
180
|
+
|
|
181
|
+
MargeSort.merge(data, left, mid, right)
|
|
182
|
+
|
|
183
|
+
|
|
184
|
+
|
|
185
|
+
|
|
186
|
+
|
|
187
|
+
if __name__ == '__main__':
|
|
188
|
+
|
|
189
|
+
A = [7675, 8, 678, 9, 87, 84, 645, 3, 46456, 24, 423, 4, 3]
|
|
190
|
+
|
|
191
|
+
MargeSort.sort(A, 0, len(A))
|
|
192
|
+
|
|
193
|
+
print(A)
|
|
194
|
+
|
|
195
|
+
```
|
3
クラス版追加
test
CHANGED
|
@@ -1,4 +1,74 @@
|
|
|
1
1
|
なおしてみました。
|
|
2
|
+
|
|
3
|
+
|
|
4
|
+
|
|
5
|
+
```py
|
|
6
|
+
|
|
7
|
+
class MargeSort:
|
|
8
|
+
|
|
9
|
+
def __init__(self, data):
|
|
10
|
+
|
|
11
|
+
self.data = data;
|
|
12
|
+
|
|
13
|
+
|
|
14
|
+
|
|
15
|
+
def merge(self, left, mid, right):
|
|
16
|
+
|
|
17
|
+
L = self.data[left:mid]
|
|
18
|
+
|
|
19
|
+
R = self.data[mid:right]
|
|
20
|
+
|
|
21
|
+
l = r = 0
|
|
22
|
+
|
|
23
|
+
for d in range(left, right):
|
|
24
|
+
|
|
25
|
+
if r == len(R) or l < len(L) and L[l] <= R[r]:
|
|
26
|
+
|
|
27
|
+
self.data[d] = L[l]
|
|
28
|
+
|
|
29
|
+
l += 1
|
|
30
|
+
|
|
31
|
+
else:
|
|
32
|
+
|
|
33
|
+
self.data[d] = R[r]
|
|
34
|
+
|
|
35
|
+
r += 1
|
|
36
|
+
|
|
37
|
+
|
|
38
|
+
|
|
39
|
+
|
|
40
|
+
|
|
41
|
+
def sort(self, left, right):
|
|
42
|
+
|
|
43
|
+
mid = (left + right) // 2
|
|
44
|
+
|
|
45
|
+
print(f"left: {left}, right: {right}, mid: {mid}")
|
|
46
|
+
|
|
47
|
+
if left + 1 < right:
|
|
48
|
+
|
|
49
|
+
self.sort(left, mid)
|
|
50
|
+
|
|
51
|
+
self.sort(mid, right)
|
|
52
|
+
|
|
53
|
+
self.merge(left, mid, right)
|
|
54
|
+
|
|
55
|
+
|
|
56
|
+
|
|
57
|
+
|
|
58
|
+
|
|
59
|
+
if __name__ == '__main__':
|
|
60
|
+
|
|
61
|
+
A = [7675, 8, 678, 9, 87, 84, 645, 3, 46456, 24, 423, 4, 3]
|
|
62
|
+
|
|
63
|
+
MargeSort(A).sort(0, len(A))
|
|
64
|
+
|
|
65
|
+
print(A)
|
|
66
|
+
|
|
67
|
+
```
|
|
68
|
+
|
|
69
|
+
|
|
70
|
+
|
|
71
|
+
クラスにしない方がスッキリしますよ。
|
|
2
72
|
|
|
3
73
|
|
|
4
74
|
|
2
PEP8準拠
test
CHANGED
|
@@ -30,25 +30,27 @@
|
|
|
30
30
|
|
|
31
31
|
|
|
32
32
|
|
|
33
|
-
def mergeSort(data
|
|
33
|
+
def mergeSort(data, left, right):
|
|
34
34
|
|
|
35
35
|
mid = (left + right) // 2
|
|
36
36
|
|
|
37
|
-
print("left: {}, right: {}, mid: {}".format(left,right,mid))
|
|
37
|
+
print("left: {}, right: {}, mid: {}".format(left, right, mid))
|
|
38
38
|
|
|
39
39
|
if left + 1 < right:
|
|
40
40
|
|
|
41
41
|
mergeSort(data, left, mid)
|
|
42
42
|
|
|
43
|
-
mergeSort(data, mid
|
|
43
|
+
mergeSort(data, mid, right)
|
|
44
44
|
|
|
45
45
|
merge(data, left, mid, right)
|
|
46
46
|
|
|
47
47
|
|
|
48
48
|
|
|
49
|
+
|
|
50
|
+
|
|
49
51
|
if __name__ == '__main__':
|
|
50
52
|
|
|
51
|
-
A = [7675,8,678,9,87,84,645,3,46456,24,423,4,3]
|
|
53
|
+
A = [7675, 8, 678, 9, 87, 84, 645, 3, 46456, 24, 423, 4, 3]
|
|
52
54
|
|
|
53
55
|
mergeSort(A, 0, len(A))
|
|
54
56
|
|
1
変数名変更
test
CHANGED
|
@@ -10,21 +10,21 @@
|
|
|
10
10
|
|
|
11
11
|
R = data[mid:right]
|
|
12
12
|
|
|
13
|
-
|
|
13
|
+
l = r = 0
|
|
14
14
|
|
|
15
|
-
for
|
|
15
|
+
for d in range(left, right):
|
|
16
16
|
|
|
17
|
-
if
|
|
17
|
+
if r == len(R) or l < len(L) and L[l] <= R[r]:
|
|
18
18
|
|
|
19
|
-
data[
|
|
19
|
+
data[d] = L[l]
|
|
20
20
|
|
|
21
|
-
|
|
21
|
+
l += 1
|
|
22
22
|
|
|
23
23
|
else:
|
|
24
24
|
|
|
25
|
-
data[
|
|
25
|
+
data[d] = R[r]
|
|
26
26
|
|
|
27
|
-
|
|
27
|
+
r += 1
|
|
28
28
|
|
|
29
29
|
|
|
30
30
|
|
|
@@ -54,6 +54,4 @@
|
|
|
54
54
|
|
|
55
55
|
print(A)
|
|
56
56
|
|
|
57
|
-
|
|
58
|
-
|
|
59
57
|
```
|