Insertion Sort Algorithm

삽입 정렬 알고리즘은 주어진 배열의 2번째 요소부터 앞의 모든 요소들과 비교하여 알맞은 곳에 삽입시키는 알고리즘이다.

 

배열 A = {5, 2, 4, 6, 1, 3} 이 주어졌다고 가정하자.

삽입 정렬의 과정

회색 칸은 이미 정렬이 된 원소이고, 검은색 칸은 현재 정렬해야할 key값이다. 흰색 칸은 각 단계에서 사용할 필요가 없는 원소이다.

흰색 칸을 아직 정렬되지 않은 칸으로만 볼 수 있지만, 그림(c)를 보면 이미 정렬된 2, 4 또한 흰색으로 칠해져 있다. key값인 6이 5와 비교되면 바로 자리에 삽입되기 때문에 2, 4와 비교될 필요가 없다. 이처럼 삽입 정렬 알고리즘에서의 비교횟수는 불규칙적이다.

 

2번째 요소부터 마지막 6번째 요소까지 비교 반복을 해주면, (f)그림처럼 잘 정렬된 배열이 완성된다.

Insertion Sort 수도코드

나는 수도 코드 읽는 것이 왜이리 어려운가.. 최대한 해석흐앙자

 

먼저 변수 j는 배열 A의 길이에서 1을 뺀만큼 반복된다. 배열의 맨 앞 원소는 비교대상이 없기 때문에 두번째 원소부터 시작되기 때문이다.

key값에는 당연히 A[j]의 값이 들어갈거고, key값을 정렬된 배열 A[1...j-1]에 삽입하는 것이 목표다.

key값을 올바른 곳에 삽입하기 위하여 변수 i에 j-1의 값을 넣는다. j번째 원소와 바로 왼쪽 원소부터 비교하는 것이다.

 

이제 while 루프가 돌 건데, i는 0보다 크고 A[i]의 값이 key값보다 크다면 A[i]의 값을 A[i+1]로 대입한다. A[i]의 값을 오른쪽으로 한 칸미는 것이다. 후에 i--를 하고, 다시 비교한다. 그러다가 key값보다 작은 A[i]를 찾는다면 key값을 A[i+1]자리에 대입한다. A[i]가 key값보다 작으니 그 오른쪽인 A[i+1]자리에 key값이 대입되어야겠지!

 

이제 j++하고 다시 루프를 돌면 어느샌가 잘 정렬된 배열이 완성된다.

어 뭔가 한줄씩 집중해서 읽으니까 생각보다 쉬운 수도코드. 좋은데?

 

 

자, 이제 코드 한줄을 실행하는데 드는 비용과 실행횟수가 추가된 수도코드다.

 

1번 줄부터 보면 실행횟수가 n번인 걸 볼 수 있다. 2부터 n까지인데 왜 (n-1)이 아닌 n인걸까?

j가 length[A]보다 작거나 같은 걸 확인할 때,

(j=2) ≤ n, (j=3) ≤ n ・・・, (j=n) ≤ n 까지 올 것이다. 이때까지는 실행 횟수가 (n-1)번이다.

근데 루프 탈출을 위해서는 (j=n+1) ≤ n까지 비교되어야 하지 않겠는가? 따라서 실행 횟수가 n번인 것이다.

같은 원리로 5번 줄에 $(t_j-1)$이 아닌 ($t_j$)가 된다. while문 역시 i가 0보다 작다는 것을 확인해야 탈출할 수 있으니까!

 

다음으로, while반복문에서 t변수가 있는걸 확인할 수 있다.

$t_j$는 A[j]를 알맞은 곳에 삽입하기까지 걸린 while 루프의 실행 시간인데, 위에서 설명했다싶이 비교횟수가 가변적이여서 정확한 값을 낼 수 없기에 t라는 변수로 둔 것이다.

---

알고리즘.. 뭔가 눈으로 후르륵 흝기만 하면 이해가 다 된 것 같은데, 막상 분석해보면 엥 이게 무슨말이야 싶은 마성의 무언가.

재미있나? 싶기도 하고...?

 

** 대학교 수업을 듣고 이해한 부분을 최대한 풀어서 작성한 글입니다.

틀린 정보가 존재할 수 있으며, 언제나 피드백은 환영입니다. **