Seongwon Lim

삽입 정렬 (Insertion Sort) 삽입 정렬이란 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 알고리즘이다. 삽입 정렬의 특징은 다음과 같다. 두 번째 키와 첫 번째 키를 비교하여 순서대로 나열(1회전)하고, 이어서 세 번째 키를 1,2 번째 키와 비교하여 순서대로 나열(2회전)하고, 계속해서 n번째 키를 앞의 n-1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬하는 알고리즘이다. 평균과 최악 모두 수행 시간 복잡도는 O(n^2) 이다. 예제를 통해서 삽입 정렬을 이해해보자. 삽입 정렬 예제 초기 상태 : [8, 5, 6, 2, 4] 1회전 두 번째 레코드 5를 Key로 지정하여 이전 자료들과 비교한다. Key(5)가 첫 번째 레코드인 8 보다 작으므로, 8을 Key..