삽입 정렬(Insertion Sort)과 이진 삽입 정렬(Binary Insertion Sort)

※ 이 글은 chatGPT를 기반으로 작성한 글입니다.

① 삽입 정렬(insertion sort)는 비교적 간단한 정렬 알고리즘이다.

  ㉠ 추가적인 메모리 공간이 필요하지 않지만, 알고리즘의 수행 시간이 O(n^2)이다.

② 삽입 정렬은 제자리 알고리즘(in-place algorithm) 중 하나이다.

  ㉠ 제자리 알고리즘은 자료 구조를 추가로 사용하지 않아 추가적인 메모리 공간이 필요하지 않다는 것을 의미한다.

③ 삽입 정렬과 이진 삽입 정렬의 기본 원리는 정렬된 배열 A에 정렬할 요소를 집어넣는 것이다.

  ㉠ 삽입 정렬과 이진 삽입 정렬의 작동 원리는 다음과 같다.

    ⓐ 정렬할 배열을 정렬된 배열 A와 비정렬된 배열 B로 나눈다.(크기가 1인 배열은 정렬된 상태로 본다.)

 

배열 A의 크기는 1이기 때문에 정렬된 상태로 본다.

    ⓑ 비정렬된 배열의 첫 번째 요소가 배열 A 들어갈 적절한 위치를 찾는다.

 

3은 5보다 작기 때문에 5의 앞에 삽입할 수 있다.

    ⓒ 비정렬된 배열의 크기가 0이 될 때까지 ⓑ를 반복한다.

 

  ㉡ ㉠의 ⓑ번에서 적절한 위치를 찾는 방법은 다음과 같다.

    ⓐ 일반적인 삽입 정렬에서는 선형 탐색(linear search)으로, 인덱스가 증가하는 순으로 탐색할 수 있고, 인덱스가 감소하는 순으로 적절한 위치를 찾을 수 있다.(구현의 편의상 후자를 택하겠다.)

    ⓑ 이진 삽입 정렬에서는 이진 탐색(binary search)로 적절한 위치를 찾을 수 있다.

    ⓒ 이진 탐색 알고리즘은 아래를 참고하자.

 

이진 검색 알고리즘(Binary Search Algorithm)

④ 삽입 정렬의 의사 코드(psuedo code)는 다음과 같다.

 

⑤ 이진 삽입 정렬의 의사 코드는 다음과 같다.

 

⑥ 삽입 정렬의 시간 복잡도는 Θ(n^2)이다.

  ㉠ 역순으로 정렬되어 있을 때가 최악의 경우이다.

    ⓐ 정렬된 크기 2인 배열에서 삽입될 수 있는 위치는 3개이지만, 비교는 2번만 수행하면 된다.

 

②인지 ③인지 판별하고 아니면, ①인지 ②인지 판별하면 되기 때문에 2번만 비교하면 된다.

    ⓑ 같은 원리로 비교하면 44번 비교해야 한다.

  ㉡ 평균적인 경우를 생각해보자.

    ⓐ 평균적인 시간 복잡도를 구하기 위해 확률론의 기댓값 식을 이용할 수 있다. 랜덤변수 X를 비교 횟수라고 설정하자.

    ⓑ x는 확률변수가 x일 때 비교횟수이므로 다음과 같이 구할 수 있다.

 

    ⓒ 입력 배열이 무작위로 나열되어 있다고 가정하면 각 요소가 특정 위치에 삽입될 확률은 1/i이다. 이 확률은 모든 요소가 동일한 확률을 가진다.

 

11번째 요소를 삽입할 때 가능한 확률은 1/11이다.

    ⓓ 평균 시간 복잡도는 Θ(n^2)이다. 

⑦ 일반적인 이진 삽입 정렬의 평균 시간 복잡도는 여전히  O(n^2)이다.

  ㉠ 삽입할 키의 위치를 찾기 위해 이분 탐색을 할 경우 log(n)의 비교를 수행하기 때문에 시간적인 이득이 있지만, 여전히 n - i개를 뒤로 이동시켜야 하므로, 결과적으로는 시간복잡도는 O(n^2)이다.

⑧ 삽입 정렬, 이진 삽입 정렬의 구현 코드는 다음과 같다.

  ㉠ 삽입 정렬의 구현 코드는 다음과 같다.

 

  ㉡ 이진 삽입 정렬의 구현 코드는 다음과 같다.