알고리즘 기초 (삽입정렬)

Harvard CS50 x Edwith 강의를 학습하며 정리한 내용입니다.

삽입정렬

---

삽입정렬은 자료를 정렬하는 알고리즘중 하나로 자료가 정렬된 부분과 정렬되지 않은 부분으로 나누어 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법입니다. 그렇기 때문에 자료를 여러 번 비교하거나 교환할 필요가 없으며 배열이 길수록 효율이 떨어지지만 구현은 간단한 방법입니다.

예제

---

3, 6, 2, 5, 1, 4 의 배열을 정렬해보자.

1. [3] | 6 | 2 | 5 | 1 | 4
2. [3] | [6] | 2 | 5 | 1 | 4
3. [2] | [3] | [6] | 5 | 1 | 4
4. [2] | [3] | [5] | [6] | 1 | 4
5. [1] | [2] | [3] | [5] | [6] | 4
6. [1] | [2] | [3] | [4] | [5] | [6]

배열의 정렬된 부분은 [] 로 표기하였고 정렬되지 않은 부분은 그냥 숫자로 표기하였습니다.

• 프로그램이 실행되었을때 배열의 첫번째 자리는 이미 정렬된 부분으로 간주합니다.
• 정렬되지 않은 부분의 6은 3보다 크기 때문에 이동할 필요가 없습니다.
• 다음 정렬되지 않은 2는 3과 6보다 작기 때문에 2가 자리를 비우고 3과 6이 오른쪽으로 이동 후 맨 앞자리로 2가 들어옵니다.
• 다음 정렬되지 않은 5는 정렬된 2,3,6에서 2,3은 제외한 6의 기준에서만 작기때문에 5 와 6 은 자리를 교환합니다.

이런식으로 같은 방식을 반복하면 전체의 모든 값이 정렬되는 것을 볼 수 있습니다.

코드(Java)

---

static void insertionSort(int[] arr)
    {
        int i, temp, j;
        for(i = 1 ; i < arr.length ; i++){

            temp = arr[i];
            j = i - 1;

            while( (j >= 0) && ( arr[j] > temp ) ) {

                arr[j+1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;

            System.out.print("\n삽입정렬 "+i+" 번 : ");
            for (int z = 0; z < arr.length; z++) {
                System.out.print(arr[z]+" ");
            }
        }
    }

    public static void main(String[] args) {
        int arr [] = {3,6,2,5,1,4};
        insertionSort(arr);
    }

결과

---

정리

---

삽입정렬은 특정 실행 단계에서 한 원소가 정렬된 배열의 자리를 이동하거나 찾았다 해도 그것이 최종적인 자리인 보장을 할 수 없습니다. 즉 정렬이 끝나기 전까지는 확실한 보장을 하지 못한다는 의미입니다. 그렇기에 삽입정렬은 자료의 양이 많을 수록 성능이 떨어질 수 밖에 없으며 또한 많은 자료가 정렬이 되어 있는 경우라도 정렬이 된 많은 자료들을 이동시켜야 하기 때문에 안정성도 떨어집니다. 결과적으로 자료의 양이 적거나 자료가 대부분 정렬이 되어 있는 경우 효율적인 정렬이라고 볼 수 있습니다.

참고

---

cs50 x edwith
위키백과