import java.util.*;

public class TableSort extends JApplet {
int t[];//permutation array
JButton sort;
int list[];//data records
JTextArea ta;
final int size=20;
 

public String getContents(int heap[]){
String tmp="";
for(int k=0;k<size;k++){
 tmp=tmp+"  "+heap[k];
 if(k%10==0)
    tmp=tmp+'\n';}
return tmp;
}
public void swap(int x[],int a,int b){
 int tmp=x[a];
 x[a]=x[b];
 x[b]=tmp;
}//swap

public void init(){
Random thing=new Random();
sort =new JButton("sort");
ta=new JTextArea(20,50);
list=new int[size];
for(int j=0;j<size;j++)
  list[j]=thing.nextInt(1000);

t=new int[list.length];
 for(int i=0;i<size;i++)
   t[i]=i;
 Container c=getContentPane();
 c.setLayout(new BorderLayout());
 c.add(ta,BorderLayout.CENTER);
 c.add(sort,BorderLayout.SOUTH);
 ta.setText("Array is"+getContents(list));
 ta.append("\noriginal"+getContents(t));//original order
 sort.addActionListener(new ActionListener(){
  public void actionPerformed(ActionEvent e){
someIndexSort(list,t);
ta.append("\nsort ");
ta.append("Array is"+getContents(list));
ta.append("\npermutation is"+getContents(t));//sorted order
ta.append("\ntable sort ");

table(list,t);
ta.append("Array is"+getContents(list));
  }
 }
 );
 

}//init
public void someIndexSort(int x[],int index[]){

  for(int i=1;i<x.length;i++)
    for(int j=i;j>0&&x[index[j-1]]>x[index[j]];j--)
       swap(index,j,j-1);
   }//insertion sort on indices
 

public void table(int list[],int t[]){
int n=list.length;
for(int i=0;i<n;i++)
   if(t[i]!=i){//non trivial cycle
      int p=list[i];
      int j=i;
      do{
   int k= t[j];
   list[j]=list[k];
   t[j]=j;
   j=k;
  }while(t[j]!=i);//haven't got around cycle yet
  list[j]=p;
  t[j]=j;
 }//if
}//table
 

}//applet