Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- public class Main {
- public static void main(String[] args) {
- int[] a = new int[]{1000, 10, 7, 8, 9, 30, 900, 1, 5, 6, 20};
- quickSort(a,0,a.length-1);
- System.out.println(Arrays.toString(a));
- }
- public static void quickSort(int[] arr,int l,int h){
- if (l < h){
- int n = h-l+1;
- int med = kthSmallest(arr,l,h,n/2);
- int p = partition(arr,l,h,med);
- quickSort(arr,l,p-1);
- quickSort(arr,p+1,h);
- }
- }
- private static int partition(int[] arr, int l, int r, int x) {
- int i;
- for (i=l; i<r; i++)
- if (arr[i] == x)
- break;
- swap(arr,i,r);
- i = l;
- for (int j = l; j <= r - 1; j++)
- {
- if (arr[j] <= x)
- {
- swap(arr,i,j);
- i++;
- }
- }
- swap(arr,i,r);
- return i;
- }
- private static void swap(int[] arr, int i, int r) {
- int t = arr[i];
- arr[i] = arr[r];
- arr[r] = t;
- }
- private static int kthSmallest(int[] arr, int l, int r, int k) {
- if (k > 0 && k <= r - l + 1)
- {
- int n = r-l+1;
- int i;
- int[] median = new int[(n+4)/5];
- for (i=0; i<n/5; i++)
- median[i] = findMedian(arr,i*5, 5);
- {
- median[i] = findMedian(arr,i*5, n%5);
- i++;
- }
- int medOfMed = (i == 1)? median[i-1]:
- kthSmallest(median, 0, i-1, i/2);
- int pos = partition(arr, l, r, medOfMed);
- if (pos-l == k-1)
- return arr[pos];
- if (pos-l > k-1)
- return kthSmallest(arr, l, pos-1, k);
- return kthSmallest(arr, pos+1, r, k-pos+l-1);
- }
- return Integer.MAX_VALUE;
- }
- private static int findMedian(int[] arr, int start, int len) {
- Arrays.sort(arr,start,start+len);
- return arr[start+len/2];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement