Insertion Sort (삽입정렬)

알고리즘
입력된 리스트의 모든 원소를 앞부분부터 순서대로 비교하면서 적절한 위치에 삽입함.

시간복잡도
최악의 경우 : O(n^2) 번 비교와 위치변경
최선의 경우 : O(n) 비교와, O(1)번 위치변경
평균 : O(n^2) 비교 및 위치변경.

소스

public class InsertionSort {
     /**
     * @param args
     */
     public static void main(String[] args) {
         
          int nData = 100000;     //정렬할 데이터 개수 설정.
          double TargetDataList[] = new double[nData];
         
          //데이터 생성
          for(int i = 0; i < nData; i++)
          {
               TargetDataList[i] = Math.random();
              
               System.out.print(TargetDataList[i]+" ");     //데이터 출력
          }
          System.out.println();
         
          //정렬 수행
          for(int i = 0; i < nData; i++){
               for(int j =0; j < i; j++){

                    if(TargetDataList[i] < TargetDataList[j]){
                         double tmp = TargetDataList[i];
                        
                         //삽입하고 남은배열들을 뒤로 밀어 넣음.
                         for(int moveidx = i; moveidx > j; moveidx--){
                              TargetDataList[moveidx] = TargetDataList[moveidx - 1];
                         }
                        
                         TargetDataList[j] = tmp;
                         break;
                    }
               }
          }
         
//          //정렬된 데이터 확인.
//          for(int i =0; i < nData; i++){
//               System.out.print(TargetDataList[i] + " ");
//          }
//          System.out.println();
         
     }
}

참고
1. http://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC
2. http://en.wikipedia.org/wiki/Insertion_sort