삽입 정렬

[알고리즘][파이썬/Python] 삽입 정렬 (Insertion Sort)

정의 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식의 정렬 알고리즘 동작 방식 0. 정렬할 배열(혹은 리스트)은 두 개의 부분집합 S와 U로 구분 * S (Sorted) : 정렬된 앞부분의 원소들 * U (Unsorted) : 아직 정렬되지 않은 나머지 원소들 1. U의 가장 앞에 있는 원소를 꺼내어 S의 마지막 원소부터 첫 번째 원소까지 대소 비교하며, S 내에 적절하게 삽입될 위치를 탐색 2. 대소 비교가 끝나면, U에서 꺼낸 원소를 탐색한 위치에 삽입 3. 그 결과, S의 원소는 하나 증가하며 U의 원소는 하나 감소 4. U가 공집합이 될 때까지 위 과정을 반복하며 정렬 메모리 사용 공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 1. 최선의 경우 (Best Ca..