質問編集履歴
2
誤字修正
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -37,10 +37,10 @@
|
|
|
37
37
|
while (left < right) {
|
|
38
38
|
int i = partition(target, left, right);
|
|
39
39
|
if( i - left <= right - i ){ // The left interval is shorter.
|
|
40
|
-
|
|
40
|
+
randomQuickSort1(target, left, i-1);
|
|
41
41
|
left=i+1;
|
|
42
42
|
}else{ // The right interval is shorter.
|
|
43
|
-
|
|
43
|
+
randomQuickSort1(target, i+1, right);
|
|
44
44
|
right=i-1;
|
|
45
45
|
}
|
|
46
46
|
}
|
1
一般的なランダムクイックソートに追記
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -58,6 +58,29 @@
|
|
|
58
58
|
|
|
59
59
|
#### 一般的なランダムクイックソート
|
|
60
60
|
```C
|
|
61
|
+
// 変更前のpartition関数
|
|
62
|
+
int partition(int* target, int left, int right) {
|
|
63
|
+
// Select a number between left and right at random.
|
|
64
|
+
int random = left + rand() % (right - left + 1);
|
|
65
|
+
// Exchange target[right] and target[random].
|
|
66
|
+
int tmp = target[right]; target[right] = target[random]; target[random] = tmp;
|
|
67
|
+
int pivot = target[right];
|
|
68
|
+
int i = left-1; // i scans the array from the left.
|
|
69
|
+
int j = right; // j scans the array from the right.
|
|
70
|
+
for (;;) {
|
|
71
|
+
// Move from the left until hitting a value no less than the pivot.
|
|
72
|
+
for(i++; target[i] < pivot; i++){}
|
|
73
|
+
// Move from the right until hitting a value no greater than the pivot.
|
|
74
|
+
for(j--; pivot < target[j] && i < j; j--){}
|
|
75
|
+
if (i >= j) break;
|
|
76
|
+
// Exchange target[i] and target[j].
|
|
77
|
+
tmp = target[i]; target[i] = target[j]; target[j] = tmp;
|
|
78
|
+
}
|
|
79
|
+
// Exchange target[i] and target[right].
|
|
80
|
+
tmp = target[i]; target[i] = target[right]; target[right] = tmp;
|
|
81
|
+
return i;
|
|
82
|
+
}
|
|
83
|
+
|
|
61
84
|
void randomQuickSort(int* target, int left, int right ) {
|
|
62
85
|
if (left < right) {
|
|
63
86
|
int i = partition(target, left, right); // i: Position of the pivot.
|