삽입 정렬(insertion sort)

📔 삽입 정렬(insertion sort) 이란

• 숫자를 적절한 위치에 삽입하는 방법 "필요할 경우에만" 위치를 바꾼다.
• 2개의 반복문을 중첩해서 구현하기 때문에 시간복잡도는 O(n^2)
• 한 세트가 끝날 때마다 앞의 숫자들은 "정렬"된 상태이다.

 

📔 삽입 정렬(insertion sort) 예제

• 위의 예제는 오름차순일 경우의 예제이다.
• 5개의 원소중 처음과 그 다음을 비교한다. 그 둘을 정렬한다.
• 1세트가 끝나면 앞의 숫자들(노란색)은 정렬된 상태이다.
• 다음 세트는 두번째 숫자부터 앞의 숫자와 비교한다.

 

📔 삽입 정렬(insertion sort) 구현

numbers = [5, 3, 8, 1, 2]
print(f'정렬 전: {numbers}')
print()
for i in range(len(numbers)-1):
    print(f'{i + 1}세트')
    for j in range(i, -1, -1):
        if numbers[j] > numbers[j+1]:
            numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
        else:
            break
    print(f'정렬 중: {numbers}')
print()
print(f'정렬 후: {numbers}')

 

📔 삽입 정렬(insertion sort) 특징

• 장점
  • 버블정렬과 선택정렬과 같은 O(n^2) 이지만 어느정도 정렬이 되는 형태로 진행되기 때문에 연산의 횟수가 적어 사실상 조금 더 빠르다.
• 단점
  
  • 역시 시간복잡도 O(n^2)

 

• 만약 정렬이 거의 된 상태라면 한세트에 수행하는 연산이 거의 없으므로 속도가 매우 빨라진다.

 

 

 

📔 삽입 정렬(insertion sort) 참교자료