class Sorter
{

 public static void sort(int [] a,int n)
 // sort (in place) the first n integers in array a
 // uses selection sort
 {
  int sorted,minPos;
  for(sorted=0;sorted<n;sorted++)
     {
      minPos=indexSmallest(a,sorted,n);
      swap(a,sorted,minPos);
     }
 }

 public static void swap(int [] a,int pos1,int pos2)
 // swap the integers at index pos1 and pos2 in array a
 {
  int temp;
  temp=a[pos1];
  a[pos1]=a[pos2];
  a[pos2]=temp;
 }

 private static int indexSmallest(int [] a,int pos1,int pos2)
 // Return the index of the smallest integer in the portion
 // of array a starting at index pos1 and up to but not
 // including index pos2.
 {
  int i,pos=pos1;
  for(i=pos1+1; i<pos2; i++)
     if(a[i]<a[pos])
        pos=i;
  return pos;
 }

 public static int[] makeSort(int [] a,int n)
 // return a new array which is the sort of the first n
 // integers of array a
 {
  int i;
  int [] b = new int[n];
  for(i=0;i<n;i++)
     insert(a[i],b,i);
  return b;
 }

 private static void insert(int m,int [] a,int n)
 // insert integer m in first n cells in ordered array a
 {
  int j;
  for(j=n;j>0&&a[j-1]>m;j--)
     a[j]=a[j-1];
  a[j]=m;
 }

}