[Algorithm] 삽입 정렬은 뭐야?

삽입 정렬은 "정보를 하나하나 확인하면서 각 정보들을 적절한 위치에 삽입하면 어떨까?"라는 생각에서 출발하는 알고리즘으로 앞서 말했던 선택 정렬과 다른 점은 필요할 때만 위치를 바꾼다는 것이다. 따라서 삽입 정렬은 거의 정렬되어있는 정보를 정렬할 때는 연산의 수가 적고, 빠르게 연산된다는 특징이 있다.

 

삽입 정렬은 정렬된 숫자들의 왼쪽과 오른쪽의 숫자들을 비교하여 연산 중인 숫자가 들어갈 적절한 위치에 숫자를 넣어준다.

 

다음은 1부터 5까지의 숫자를 무작위로 배치한 정보를 삽입 정렬을 이용하여 정렬하는 방식이다.

 

삽입 정렬 순서 1번째

일단 무작위로 받은 숫자들이다. 파란색 배경은 정렬된 숫자, 진한 회색 배경은 선택 정렬 중인 숫자라고 한다.

 

삽입 정렬 순서 2번째

선택 정렬에서 첫번째 인덱스는 정렬되었다는 가정을 하기 때문에 두 번째 인덱스인 5부터 정렬을 시작한다. 5는 이미 정렬된 1보다 크기 때문에 1을 기준으로 오른쪽에 가만히 있는 것으로 정렬한다.

 

삽입 정렬 순서 3번째

다음은 3을 정렬할 차례이다. 이미 정렬된 숫자 1,5 에서 3은 1보다 크고, 5보다 작기 때문에 5의 왼쪽에 정렬되게 된다.

 

삽입 정렬 순서 4번째

3과 마찬가지로 2는 1보다 크고, 3보다 작기 때문에 3의 왼쪽에 정렬되게 된다.

 

삽입 정렬 순서 5번째

마지막으로 4는 3보다 크고, 5보다 작기 때문에 5의 왼쪽에 정렬되게 된다.

 

삽입 정렬 순서 6번째

위의 과정을 통해서 삽입 정렬의 순서를 알아보았다. 삽입 정렬은 선택 정렬과 마찬가지로 시간 복잡도는 O(N^2)이다.

 

다음은 삽입 정렬의 과정을 코드로 표현한 것이다.

 

array = [1,5,3,2,4]
 
for i in range(1, len(array)):
  for j in range(i, 0, -1):
    if array[j] < array[j-1]:
      array[j], array[j-1] = array[j-1], array[j]
    else:
      break
 
print(array)

for j in range(i,0,-1) 반복문을 통해서 정렬된 배열의 뒤에서부터 하나씩 값을 확인하면서 적절한 위치로 이동할 때까지 이동시켜준다.

 

마지막으로 삽입 정렬은 "이미 정렬되어있다"라는 가정을 하기 때문에 거의 정렬이 되어있는 배열에 대해서는 빠른 속도를 기대할 수 있다.

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