import java.util.*;
public class recursion{
public static void main(string args[]){
int[] a=new int[10];
random myrandom=new random();
for(int i=0;i <a.length;i++){
a[i]=(int)(myrandom.nextdouble()*10.0);
}
system.out.print( " initial data: ");
for(int i=0;i <a.length;i++){
system.out.print(a[i]+ " ");
}
system.out.println();
recursion(a,0,a.length-1);
system.out.print( "after sorting the data: ");
for(int i=0;i <a.length;i++){
system.out.print(a[i]+ ", ");
}
system.out.println();
int[] b=new int[a.length];
system.arraycopy(a, 0, b, 0,a.length);
system.out.print( "copydata: ");
int maxsize = 100;
recursion arr = new recursion(maxsize);
for(int i=0;i <b.length;i++){
arr.insert(b[i]);
}
arr.display();
int searchkey =5;
if (arr.find(searchkey) != arr.size())
system.out.println( "found " + searchkey);
else
system.out.println( "can 't find " + searchkey);
}
static int quicksortstep(int[] a, int lo, int hi){
int pivot = a[lo];
while (hi > lo) {
while (hi > lo && a[hi] > pivot) {
hi--;
}
if (hi == lo) break;
a[lo] = a[hi];
lo++;
while (hi > lo && a[lo] < pivot) {
lo++;
}
if (hi == lo) break;
a[hi] = a[lo];
hi--;
}
a[lo] = pivot;
return lo;
}
static void recursion(int[] a,int lo,int hi){
if(hi <=lo){
return;
}
else{
int pivotposition=quicksortstep(a,lo,hi);
recursion(a,lo,pivotposition-1);
recursion(a,pivotposition+1,hi);
}
}
private int[] a;
private int n;
public recursion(int max) {
a = new int[max];
n = 0;
}
public int size() {
return n;
}
public int find(int searchkey) {
return recfind(searchkey, 0, n - 1);
}
private int recfind(int searchkey, int loindex, int hiindex) {
if (loindex > hiindex) {
return -1;
}
else {
int middle = (loindex + hiindex) / 2;
if (searchkey == a[middle])
return middle;
else if (searchkey <a[middle])
return recfind(searchkey, loindex, middle - 1);
else
return recfind(searchkey, middle + 1, hiindex);
}
}
public void insert(int value)
{
a[n] = value;
n++;
}
public void display() {
for (int j = 0; j < n; j++)
system.out.print(a[j] + " ");
system.out.println( " ");
}
}