/**
 * Hoare's quicksort and quickselect.
 * 
 * @author (Stefan Edelkamp) 
 * @version (2013)
 */

import java.util.Random;

public class Quick
{
     private int a[];
    /**
     * Constructor for objects of class Quick
     *
     * @param  n   number of array elements 
     * @param  k   position k for k-th element selection 
     */
    public Quick(int n, int k) {
      a = new int[n]; 
      Random r = new Random();
      for (int i=0;i<n;i++) a[i] = i;  
      for (int i=1;i<n;i++) swap(i,r.nextInt(i));  
      System.out.println("Quickselect "+ select(0,n-1,k));  
      for (int i=1;i<n;i++) swap(i,r.nextInt(i)); 
      sort(0,n-1); 
      for (int i=0;i<n;i++) System.out.print(a[i]+" ");  
      System.out.println(); 
    }
    void swap(int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
    /**
     * selects the kth element in interval 
     * 
     * @param  left    left interval bound
     * @param  right   right interval bound
     * @param  k       position 
     */
    public int select(int left, int right, int k) {
      int i,j,v;  
      i = left; j = right+1; v=a[left]; // set pivot
      do { // partition wrt. pivot
        do j--; while (j>=i && v < a[j]); 
        do i++; while (i<=j && a[i] < v);
        if (j > i) swap(i,j); 
      } while(j >= i);
      swap(left,j); // move pivot, end of partitioning
      if (k == j) return a[k]; // element found
      return k < j ? select(left,j,k) : select(j+1,right,k);
    }
     /**
     * sorts interval according to Hoares Quicksort algorithm 
     * 
     * @param  left    left interval bound
     * @param  right   right interval bound 
     */
    public void sort(int left, int right) { 
      int i,j,v; // two indices and one temporary
      if (right-left > 0) { // interval is non-trivial
        i = left; j = right+1; v=a[left]; // set pivot
        do { // partition wrt. pivot
          do j--; while (j>=i && v < a[j]); 
          do i++; while (i<=j && a[i] < v);
          if (j > i) swap(i,j); 
        } while(j >= i);
        swap(left,j); // move pivot, end of partitioning
        if (j-left < right-i+1) { sort(left,j-1); sort(j+1,right); }
        else { sort(j+1,right); sort(left,j-1); } 
      } 
    }
}