-
Notifications
You must be signed in to change notification settings - Fork 0
/
RandomisedSelection.java
55 lines (51 loc) · 1.03 KB
/
RandomisedSelection.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.Scanner;
public class RandomisedSelection {
public static int sort(int a[], int s){
if(a.length==1){
return a[0];
}
return quickSort(a, 0, a.length, s);
}
public static int quickSort(int a[], int l, int r, int s){
if(r-l==1)
return a[l];
if(r>l){
int pIndex = (l + (int)Math.random() )%(r-l);
swap(a, l, pIndex);
int p = a[l];
int i = l+1;
for(int j = i; j<r; j++){
if(p>a[j]){
swap(a, i, j);
i++;
}
}
swap(a, l, i-1);
if(s==i-1)
return a[i-1];
else if(s<i-1)
return quickSort(a, l, i-1, s);
else
return quickSort(a, i, r, s-i);
}else
return 0;
}
public static void swap(int a[], int x, int y){
if(x!=y){
a[x] = a[x] + a[y];
a[y] = a[x] - a[y];
a[x] = a[x] - a[y];
}
}
public static void main(String s[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int se = sc.nextInt();
int a[] = new int[n];
for( int i = 0; i<n; i++){
a[i] = sc.nextInt();
}
System.out.println(sort(a, se-1));
sc.close();
}
}