[코딩도장] 삽입정렬 응용

[문제]

위 그림은 {5,2,4,6,1,3} 이라는 배열을 소트하는 방법을 보여준다.

1. 배열의 두번째 인덱스부터 시작하여 시작한 인덱스(검정색 블록) 좌측의 항목 중 자신이 들어가야 할 위치를 판단(소트되도록)하여 이동 한다.
2. 좌측의 배열 요소들은 본인보다 좌측에 값이 삽입되어 들어올 경우 한칸씩 우측으로 이동한다. 단, 삽입되어 들어오는 요소(그림에서 검정색 블록)가 있던 인덱스(원래의 위치)까지만 이동한다.
3. 마지막 인덱스까지 위 과정을 반복한다.

이와 같은 기능을 하는 소트 프로그램을 작성하시오.

[소스]

package InsertionSort;
 
 
public class main_mh {
 
 
    public static void main(String[] args) {
 
 
        int[] numArr = { 5, 2, 4, 6, 1, 3 };
        int numTmp = 0, idxTmp = 0;
        
        for ( int i = 1; i < numArr.length; i++ ) {
            
            for ( int j = i-1; j >= 0; j-- ) {
                
                if ( numArr[j] < numArr[i] ) {
                    numTmp = numArr[j+1];
                    idxTmp = j+1;
                    numArr[idxTmp] = numArr[i];
                    break;
                    
                } else if ( j == 0 && numArr[j] > numArr[i] ) {
                    
                    numTmp = numArr[j];
                    idxTmp = j;
                    numArr[idxTmp] = numArr[i];
                }
            }
            
            for ( int j = i; j > idxTmp; j-- ) {
                
                if ( j-1 == idxTmp ) {
                    numArr[j] = numTmp;
                    
                } else {
                    numArr[j] = numArr[j-1];
                }
            }
        }
        
        for ( int num : numArr ) {
            System.out.print(num + " ");
        }
    }
}

[결과]

※ 출처: http://codingdojang.com/scode/443?answer_mode=hide