質問編集履歴
2
誤字修正
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -76,13 +76,13 @@
|
|
|
76
76
|
|
|
77
77
|
if( i - left <= right - i ){ // The left interval is shorter.
|
|
78
78
|
|
|
79
|
-
randomQuickSort
|
|
79
|
+
randomQuickSort1(target, left, i-1);
|
|
80
80
|
|
|
81
81
|
left=i+1;
|
|
82
82
|
|
|
83
83
|
}else{ // The right interval is shorter.
|
|
84
84
|
|
|
85
|
-
randomQuickSort
|
|
85
|
+
randomQuickSort1(target, i+1, right);
|
|
86
86
|
|
|
87
87
|
right=i-1;
|
|
88
88
|
|
1
一般的なランダムクイックソートに追記
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -118,6 +118,52 @@
|
|
|
118
118
|
|
|
119
119
|
```C
|
|
120
120
|
|
|
121
|
+
// 変更前のpartition関数
|
|
122
|
+
|
|
123
|
+
int partition(int* target, int left, int right) {
|
|
124
|
+
|
|
125
|
+
// Select a number between left and right at random.
|
|
126
|
+
|
|
127
|
+
int random = left + rand() % (right - left + 1);
|
|
128
|
+
|
|
129
|
+
// Exchange target[right] and target[random].
|
|
130
|
+
|
|
131
|
+
int tmp = target[right]; target[right] = target[random]; target[random] = tmp;
|
|
132
|
+
|
|
133
|
+
int pivot = target[right];
|
|
134
|
+
|
|
135
|
+
int i = left-1; // i scans the array from the left.
|
|
136
|
+
|
|
137
|
+
int j = right; // j scans the array from the right.
|
|
138
|
+
|
|
139
|
+
for (;;) {
|
|
140
|
+
|
|
141
|
+
// Move from the left until hitting a value no less than the pivot.
|
|
142
|
+
|
|
143
|
+
for(i++; target[i] < pivot; i++){}
|
|
144
|
+
|
|
145
|
+
// Move from the right until hitting a value no greater than the pivot.
|
|
146
|
+
|
|
147
|
+
for(j--; pivot < target[j] && i < j; j--){}
|
|
148
|
+
|
|
149
|
+
if (i >= j) break;
|
|
150
|
+
|
|
151
|
+
// Exchange target[i] and target[j].
|
|
152
|
+
|
|
153
|
+
tmp = target[i]; target[i] = target[j]; target[j] = tmp;
|
|
154
|
+
|
|
155
|
+
}
|
|
156
|
+
|
|
157
|
+
// Exchange target[i] and target[right].
|
|
158
|
+
|
|
159
|
+
tmp = target[i]; target[i] = target[right]; target[right] = tmp;
|
|
160
|
+
|
|
161
|
+
return i;
|
|
162
|
+
|
|
163
|
+
}
|
|
164
|
+
|
|
165
|
+
|
|
166
|
+
|
|
121
167
|
void randomQuickSort(int* target, int left, int right ) {
|
|
122
168
|
|
|
123
169
|
if (left < right) {
|