/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static void quick_sort(int[] d, int left, int right) {
if (left>=right) {
return;
}
int p = d[(left+right)/2];
int l = left, r = right, tmp;
while(l<=r) {
while(d[l] < p) { l++; }
while(d[r] > p) { r--; }
if (l<=r) {
tmp = d[l]; d[l] = d[r]; d[r] = tmp;
l++; r--;
}
}
quick_sort(d, left, r); // ピボットより左側をクイックソート
quick_sort(d, l, right); // ピボットより右側をクイックソート
}
// 配列内のデータ列を表示する
static void print_data(int[] d) {
for(int i
= 0; i
< d.
length; i
++) System.
out.
print(d
[i
] + " "); }
public static void main
(String[] args
) { int[] data = {5, 10, 3, 7, 8, 1, 9, 2};
print_data(data);
quick_sort(data, 0, data.length-1);
print_data(data);
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKICAgIHN0YXRpYyB2b2lkIHF1aWNrX3NvcnQoaW50W10gZCwgaW50IGxlZnQsIGludCByaWdodCkgewogICAgICAgIGlmIChsZWZ0Pj1yaWdodCkgewogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogICAgICAgIGludCBwID0gZFsobGVmdCtyaWdodCkvMl07CiAgICAgICAgaW50IGwgPSBsZWZ0LCByID0gcmlnaHQsIHRtcDsKICAgICAgICB3aGlsZShsPD1yKSB7CiAgICAgICAgICAgIHdoaWxlKGRbbF0gPCBwKSB7IGwrKzsgfQogICAgICAgICAgICB3aGlsZShkW3JdID4gcCkgeyByLS07IH0KICAgICAgICAgICAgaWYgKGw8PXIpIHsKICAgICAgICAgICAgICAgIHRtcCA9IGRbbF07IGRbbF0gPSBkW3JdOyBkW3JdID0gdG1wOwogICAgICAgICAgICAgICAgbCsrOyByLS07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcXVpY2tfc29ydChkLCBsZWZ0LCByKTsgIC8vIOODlOODnOODg+ODiOOCiOOCiuW3puWBtOOCkuOCr+OCpOODg+OCr+OCveODvOODiAogICAgICAgIHF1aWNrX3NvcnQoZCwgbCwgcmlnaHQpOyAvLyDjg5Tjg5zjg4Pjg4jjgojjgorlj7PlgbTjgpLjgq/jgqTjg4Pjgq/jgr3jg7zjg4gKICAgIH0KICAgIC8vIOmFjeWIl+WGheOBruODh+ODvOOCv+WIl+OCkuihqOekuuOBmeOCiwogICAgc3RhdGljIHZvaWQgcHJpbnRfZGF0YShpbnRbXSBkKSB7CiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IGQubGVuZ3RoOyBpKyspIFN5c3RlbS5vdXQucHJpbnQoZFtpXSArICIgIik7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCk7CiAgICB9CiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgaW50W10gZGF0YSA9IHs1LCAxMCwgMywgNywgOCwgMSwgOSwgMn07CiAgICAgICAgcHJpbnRfZGF0YShkYXRhKTsKICAgICAgICBxdWlja19zb3J0KGRhdGEsIDAsIGRhdGEubGVuZ3RoLTEpOwogICAgICAgIHByaW50X2RhdGEoZGF0YSk7CiAgICB9Cn0=