回答編集履歴
4
追記
test
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
|
|
3
3
|
|
|
4
4
|
|
|
5
|
-
a. `Thread`クラスを継承(extends)するときは、`run`メソッドをオーバーロード(オーバーライドではないです）しないでください。
|
|
5
|
+
a. `Thread`クラスを継承(extends)するときは、`run`メソッドをオーバーロード(オーバーライドではないです）しないでください。これが質問文のスレッド終了のメッセージが出ない原因です。
|
|
6
6
|
|
|
7
7
|
```diff
|
|
8
8
|
|
3
追記
test
CHANGED
|
@@ -99,3 +99,23 @@
|
|
|
99
99
|
|
|
100
100
|
|
|
101
101
|
```
|
|
102
|
+
|
|
103
|
+
e. `pivot`値の選択がオーバーフローする可能性があります。これはある整数値の範囲を表すのに、符号付きの数値型だとその範囲を表せないというのが原因です。
|
|
104
|
+
|
|
105
|
+
```diff
|
|
106
|
+
|
|
107
|
+
-int pivot = array[(currentLeft + currentRight) / 2];
|
|
108
|
+
|
|
109
|
+
+int pivot = array[currentLeft + ((currentRight- currentLeft) / 2)];
|
|
110
|
+
|
|
111
|
+
```
|
|
112
|
+
|
|
113
|
+
◇参考情報
|
|
114
|
+
|
|
115
|
+
[Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken](https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html)
|
|
116
|
+
|
|
117
|
+
|
|
118
|
+
|
|
119
|
+
f. `private static int[] quick(int[] n, int left, int right){` で再帰呼出しを行っていますが、多分大丈夫だと思いますが、スタック・オーバーフローする可能性があるので、再帰呼出しは避けたほうが無難です。
|
|
120
|
+
|
|
121
|
+
※データ数によって実行時エラーが発生する可能性があるプログラムは個人的に好きではないというのがあります。
|
2
追記
test
CHANGED
|
@@ -42,29 +42,9 @@
|
|
|
42
42
|
|
|
43
43
|
```
|
|
44
44
|
|
|
45
|
-
```Java
|
|
46
45
|
|
|
47
|
-
for(int i = n.length-1; i>0; i--){
|
|
48
46
|
|
|
49
|
-
|
|
50
|
-
|
|
51
|
-
if (index == i) continue;
|
|
52
|
-
|
|
53
|
-
int temp = n[i];
|
|
54
|
-
|
|
55
|
-
n[i] = n[index];
|
|
56
|
-
|
|
57
|
-
n[index] = temp;
|
|
58
|
-
|
|
59
|
-
}
|
|
60
|
-
|
|
61
|
-
```
|
|
62
|
-
|
|
63
|
-
c. `babble`クラスと`quick`クラスに同じ変数`n`を参照しています。
|
|
64
|
-
|
|
65
|
-
スレッド間でのデータ競合が起こるため、
|
|
66
|
-
|
|
67
|
-
n.clone()でコピーするか、[Arrays.copyOf](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Arrays.html#copyOf-boolean:A-int-)を行ってください。
|
|
47
|
+
c. `babble`クラスと`quick`クラスに同じ変数`n`を参照しています。スレッド間でのデータ競合が起こるため、n.clone()でコピーするか、[Arrays.copyOf](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Arrays.html#copyOf-int:A-int-)を行ってください。よーするに複数スレッドから同じ変数に対して、排他制御（ロック）をしないで、変更してはダメということです。
|
|
68
48
|
|
|
69
49
|
```Java
|
|
70
50
|
|
|
@@ -84,9 +64,13 @@
|
|
|
84
64
|
|
|
85
65
|
babble b = new babble(n.clone());
|
|
86
66
|
|
|
67
|
+
//中略
|
|
68
|
+
|
|
69
|
+
quick q = new quick(n.clone());
|
|
70
|
+
|
|
71
|
+
//もしくはbabbleクラスquickクラスのコンストラクタ内で引数に対してclone()を呼び出す。
|
|
72
|
+
|
|
87
73
|
```
|
|
88
|
-
|
|
89
|
-
|
|
90
74
|
|
|
91
75
|
---
|
|
92
76
|
|
1
追記
test
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
|
|
3
3
|
|
|
4
4
|
|
|
5
|
-
|
|
5
|
+
a. `Thread`クラスを継承(extends)するときは、`run`メソッドをオーバーロード(オーバーライドではないです）しないでください。
|
|
6
6
|
|
|
7
7
|
```diff
|
|
8
8
|
|
|
@@ -12,15 +12,13 @@
|
|
|
12
12
|
|
|
13
13
|
```
|
|
14
14
|
|
|
15
|
-
|
|
15
|
+
b. quick クラス、babbleクラスともにコンストラクタで渡された引数nを無視しています。
|
|
16
16
|
|
|
17
17
|
```Java
|
|
18
18
|
|
|
19
19
|
quick(int[] n){ // 引数 nに対して以下ブロックで何もしていない。
|
|
20
20
|
|
|
21
21
|
System.out.println("クイックソートスタート");
|
|
22
|
-
|
|
23
|
-
|
|
24
22
|
|
|
25
23
|
}
|
|
26
24
|
|
|
@@ -43,3 +41,77 @@
|
|
|
43
41
|
}
|
|
44
42
|
|
|
45
43
|
```
|
|
44
|
+
|
|
45
|
+
```Java
|
|
46
|
+
|
|
47
|
+
for(int i = n.length-1; i>0; i--){
|
|
48
|
+
|
|
49
|
+
int index = (int)(Math.random()*(i+1));
|
|
50
|
+
|
|
51
|
+
if (index == i) continue;
|
|
52
|
+
|
|
53
|
+
int temp = n[i];
|
|
54
|
+
|
|
55
|
+
n[i] = n[index];
|
|
56
|
+
|
|
57
|
+
n[index] = temp;
|
|
58
|
+
|
|
59
|
+
}
|
|
60
|
+
|
|
61
|
+
```
|
|
62
|
+
|
|
63
|
+
c. `babble`クラスと`quick`クラスに同じ変数`n`を参照しています。
|
|
64
|
+
|
|
65
|
+
スレッド間でのデータ競合が起こるため、
|
|
66
|
+
|
|
67
|
+
n.clone()でコピーするか、[Arrays.copyOf](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Arrays.html#copyOf-boolean:A-int-)を行ってください。
|
|
68
|
+
|
|
69
|
+
```Java
|
|
70
|
+
|
|
71
|
+
babble b = new babble(n);
|
|
72
|
+
|
|
73
|
+
b.start();
|
|
74
|
+
|
|
75
|
+
|
|
76
|
+
|
|
77
|
+
quick q = new quick(n);
|
|
78
|
+
|
|
79
|
+
q.start();
|
|
80
|
+
|
|
81
|
+
```
|
|
82
|
+
|
|
83
|
+
```Java
|
|
84
|
+
|
|
85
|
+
babble b = new babble(n.clone());
|
|
86
|
+
|
|
87
|
+
```
|
|
88
|
+
|
|
89
|
+
|
|
90
|
+
|
|
91
|
+
---
|
|
92
|
+
|
|
93
|
+
ここから余談です。
|
|
94
|
+
|
|
95
|
+
d. 以下のシャッフル部分は[Collections#shuffle](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Collections.html#shuffle-java.util.List-)が使えます。
|
|
96
|
+
|
|
97
|
+
```Java
|
|
98
|
+
|
|
99
|
+
//シャッフル
|
|
100
|
+
|
|
101
|
+
for(int i = n.length-1; i>0; i--){
|
|
102
|
+
|
|
103
|
+
int index = (int)(Math.random()*(i+1));
|
|
104
|
+
|
|
105
|
+
if (index == i) continue;
|
|
106
|
+
|
|
107
|
+
int temp = n[i];
|
|
108
|
+
|
|
109
|
+
n[i] = n[index];
|
|
110
|
+
|
|
111
|
+
n[index] = temp;
|
|
112
|
+
|
|
113
|
+
}
|
|
114
|
+
|
|
115
|
+
|
|
116
|
+
|
|
117
|
+
```
|