import java.util.Random;
public class Main
{
public static void main
(String[] args
) {
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++)
{
arr[i] = r.nextInt(1000);
}
quickSort(arr, 0, arr.length-1);
for (int i:arr)
{
}
}
public static void quickSort(int[] a, int left, int right) {
int index = partition(a, left, right);
if (left < index - 1)
quickSort(a, left, index);
if (index < right)
quickSort(a, index + 1, right);
}
private static int partition (int[] a, int left, int right) {
int i = left - 1;
int j = right + 1;
int pivot = a[left];
while (i < j) {
i++;
while (a[i] < pivot)
i++;
j--;
while (a[j] > pivot)
j--;
if (i < j)
swap (a, i--, j++);
}
return i;
}
private static void swap (int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
aW1wb3J0IGphdmEudXRpbC5SYW5kb207CgpwdWJsaWMgY2xhc3MgTWFpbgp7CiAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpCiAgIHsKICAgICAgaW50W10gYXJyID0gbmV3IGludFsxMF07CiAgICAgIFJhbmRvbSByID0gbmV3IFJhbmRvbSgpOwogICAgICBmb3IgKGludCBpID0gMDsgaSA8IGFyci5sZW5ndGg7IGkrKykKICAgICAgewogICAgICAgICBhcnJbaV0gPSByLm5leHRJbnQoMTAwMCk7CiAgICAgIH0KICAgICAgcXVpY2tTb3J0KGFyciwgMCwgYXJyLmxlbmd0aC0xKTsKICAgICAgZm9yIChpbnQgaTphcnIpCiAgICAgIHsKICAgICAgICAgU3lzdGVtLm91dC5wcmludChpKyIgIik7CiAgICAgIH0KICAgICAgU3lzdGVtLm91dC5wcmludGxuKCk7CiAgIH0KCnB1YmxpYyBzdGF0aWMgdm9pZCBxdWlja1NvcnQoaW50W10gYSwgaW50IGxlZnQsIGludCByaWdodCkgewoKICAgIGludCBpbmRleCA9IHBhcnRpdGlvbihhLCBsZWZ0LCByaWdodCk7CiAgICBpZiAobGVmdCA8IGluZGV4IC0gMSkKICAgICAgcXVpY2tTb3J0KGEsIGxlZnQsIGluZGV4KTsKICAgIGlmIChpbmRleCA8IHJpZ2h0KQogICAgICBxdWlja1NvcnQoYSwgaW5kZXggKyAxLCByaWdodCk7Cn0KCnByaXZhdGUgc3RhdGljIGludCBwYXJ0aXRpb24gKGludFtdIGEsIGludCBsZWZ0LCBpbnQgcmlnaHQpIHsKICAgIGludCBpID0gbGVmdCAtIDE7CiAgICBpbnQgaiA9IHJpZ2h0ICsgMTsKICAgIGludCBwaXZvdCA9IGFbbGVmdF07CgogICAgd2hpbGUgKGkgPCBqKSB7CgogICAgICAgIGkrKzsKCiAgICAgICAgd2hpbGUgKGFbaV0gPCBwaXZvdCkKICAgICAgICAgICAgaSsrOwoKICAgICAgICBqLS07CgogICAgICAgIHdoaWxlIChhW2pdID4gcGl2b3QpCiAgICAgICAgICAgIGotLTsKCiAgICAgICAgaWYgKGkgPCBqKQogICAgICAgICAgICBzd2FwIChhLCBpLS0sIGorKyk7CiAgICB9CiAgICAKcmV0dXJuIGk7Cn0KCnByaXZhdGUgc3RhdGljIHZvaWQgc3dhcCAoaW50W10gYSwgaW50IGksIGludCBqKSB7CiAgICBpbnQgdGVtcCA9IGFbaV07CiAgICBhW2ldID0gYVtqXTsKICAgIGFbal0gPSB0ZW1wOwp9Cn0=