// TestShellSort.java ปรับปรุง : 2548-06-05 ()
// เคล็ด : แบ่งเป็นกลุ่ม ากจำนวนกลุ่มมาก ถึงจำนวนกลุ่มน้อย แต่ละครั้งที่แบ่งก็จะจัดเรียง
// โปรแกรมสำหรับ จัดเรียงข้อมูล แบบ Shell 
// Shell Sort (Diminishing-Increment Sort) by Donald L. Shell 1959
// แหล่งอ้างอิง
//   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 ShellSort() {
    int i, j;
    Comparable temp;
    int k = 1;
    while(k <= elems / 3)
      k = k * 3 + 1;  // 1, 4, 13, 40, 121, ...    
    while(k > 0) {
      for(i = k; i < elems; i++) {
        temp = ar[i];
        j = i;
        while(j > k - 1 && ar[j-k].compareTo(temp) >= 0) {
          ar[j] = ar[j - k];
          j -= k;
        }
        ar[j] = temp;
      }
      k = (k - 1) / 3; 
    }
  }
}
class TestShellSort {
  public static void main(String[] args) {
    System.out.println("Shell 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.ShellSort();
    arr.printresult("After  :");
  }
}