7장 삽입 정렬(Insertion Sort)[PYTHON]

목차
1. 삽입 정렬
2. 그림으로 이해
3. 코드
4. 느낀점

삽입 정렬

삽입 정렬은 이미 정렬된 데이터에 선택된 데이터를 적절한 위치에 삽입하는 정렬이다.
삽입 정렬의 시간 복잡도는 O(n^2)이다.

그림으로 이해

아래와 같은 데이터가 저장된 리스트가 있다고 하자.
우리는 이 데이터를 삽입 정렬을 이용하여 정렬하고자 한다.
우리는 오름차순 정렬을 할 것이다.

우선 1번째 인덱스인 부분을 선택 데이터로 설정한다.(0이 아닌 1부터 시작한다.)

그 후 0번째 인덱스와 비교하여 정렬위치를 확인하여 Swap해준다.
사실상 0번째 인덱스 부분을 정렬된 데이터라고 봐도 무방하다.
여기서 말하는 Swap은 단순히 두 인덱스 부분을 바꾸라는 의미가 아니다. 선택 데이터가 정렬위치까지 갈 때까지 모든 값들을 Swap해줘야 한다. Swap하는 조건은 다음과 같다.

• 선택 데이터의 인덱스부터 0번째 인덱스까지 탐색한다.
• 이 때 비교하는 인덱스의 데이터가 선택 데이터보다 큰 경우 Swap해준다.
• 작거나 같다면 종료한다.
  
  그러면 아래와 같이 정렬된 부분이 생기게 된다.
  그 후 선택 데이터의 인덱스를 늘려가며 리스트의 마지막까지 반복해주면 된다.
  
  
  
  
  
  
  
  
  
  
  이렇게 최종적으로 정렬된 데이터가 만들어지게 된다.
  

코드

코드 구현은 그렇게 어렵진 않다.

num = [7, 3, 9, 5, 4, 1, 2] # 정렬 할 리스트
N = len(num) # 리스트의 길이

for i in range(1, N):
    for j in range(i, 0, -1):
        if num[j - 1] > num[j]: # Swap 조건
            temp = num[j]
            num[j] = num[j - 1]
            num[j - 1] = temp
        else:
            break

print(num)

느낀점

선택 정렬과 삽입 정렬이 평소에 헷갈렸는데 이제 제대로 이해할 수 있게 되었다.