teratail
回答率
85.48%
質問するログイン新規登録
トップPython 3.xに関する質問Pythonの挿入ソートにおけるバグ

編集履歴

回答編集履歴

6

誤字修正

2019/03/21 19:39

投稿

nico25
nico25

スコア830

test CHANGED
@@ -70,23 +70,13 @@
70
70
 
71
71
 
72
72
 
73
- ### 2.2. print 関数で出力
74
-
75
- 最後の結果だけでなく、途中結果についても `print(A)` で表示して、自分が意図していない動作を **しはじめた** 箇所を突き止めるといいかなと思います。出力結果だけでデバックは、結構辛いかなと感じます。とは言え、途中結果を出力してもわからないものは、わからないのですが笑
76
-
77
-
78
-
79
-
80
-
81
- ### 2.3. reversed 関数
73
+ ### 2.2. reversed 関数
82
74
 
83
75
  以下の２つは等価です。
84
76
 
85
77
  ```python
86
78
 
87
- range(i - 1, -1, -1)
79
+ range(i - 1, -1, -1) == reversed(range(i))
88
-
89
- reversed(range(i))
90
80
 
91
81
  ```
92
82
 
@@ -94,41 +84,41 @@
94
84
 
95
85
 
96
86
 
97
- ### 2.4. 入れ替えの書き方
87
+ ### 2.3. 入れ替えの書き方
98
88
 
99
89
  変数をいれかえるには
100
90
 
101
91
  ```python
102
92
 
103
- # 挿入するために配列のtmpの１つ前から挿入した挿入したい
93
+ # 挿入するために配列のtmpの１つ前から挿入した挿入したい
104
94
 
105
- # exchangeindexの要素を１つずつ後ろに移動させる
95
+ # exchangeindexの要素を１つずつ後ろに移動させる
106
96
 
107
- for k in range(i+1, -1, -1):
97
+ for k in range(i+1, -1, -1):
108
98
 
109
- A[k] = A[k-1]
99
+ A[k] = A[k-1]
110
100
 
111
- A[j] = tmp
101
+ A[j] = tmp
112
102
 
113
103
  ```
114
104
 
115
105
 
116
106
 
117
- #### 2.4.1. 書き方 1
107
+ #### 2.3.1. 書き方 1
118
108
 
119
109
  ```python
120
110
 
121
- A[i] = A[j]
111
+ A[i] = A[j]
122
112
 
123
- A[j] = tmp
113
+ A[j] = tmp
124
114
 
125
- i = j
115
+ i = j
126
116
 
127
117
  ```
128
118
 
129
119
 
130
120
 
131
- #### 2.4.2. 書き方 2
121
+ #### 2.3.2. 書き方 2
132
122
 
133
123
  Python ではこのように書けます。
134
124
 

5

誤字修正

2019/03/21 19:39

投稿

nico25
nico25

スコア830

test CHANGED
@@ -86,7 +86,7 @@
86
86
 
87
87
  range(i - 1, -1, -1)
88
88
 
89
- reversed(i)
89
+ reversed(range(i))
90
90
 
91
91
  ```
92
92
 

4

誤字修正

2019/03/21 19:01

投稿

nico25
nico25

スコア830

test CHANGED
@@ -140,4 +140,4 @@
140
140
 
141
141
 
142
142
 
143
- * [Python のPython の代入の色々な書き方](https://python.ms/sub/misc/assignment/)
143
+ * [Python の代入の色々な書き方](https://python.ms/sub/misc/assignment/)

3

誤字修正

2019/03/21 17:58

投稿

nico25
nico25

スコア830

test CHANGED
@@ -1,15 +1,3 @@
1
- 挿入ソート自体はもっと短く書けます。
2
-
3
- * [Python の挿入ソート](https://python.ms/sub/algorithm/sort/insertion/)
4
-
5
-
6
-
7
-
8
-
9
-
10
-
11
-
12
-
13
1
  ## 1. 修正したコード
14
2
 
15
3
  なるべく元のコードに沿う形で書き換えました。
@@ -72,7 +60,17 @@
72
60
 
73
61
  ## 2. 改善点
74
62
 
63
+ ### 2.1. break 文
64
+
65
+ 挿入ソートには break 文が必要です。break 文がないとバブルソートと、ある意味同じものになってしまいます。それについては以下で書きました。
66
+
67
+ * [Python の挿入ソート](https://python.ms/sub/algorithm/sort/insertion/)
68
+
69
+
70
+
71
+
72
+
75
- ### 2.1. print 関数で出力
73
+ ### 2.2. print 関数で出力
76
74
 
77
75
  最後の結果だけでなく、途中結果についても `print(A)` で表示して、自分が意図していない動作を **しはじめた** 箇所を突き止めるといいかなと思います。出力結果だけでデバックは、結構辛いかなと感じます。とは言え、途中結果を出力してもわからないものは、わからないのですが笑
78
76
 
@@ -80,7 +78,7 @@
80
78
 
81
79
 
82
80
 
83
- ### 2.2. reversed 関数
81
+ ### 2.3. reversed 関数
84
82
 
85
83
  以下の２つは等価です。
86
84
 
@@ -96,7 +94,7 @@
96
94
 
97
95
 
98
96
 
99
- ### 2.3. 入れ替えの書き方
97
+ ### 2.4. 入れ替えの書き方
100
98
 
101
99
  変数をいれかえるには
102
100
 
@@ -116,7 +114,7 @@
116
114
 
117
115
 
118
116
 
119
- #### 2.3.1. 書き方 1
117
+ #### 2.4.1. 書き方 1
120
118
 
121
119
  ```python
122
120
 
@@ -130,7 +128,7 @@
130
128
 
131
129
 
132
130
 
