[알고리즘] 정렬 - 삽입 정렬, O(N^2)

삽입 정렬 역시 Θ(N^2) 의 시간 복잡도를 지닌 정렬 알고리즘이다. 사실 정렬 알고리즘은 어디서부터 정렬할지 정하기 나름이지만 필자는 삽입 정렬을 왼쪽부터 정렬된 상태를 늘려나간다고 공부했다. 개념적으로 왼쪽부터 정렬된 공간을 1씩 늘려나간다고 생각할 수 있다. 삽입 정렬 (Insertion Sort) 소개 삽입 정렬은 왼쪽부터 정렬된 공간을 1씩 순차적으로 늘려나가면서 정렬하는 과정이다. 차례대로 원소를 보면서 왼쪽의 정렬된 공간의 알맞은 자리에 삽입하면서 정렬된다는 의미에서 삽입 정렬이라는 이름이 붙게 되었다. 글로만 설명하려니까 어려우므로 그림을 보면서 이해하면 될 것 같다. 그림에서는 알맞은 자리로 한 번에 이동하는 것처럼 표시했지만 사실은 현재 삽입하려는 원소를 바로 아래의 인덱스부터 차례대..

2024.03.17