카테고리 없음

[알고리즘] insert sort: 삽입 정렬

뱌재데 2024. 6. 20. 23:39
728x90

 

위키피디아 - 삽입 정렬 gif

 

삽입 정렬(Insertion Sort)은 매우 직관적인 정렬 방법 중 하나로, 카드 게임을 할 때 카드를 정렬하는 방법과 비슷합니다. 삽입 정렬의 기본 아이디어는 현재 정렬된 리스트에 새로운 원소를 그것이 들어갈 적절한 위치에 삽입하는 것입니다.

 

작지만 정렬된 배열에서 주로 사용합니다. 정렬된 배열의 크기를 하나씩 늘려가면서 진행합니다.

 

삽입 정렬 과정:

1. 리스트의 두 번째 원소부터 시작합니다.

2. 해당 원소를 이전의 원소들과 비교하여 적절한 위치에 삽입합니다.

3. 이 과정을 리스트의 모든 원소에 대해 반복합니다.

 

예를 들어, 숫자 리스트가 다음과 같다고 해봅시다:

[4, 3, 5, 1, 2]

- 첫 번째 원소 (4)는 이미 정렬된 것으로 간주합니다.

- 두 번째 원소 (3)을 적절한 위치, 여기서는 (4 )의 앞으로 이동합니다: [3, 4, 5, 1, 2 ]

- 세 번째 원소 (5)는 이미 올바른 위치에 있습니다.

- 네 번째 원소 (1)을 그의 위치를 찾아 이동합니다: [1, 3, 4, 5, 2 ]

- 마지막 원소 (2)도 적절한 위치로 이동합니다: [1, 2, 3, 4, 5 ]

 

 

의사코드 pseudocode:

삽입 정렬 의사코드

 

 

이 코드에는 두 개의 반복문(루프)가 있습니다.

바깥의 for loop (outer 루프)의 범위는 정렬된 배열 array를 유지할 때 사용됩니다.

시작 크기를 2로 설정합니다

안쪽의 while loop (inner 루프)는 정렬된 array를 끝까지 탐색하지 않았고, 동시에 현재 값보다 key 값이 작으면 왼쪽으로 한 칸 이동합니다

작으면 루프 안쪽으로 들어가 위치를 이동하고, 크면 바깥으로 나와 현재 위치에 새로운 값을 할당합니다.

 

삽입 정렬의 시간복잡도는 모두 n^2입니다.

 

코드의 작동 순서는 다음과 같습니다

알고리즘 - 삽입정렬 필기

 

 

 

 

 

루프 불변성(Loop Invariance):

루프 불변성이란 반복문(loop)이 진행되는 동안 항상 참이라는 성질을 가진 조건을 말합니다. 이 성질을 이용하면 코드의 정확성을 증명할 수 있습니다.

 

삽입 정렬에서의 루프 불변성:

- 불변성 조건: 반복문이 각 반복을 시작할 때마다, 현재 원소 이전의 부분 리스트는 정렬되어 있습니다.

- 초기화: 첫 번째 원소만 포함된 상태에서는, 이미 정렬되어 있다고 볼 수 있습니다.

- 유지: 각 반복에서 현재 원소를 적절한 위치에 삽입하므로, 삽입 후에도 이 부분 리스트는 정렬된 상태를 유지합니다.

- 종료: 루프가 종료될 때 모든 원소가 처리되었으므로 전체 리스트가 정렬된 상태가 됩니다.

 

이렇게 삽입 정렬과 루프 불변성을 이해하면, 간단한 알고리즘이지만 그 원리가 어떻게 작동하는지 명확하게 파악할 수 있습니다.