[알고리즘] 삽입 정렬, Insertion Sort

삽입정렬이란?

삽입정렬이란, 자기보다 앞에 있는 요소들과 비교한 뒤,
"자신이 들어갈 자리를 찾아서" 그 자리에 삽입하는 방식

예

위의 사진을 통해 알 수 있듯, 집합의 두 번째 요소(인덱스 1)부터 시작하여 해당 값이 앞쪽 요소들 중 어디에 들어갈 수 있을지를 비교하고, 그 자리에 삽입하기 위해 필요한 만큼 요소들을 오른쪽으로 이동시키는 방식이다.

수도코드

Python

A = [3, 2, 4, 1, 5]
n = len(A) #5

for i in range(1, n):
  key = A[i]
  j=i-1

  while j>=0 and A[j]>key:
    A[j+1]=A[j]
    j-=1

  A[j+1] = key
 
print(A)

key값 도입 이유

이후 크기 비교/이동 중 A[i]가 덮어씌워지므로, 원래 값을 저장해둠

j는?

key와 비교될 앞쪽 인덱스. while문에서 1씩 작아지게 되어

A[j+1] = A[j]

while문 조건이 성립될 때마다 j가 감소하며,
key보다 큰 값들은 오른쪽으로 하나씩 밀린다.

A[j+1] = key

반복이 끝난 뒤 j는 key보다 작거나 같은 값의 인덱스를 가리키게 되며,
그 다음 위치인 j+1이 key가 들어가야 할 정확한 위치가 된다.
따라서 key는 밀려서 생긴 빈 자리에 삽입된다.

의문이었던 점

while문 조건이 False여서 반복문에 진입하지 않으면 j -= 1도 실행되지 않는데,
이렇게 되면 j가 끝까지 줄어들지 않고 바로 다음 i로 넘어가도 괜찮은 걸까?
즉, 비교가 충분히 이루어지지 않고 정렬이 틀어지는 건 아닌가?
답변
문제가 없다.
삽입 정렬은 앞에서부터 차례로 정렬된 부분을 점점 확장해나가는 알고리즘이다.
즉, i번째 원소를 삽입할 때,
그 앞의 0 ~ i-1까지는 이미 정렬되어 있다는 전제가 있다.