[알고리즘] 삽입 정렬 (Insert Sort) - JAVA / 자바

삽입 정렬(Insert Sort)

 - 정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법

 - 정렬할 자료를 두 개의 부분집합 S와 U로 가정

    ㄴ 부분집합 S : 정렬된 앞부분의 원소들

    ㄴ 부분집합 U : 아직 정렬되지 않은 나머지 원소들

    ㄴ 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입

    ㄴ 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다.

    ㄴ 부분집합 U가 공집합이 되면 삽입 정렬이 완성

---

 - 수행 과정

정렬되지 않은 배열 L = {69, 10, 30, 2, 16, 8, 61, 22}

초기 상태

 : 첫 번째 원소는 정렬되어있는 부분 집합 S로 생각하고 나머지 원소들은 정렬되지 않은 원소들의 부분 집합 U로 생각한다.

69	10	30	2	16	8	61	22
부분 집합 S	부분 집합 U

① U의 첫 번째 원소 10을 S의 마지막 원소 69와 비교하여 (10 < 69) 이므로 원소 10은 원소 69의 앞자리가 된다. 더 이상 비교할 S의 원소가 없으므로 찾은 위치에 원소 10을 삽입한다.

10	69	30	2	16	8	61	22
부분 집합 S		부분 집합 U

② U의 첫 번째 원소 30을 S의 마지막 원소 69와 비교하여 (30 < 69) 이므로 원소 69의 앞자리 원소 10과 비교한다. (30 > 10) 이므로 원소 10과 69 사이에 삽입한다.

10	30	69	2	16	8	61	22
부분 집합 S			부분 집합 U

③ U의 첫 번째 원소 2를 S의 마지막 원소 69와 비교하여 (2 < 69) 이므로 원소 69의 앞자리 원소 30과 비교하고, (2 < 30) 이므로 다시 그 앞자리 원소 10과 비교하는데, (2 < 10) 이면서 더 이상 비교할 S의 원소가 없으므로 원소 10의 앞에 삽 입 한다.

2	10	30	69	16	8	61	22
부분 집합 S				부분 집합 U

④ U의 첫 번째 원소 16을 S의 마지막 원소 69와 비교하여 (16 < 69) 이므로 그 앞자리 원소 30과 비교한다. (16 < 30) 이므로 다시 그 앞자리 원소 10과 비교하여, (16 > 10)이므로 원소 10과 30 사이에 삽입한다.

2	10	16	30	69	8	61	22
부분 집합 S					부분 집합 U

⑤ U의 첫 번째 원소 8을 S의 마지막 원소 69와 비교하여 (8 < 69) 이므로 그 앞자리 원소 30과 비교한다. (8 < 30) 이므로 그 앞자리 원소 10과 비교하여, (8 < 10) 이므로 다시 그 앞자리 원소 2와 비교하는데, (8 > 2)이므로 원소 2와 10 사이에 삽입한다.

2	8	10	16	30	69	61	22
부분 집합 S						부분 집합 U

⑥ U의 첫 번째 원소 31을 S의 마지막 원소 69와 비교하여 (31 < 69) 이므로 그 앞자리 원소 30과 비교한다. (31 > 30) 이므로 원소 30과 69 사이에 삽입한다.

2	8	10	16	30	61	69	22
부분 집합 S							부분 집합 U

⑦ U의 첫 번째 원소 22를 S의 마지막 원소 69와 비교하여 (22 < 69) 이므로 그 앞자리 원소 31과 비교한다. (22 < 31) 이므로 그 앞자리 원소 30과 비교하고, (22 < 30) 이므로 다시 그 앞자리 원소 16과 비교하여, (22 > 16) 이므로 원소 16과 30 사이에 삽입한다.

2	8	10	16	22	30	61	69
부분 집합 S

U가 공집합이 되었으므로 실행을 종료하고 삽입 정렬이 완성된다.

---

 - 알고리즘

insertionSort (list[], n)
    for (i ← 1; i<n; i ← i+1) do {
        temp ← list[i];
        j ← i;
        if (list[j-1] > temp) then move ← true;
        else move ← false;
        while (move) do {
            list[j] ← list[j-1];
            j ← j-1;
            if (j > 0 and list[j-1] > temp) then move ← true;
            else move ← false;
    	}
        list[j] ← temp;
    }
end insertionSort()

 - 메모리 사용 공간 : n개의 원소에 대하여 n개의 메모리 사용

 - 연산 시간

    ㄴ 최선의 경우(= 원소들이 이미 정렬되어있어서 비교 횟수가 최소인 경우)

         : 이미 정렬되어있는 경우에는 바로 앞자리 원소와 한 번만 비교한다.

         : 전체 비교 횟수 = n-1

         : 시간 복잡도 = O(n)

    ㄴ 최악의 경우(= 모든 원소가 역순으로 되어있어서 비교 횟수가 최대인 경우)

         : 전체 비교 횟수 = 1+2+3+ ⋯ +(n-1) = n(n-1)/2

         : 시간 복잡도 = O(n2)

 - 삽입 정렬의 평균 비교 횟수 = n(n-1)/4

 - 평균 시간 복잡도 : O(n2 )

---

< 분류 > 

정렬 장소 - 내부 정렬(Internal Sort)  >  삽입 방식

[자료구조] 정렬 (Sort)