/*
 * โครงสร้างข้อมูล : ฉบับวาจาวา
 * http://www.cp.eng.chula.ac.th/~somchai/books
 */
package dataStructures;

/**
 * คลาสที่เก็บวิธีการเรียงลำดับข้อมูลแบบต่าง ๆ 
 * @author สมชาย ประสิทธิ์จูตระกูล
 */
public class ArrayUtil {
  public static void selectionSort(Object[] d) {
    for(int k=d.length-1; k>0; k--) {
      int m = k;
      for (int j = 0; j < k; j++)
        if (lessThan(d[m], d[j])) m = j;
      swap(d, m, k);  // d[m] ?? d[k]
    }
  }
  //-----------------------------------------------------
  public static void bubbleSort(Object[] d) {
    for (int k=d.length; k>1; k--) {
      boolean sorted = true;
      for (int j=1; j<k; j++) {
        if (lessThan(d[j], d[j-1])) {
          swap(d, j-1, j);
          sorted = false;
        }
      }
      if (sorted) break;
    }
  }
  //-----------------------------------------------------  
  public static void insertionSort(Object[] d) {
    for (int k=1; k<d.length; k++) {
      Object t = d[k];
      int j = k-1;
      while (j>=0 && lessThan(t, d[j])) {
        d[j+1] = d[j];
        j--;
      }
      d[j+1] = t;
    }
  }
  //-----------------------------------------------------
  public static void shellSort(Object[] d) {
    for (int h = d.length / 2; h > 0; h = h == 2 ? 1 : (int)(h / 2.2)) {
      for (int m = 0; m < h; m++) {
        for (int k = h + m; k < d.length; k += h) {
          Object t = d[k]; int j = k - h;
          while (j >= 0 && lessThan(t, d[j])) {
            d[j + h] = d[j]; j -= h;
          }
          d[j + h] = t;
        }
      }
    }
  }
  //-----------------------------------------------------
  public static void heapSort(Object[] d) {
    int size = d.length;
    for(int k=size/2-1; k>=0; k--)
      fixDown(d, size, k);
    for(int k=size-1; k>0; k--) {
      swap(d, 0, k);
      fixDown(d, --size, 0);
    }  
  }
  static void fixDown(Object[] d, int size, int k) {
    int c;
    while ((c = 2 * k + 1) < size) {
      if (c < size-1 && lessThan(d[c], d[c+1])) c++;
      if (!lessThan(d[k], d[c])) break;
      swap(d, c, k);
      k = c;
    }
  }      
  //-----------------------------------------------------
  public static void mergeSort(Object[] d) {
    mSortR(d, 0, d.length - 1, (Object[]) d.clone());
  }
  
  private static void mSortR(Object[] d, int left, int right, Object[] t) {
    if (left < right) {
      int m = (left + right) / 2;
      mSortR(t, left, m, d);
      mSortR(t, m + 1, right, d);
      merge(t, left, m, right, d);
    }
  }
  private static void merge(Object[] a, int left, int mid, int right, Object[] b) {
    int i = left, j = mid + 1;
    for (int k = left; k <= right; k++) {
      if (i > mid) { b[k] = a[j++]; continue; }
      if (j > right) { b[k] = a[i++]; continue; }
      b[k] = lessThan(a[i], a[j]) ? a[i++] : a[j++];
    }
  }
  //-----------------------------------------------------
  public static void quickSort(Object[] d) {
    qSortR(d, 0, d.length-1);
  }      
  private static void qSortR(Object[] d, int left, int right){
    if (left < right) {
      int j = partition(d, left, right);
      qSortR(d, left, j - 1);
      qSortR(d, j + 1, right);
    }
  }
  private static int partition(Object[] d, int left, int right) {
    int c = (left + right)/2;
    if (lessThan(d[left],d[c])) swap(d, left, c);
    if (lessThan(d[right],d[c])) swap(d, c, right);
    if (lessThan(d[right],d[left])) swap(d, left, right);
    Object p = d[left];
    int i = left, j = right + 1;
    while (i < j) {
      while (lessThan(p, d[--j]));
      while (lessThan(d[++i], p)) if (i==right) break;
      if (i < j) swap(d, i, j);
    }
    swap(d, left, j);
    return j;
  }
  //-----------------------------------------------------    
  private static boolean lessThan(Object a, Object b) {
    return ((Comparable)a).compareTo(b) < 0;
  }
  private static void swap(Object[] d, int i, int j) {
    Object t = d[i]; d[i] = d[j]; d[j] = t;
  }
}