// TestBinarySort.java ปรับปรุง : 2548-06-05 ()
// เคล็ด : นำตัวใหม่มาต่อแถว ตอนตรวจจะตรวจจากจุดกึ่งกลาง และเลือกช่วงที่จะดำเนินย้ายค่า
// โปรแกรมสำหรับ จัดเรียงข้อมูล แบบ Binary Insertion (Binary Search)
// หลักการทำงาน (การจัดเรียงต้องอธิบายด้วย step ของภาพ จึงจะเข้าใจได้โดยง่าย)
//   เก็บข้อมูลลงอาร์เรย์ให้หมดก่อน 
//   ข้อมูลในอาร์เรย์ชุดใหม่จะค่อย ๆ เพิ่ม โดยนำสมาชิกใหม่มาต่อแถว และตรวจสอบทีละตัว 
//   เมื่อนำตัวใหม่มาตรวจสอบกับจุดกึ่งกลางของแถว ก็จะพิจารณาการเลื่อน
//   หลังเปรียบเทียบ ก็จะได้ช่วงที่ต้องดำเนินการใหม่ เช่นช่วงบน หรือช่วงล่าง
//   ผลสุดท้าย จะเลื่อน upper ตัวเก่าไปหา lower ตัวใหม่
//   เริ่มต้นนำ 46 ตรวจสอบกับ 51 มาบวกกันแล้วหาร 2 หาจุดกึ่งกลาง ซึ่งปัดเศษทิ้ง
//   Binary Insertion Sort
//   Before : 51 46 14 35 22
//   Swap : 46 51 14 35 22
//   Swap : 46 14 51 35 22
//   Swap : 14 46 51 35 22
//   Swap : 14 46 35 51 22
//   Swap : 14 35 46 51 22
//   Swap : 14 35 46 22 51
//   Swap : 14 35 22 46 51
//   Swap : 14 22 35 46 51
//   After  : 14 22 35 46 51
// แหล่งอ้างอิง
//   http://www.thaiall.com/class
//   http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/binsort.html (มี Animation)
//   http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
//   http://www.java2s.com/ExampleCode/Collections-Data-Structure/Sort-Search.htm
// ปัญหาที่อาจพบ 
//   ถ้า compile ทุกโปรแกรม แล้ว run ทีละโปรแกรม จะพบปัญหา SortingProcess ซ้ำกัน
//   แต่ถ้า compile และ run ทีละโปรแกรม จะไม่พบปัญหา เพราะปัญหาเกิดจาก SortingProcess ซ้ำกับในโปรแกรมอื่น
//
import java.lang.*;
class SortingProcess {
  int temp,elems=0; 
  Comparable ar[] = new Comparable[100];
  public void insert(Comparable value) { 
    ar[elems] = value;
    elems++;
  }  
  private void swap(int m, int n) {
    Comparable temp = ar[m];
    ar[m] = ar[n];
    ar[n] = temp;
  }
  public void printresult(String txt) {
    System.out.print(txt);
    for(int i=0;i<elems;i++) {
      System.out.print(" " + ar[i]);
    }
    System.out.println();
  }
  public void BinarySort() {
    int lower, upper;
    int mid;
    for(int i = 1; i < elems; i++) {
      lower = 0;
      upper = i;
      while(lower < upper) {
        mid = (lower + upper) / 2;
        if(ar[i].compareTo(ar[mid]) > 0)
          lower = mid + 1;
        else
          upper = mid;
      }
      for(int j = i; j > lower; j--) { // for j = upper ตัวเก่า downto lower ตัวใหม่
        swap(j - 1, j);
        printresult("Swap :");	
      }
    }
  }
}
class TestBinarySort {
  public static void main(String[] args) {
    System.out.println("Binary Insertion Sort");
    SortingProcess arr = new SortingProcess();
    arr.insert(new Integer(51));
    arr.insert(new Integer(46));
    arr.insert(new Integer(14));
    arr.insert(new Integer(35));
    arr.insert(new Integer(22));	
    arr.printresult("Before :");
    arr.BinarySort();
    arr.printresult("After  :");
  }
}