133
- #### 2.3.2. 書き方 2
131
+ #### 2.4.2. 書き方 2
134
132
 
135
133
  Python ではこのように書けます。
136
134
 

2

誤字修正

2019/03/21 17:58

投稿

nico25
nico25

スコア830

test CHANGED
@@ -45,6 +45,10 @@
45
45
  A[j] = tmp
46
46
 
47
47
  i = j
48
+
49
+ else:
50
+
51
+ break # <- 挿入ソートにはこの break 文がないといけない。
48
52
 
49
53
 
50
54
 

1

誤字

2019/03/21 17:54

投稿

nico25
nico25

スコア830

test CHANGED
@@ -1,69 +1,141 @@
1
- 部分的な修正でいけるかなと思ったのですが、
1
+ 挿入ソート自体はもっと短く書けます。
2
2
 
3
- O(n^2) なのに for 文が 3 つも重なっているので、全面的に書き換えたものを提示します。
4
-
5
- また `range(n-1, -1, -1)` も良いのですが `reversed(range(n))` も便利です。
3
+ * [Python の挿入ソート](https://python.ms/sub/algorithm/sort/insertion/)
6
4
 
7
5
 
8
6
 
7
+
8
+
9
+
10
+
11
+
12
+
13
+ ## 1. 修正したコード
14
+
15
+ なるべく元のコードに沿う形で書き換えました。
16
+
9
17
  ```python
10
18
 
11
- def insertion_sort(lst):
19
+ # sort(A, i) 関数は無くしました。
12
20
 
13
- n = len(lst)
14
21
 
15
- for i in range(n):
16
22
 
17
- for j in reversed(range(i)):
23
+ def solution(A):
18
24
 
19
- if lst[j] > lst[i]:
25
+ # for i in range(len(A)-1):
20
26
 
21
- print(lst, j, i)
27
+ for i in range(len(A)):
22
28
 
29
+ # tmp = A[i + 1]
30
+
23
- lst[j], lst[i] = lst[i], lst[j]
31
+ for j in range(i - 1, -1, -1):
32
+
33
+ tmp = A[i]
34
+
35
+ # if A[j] < tmp:
36
+
37
+ if A[j] > tmp:
38
+
39
+ # for k in range(i + 1, -1, -1):
40
+
41
+ # A[k] = A[k - 1] <- この操作で 8 が大量に生成されていました。
42
+
43
+ A[i] = A[j]
44
+
45
+ A[j] = tmp
24
46
 
25
47
  i = j
26
48
 
27
- else:
28
-
29
- break
30
49
 
31
50
 
51
+ A = [1,3,2,8]
32
52
 
33
- lst = [9981, 3333, 5123, 1243, 7412]
53
+ solution(A)
34
54
 
35
- insertion_sort(lst)
55
+ print(A)
36
56
 
37
- print(lst)
38
-
39
- ```
40
-
41
- ```
42
-
43
- >>> lst = [9981, 3333, 5123, 1243, 7412]
44
-
45
- >>> insertion_sort(lst)
46
-
47
- [9981, 3333, 5123, 1243, 7412] 0 1
48
-
49
- [3333, 9981, 5123, 1243, 7412] 1 2
50
-
51
- [3333, 5123, 9981, 1243, 7412] 2 3
52
-
53
- [3333, 5123, 1243, 9981, 7412] 1 2
54
-
55
- [3333, 1243, 5123, 9981, 7412] 0 1
56
-
57
- [1243, 3333, 5123, 9981, 7412] 3 4
58
-
59
- >>> print(lst)
60
-
61
- [1243, 3333, 5123, 7412, 9981]
57
+ # [1, 2, 3, 8]
62
-
63
- >>>
64
58
 
65
59
  ```
66
60
 
67
61
 
68
62
 
63
+
64
+
65
+
66
+
67
+
68
+
69
+ ## 2. 改善点
70
+
71
+ ### 2.1. print 関数で出力
72
+
73
+ 最後の結果だけでなく、途中結果についても `print(A)` で表示して、自分が意図していない動作を **しはじめた** 箇所を突き止めるといいかなと思います。出力結果だけでデバックは、結構辛いかなと感じます。とは言え、途中結果を出力してもわからないものは、わからないのですが笑
74
+
75
+
76
+
77
+
78
+
79
+ ### 2.2. reversed 関数
80
+
81
+ 以下の２つは等価です。
82
+
83
+ ```python
84
+
85
+ range(i - 1, -1, -1)
86
+
87
+ reversed(i)
88
+
89
+ ```
90
+
91
+
92
+
93
+
94
+
95
+ ### 2.3. 入れ替えの書き方
96
+
97
+ 変数をいれかえるには
98
+
99
+ ```python
100
+
101
+ # 挿入するために配列のtmpの１つ前から挿入した挿入したい
102
+
103
+ # exchangeindexの要素を１つずつ後ろに移動させる
104
+
105
+ for k in range(i+1, -1, -1):
106
+
107
+ A[k] = A[k-1]
108
+
109
+ A[j] = tmp
110
+
111
+ ```
112
+
113
+
114
+
115
+ #### 2.3.1. 書き方 1
116
+
117
+ ```python
118
+
119
+ A[i] = A[j]
120
+
121
+ A[j] = tmp
122
+
123
+ i = j
124
+
125
+ ```
126
+
127
+
128
+
129
+ #### 2.3.2. 書き方 2
130
+
131
+ Python ではこのように書けます。
132
+
133
+ ```python
134
+
135
+ A[i], A[j] = A[j], A[i]
136
+
137
+ ```
138
+
139
+
140
+
69
- * [Python の挿入ソート](https://python.ms/sub/algorithm/sort/insertion/)
141
+ * [Python のPython の代入の色々な書き方](https://python.ms/sub/misc/assignment/)