//
// 参考：https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88
//
// 選択ソート（selection sort）アルゴリズムの紹介
//
// データ列中で一番小さい値を探し、1番目の要素と交換する。
// 次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。
// これを、データ列の最後まで繰り返す（厳密には、データ列の最後より1つ手前までの繰り返しでよい。
// 一つ前まで交換済みであれば、最後（残り）は必ず最大値になるからである）。大小が入れ替わる降順の場合も同様の手法である。

import java.util.Scanner; //入力用 
public class Report_4_2_Selection_Sort{ 
   public static void sort_array(int[] x){
       for (int i=0;i<x.length-1 ;i++ ){ //繰り返す回数  
                int min=i;   //i番目の要素を一番小さい値と仮定する
                for (int j=i+1;j<x.length ;j++ ){  //i番目以降のデータ列から一番小さい値を探す 
                      if (x[min]>x[j]){   
                           min=j;   
                      }   
                }   
                if (min!=i){  //i番目以降のデータ列の一番小さい値をi番目の要素と交換する　　
                        int temp=x[i];  
                        x[i]=x[min];  
                        x[min]=temp;          
                }  
        }  

     System.out.println("Sorted array is:");
         for(int i = 0;i<x.length;i++){
             System.out.print(x[i]+";");

         }
   }
 public static void main(String args[]){
   Scanner scan = new Scanner(System.in);
   System.out.println("Please input the number of elements you want to sort:");
   int n = scan.nextInt();
   int[] array = new int[n];
   System.out.println("Please input the  elements of the array:");
   int i;
     for(i=0;i<n;i++){
      array[i]=scan.nextInt();
     }
   sort_array(array); 
 }

}