[알고리즘]-[정렬]-삽입정렬 (JAVA)

삽입정렬(insertion sort)

개념

• 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘 이다.
• 정렬의 시작은 두번째 요소부터 시작되며 본인의 왼쪽으로는 이미 정렬된 상태라 생각하면 된다.
• 왼쪽의 값이 비교하려는 요소값보다 작을떄까지 위치를 왼쪽으로 이동시키면 된다.

처리과정

정렬의 시작은 두번째 요소인 4부터 왼쪽의 값들과 비교를 하면된다.

처음은 비교할 값이 14 하나 뿐이고 4가 14보다 작기떄문에 값을 서로 교체한다.

4와 14는 이미 정렬이 됐고 정렬할 다음 요소는 세번째 요소인 8이다. 

같은 방법으로 왼쪽의 정렬된 요소들과 비교를 하여 자기 위치를 찾아가면 된다.

자세한 처리과정은 아래 애니메이션을 참고하면 된다.

소스 (JAVA)

    public int[] getInsertionSort(int[] _intArr) {
        
        for(int i = 0; i < _intArr.length; i++) {
            for(int j = i; j >= 1; j--) {
                if(_intArr[j-1] > _intArr[j]) {
                    int tmp = _intArr[j-1];
                    _intArr[j-1] = _intArr[j];
                    _intArr[j] = tmp;
                }else break;
            }
        }
        
        return _intArr;
    }