import utils.BubbleSort;

/**
 * This class contains methods for implementing the in-place algorithm 
 * for selecting the k-th element from an unsorted array.
 * @author Vera Boutchkova
 * @version 2.0.0 Nov 2001
 */
public class SelectionIP  {
  
  public static final int SEC_SIZE = 5;

  /**
   * Finds the value of the element with index 'k'
   * in the sorted subarray (without sorting the array),
   * The method finds the correct value when left <= k <= right.
   * Destructive; uses an in-place algorithm.
   * 
   * @param  els   the array of int elements
   * @param  left  the left begin index
   * @param  right the right end index
   * @param  k     the index of the required element in the sorted subarray
   * @return  the absolute index of the element with index 'k' in the sorted 
   *              subarray[left .. right], which value is
   *              els[findKtInPlace(left, right, k).
   */
  public static int findKthInt(int[] els, int left, int right, int k) {
    if (right - left <= 10) {
      BubbleSort.sortIP(els, left, right);
      int kth = els[k];
      return kth;
    }
    int length = right - left + 1;
    for (int i = 0; i < (length / SEC_SIZE); i++) {
      median5(els, left + i * SEC_SIZE);
      swap(els, left + i, left + i * SEC_SIZE + SEC_SIZE - 1);
    }
    int medianOfMedians = findKthInt(els, left, left + length / SEC_SIZE - 1, 
                                               left + length / (2 * SEC_SIZE));
    int medInx = partition(els, left, right, medianOfMedians);    
    if (k < medInx) return findKthInt(els, left, medInx - 1, k);
    else if (k > medInx) return findKthInt(els, medInx + 1, right, k);
    else return els[medInx];
  }
  
  /**
   * Partition the subarray starting from left to right, using
   * els[medInx] for pivot: the elements to the left are smaller
   * and the elements to the right are greater or equal to the pivot. 
   *
   * @param left  the begin index
   * @param right the end index
   * @param medInx  the index of the pivot 
   * @return  the new index of the pivot
   */
  public static int partition(int[] els, int left, int right, int medInx) {
    int pivot = els[medInx];
    int i = left;
    for (int j = right; i < j;) {
      while ((i < j) && (els[i] < pivot)) i++;
      while ((i < j) && (pivot < els[j])) j--; 
      while ((i < j) && (els[i] == els[j])) j--;
      if (i < j) swap(els, i, j);
    }
    return i;
  }
  
  /**
   * Swaps the elemets els[i] and els[j] of the array els.
   *
   * @param els the array
   * @param i the index of the first element
   * @param j the index of the second element
   */
  public static void swap(int[] els, int i, int j) {
    int tmp = els[i];
    els[i] = els[j];
    els[j] = tmp;
  }
  
  /**
   * Computes the median value of the subarray of fife elements starting from the
   * element with index sInx, performing at most 6 comparisions.
   * After the exectution the median value is stored in els[sInx + 4].
   * Destructive; uses an in-place algorithm.
   *
   * @param sInx  the starting index of the subbaray
   * @return  the median value
   */
  public static int median5(int[] els, int sInx) {
    if (els[sInx] > els[sInx + 1]) swap(els, sInx, sInx + 1);
    if (els[sInx + 2] > els[sInx + 3]) swap(els, sInx + 2, sInx + 3);
    if (els[sInx] < els[sInx + 2]) {
        swap(els, sInx, sInx + 2);
        swap(els, sInx + 1, sInx + 3);
    }
    if (els[sInx + 3] > els[sInx + 4]) swap(els, sInx + 3, sInx + 4);
    if (els[sInx] < els[sInx + 3]) { 
        swap(els, sInx, sInx + 3);
        swap(els, sInx + 1, sInx + 4);
    } else swap(els, sInx + 2, sInx + 1);
    if (els[sInx + 4] > els[sInx]) swap(els, sInx, sInx + 4);
 
    return els[sInx + 4];
  }

}