Notepad

C++/Algorithm

[Algorithm/C++] 삽입 정렬(Insertion Sort) - 비교 후 삽입

1. 설명 삽입 정렬(Insertion Sort)란 리스트의 값들을 순차적으로 인접한 원소와 비교를 하여 위치를 교환해주며 정렬을 하는 방법 중 하나이다. 한 원소를 선택하여 위치를 변경해준다는 점에서 선택 정렬(Selection Sort)과 유사하다고 할 수도 있으며 인접한 원소 간 비교를 통하여 위치를 교환해주므로 거품 정렬(Bubble Sort)과도 유사하다고 할 수도 있다. 동작 예시를 살펴보면 오름차순 정렬을 위해서는 리스트의 첫 번째 위치에는 리스트에서 가장 작은 값이 위치하여야 한다. 시작은 두 번째 Index부터 시작하며 왼쪽에 있는 원소들과 비교를 통하여 더 큰 값이 왼쪽에 위치하고 있다면 교환하는 작업을 수행한다. 이 작업을 반복하여 수행함으로써 가장 작은 원소는 가장 왼쪽의 위치하게 ..