[Algorithm] 삽입 정렬

삽입 정렬

 

 이번에는 삽입 정렬에 대해서 알아보겠습니다. 삽입 정렬 이란 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 입니다. 이 곳을 보시면 좀 더 확실한 이해가 될 것입니다. 

 시간 복잡도는 O(n^2) 입니다. 그리고 배열 두 번째 인덱스 부터 연산이 시작된다는 특징을 가지고 있습니다. 실제 JAVA 로 작성한 코드는 아래와 같습니다.

 void doSort(int[] numArr){
        int i, j;
        for(i = 1; i < numArr.length; i++){
            int tmp = numArr[i];
            for(j = i-1; j >= 0 && tmp < numArr[j]; j--){
                numArr[j + 1] = numArr[j];
            }
            numArr[j + 1] = tmp;
        }
    }

 

참고자료 : https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC