// TestInsertionSort.java ปรับปรุง : 2548-06-08 ()
// เคล็ด : นำมาต่อท้ายชุดที่เรียงแล้วทีละตัว และเรียงทันทีก่อนรับตัวต่อท้ายตัวใหม่
// โปรแกรมสำหรับ จัดเรียงข้อมูล แบบ Insertion (Linear Search)
// หลักการทำงาน (การจัดเรียงต้องอธิบายด้วย step ของภาพ จึงจะเข้าใจได้โดยง่าย)
//   เก็บข้อมูลลงอาร์เรย์ให้หมดก่อน 
//   ข้อมูลในอาร์เรย์ชุดใหม่จะค่อย ๆ เพิ่ม โดยนำสมาชิกใหม่มาต่อแถว และตรวจสอบทีละตัว 
//   เมื่อนำตัวใหม่มาต่อแถว ก็จะเก็บตัวใหม่ไว้ใน hold
//   ตรวจสอบจากล่างขึ้นบน ถ้าตัวใหม่มากกว่าตัวเก่าตัวสุดท้าย ก็จะสลับที่ตัวเก่า กับก่อนตัวเก่า
//   เลื่อนการตรวจขึ้นไป จนไม่สามารถขึ้นไปได้อีก ก็จะนำตัวที่เก็บใน hold มาแทนที่ในตำแหน่งใหม่
//   เริ่มต้นนำ 46 ตรวจสอบกับ 51
//   Selection Sort
//   Before : 51 46 14 35 22
//   After  : 14 22 35 46 51
// แหล่งอ้างอิง
//   http://www.thaiall.com/class
//   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++;
  }  
  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 InsertionSort() {
    int current, walker;
    Comparable hold;
    for(current = 1; current < elems; current++) {
      hold = ar[current];
      walker = current;
      while(walker > 0 && ar[walker-1].compareTo(hold) >= 0) {
        ar[walker] = ar[walker-1];
        walker--;
      }
      ar[walker] = hold;
    }
  }
}
class TestInsertionSort {
  public static void main(String[] args) {
    System.out.println("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.InsertionSort();
    arr.printresult("After  :");
  }
}