// Arup Guha
// 9/30/02
import java.util.Random;

public class Sort {

  private int[] values;

  public Sort(int n) {
    values = new int[n];
    Random r = new Random();
    for (int i=0; i<n; i++)
      values[i] = Math.abs(r.nextInt()%100);
  }

  public void QuickSort(int low, int high) {
    if (low < high) {
      int part = Partition(low, high);
      QuickSort(low, part-1);
      QuickSort(part+1, high);
    }
  }

  public int QuickSelect(int low, int high, int k) {
    if ((low == high) && (k == 1))
      return values[low];
    else {

      int mid = Partition(low, high);
      int place = mid - low + 1;
      if (k == place)
        return values[mid];
      else if (k < place)
        return QuickSelect(low, mid-1, k);
      else
        return QuickSelect(mid+1, high, k-place);
    }
  }

  public int Partition(int start, int end) {

    int i = start;
    int j = end;

    while (i < j) {

      while (i <= end && values[i] <= values[start])
        i++;
      while (values[j] > values[start])
        j--;
      if (i < j) 
        swap(i,j);
    }
    swap(start, j);
    return j;
  }

  public void swap(int i, int j) {
    int temp = values[i];
    values[i] = values[j];
    values[j] = temp;
  }

  public void print() {

    for (int i=0; i<values.length; i++) {
      System.out.print(values[i]+" ");
      if (i%25 == 24)
        System.out.println();
    }
  }

  public int length() {
    return values.length;
  }

  public static void main(String [] args) {

    Sort test = new Sort(20);
    for (int i=1; i<=20; i++)
    System.out.println(i+"th sm val = "+ test.QuickSelect(0,19,i));

    test.QuickSort(0, test.length()-1);
    test.print();
  }
}