기수정렬

1. 삽입 정렬(Insertion Sort) - 가장 간단한 정렬 방식 - 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬한다. - 두 번째 키와 첫 번째 키를 비교해 순서대로 나열(1회전)하고, 이어서 세 번째 키를 첫 번째, 두 번째 키와 비교해서 순서대로 나열(2회전)하고, n번째 키를 n-1개의 키와 비교하여 알맞은 순서에 삽입하는 방식이다. - 평균과 최악 모두 수행 시간 복잡도는 O(n^2)이다. 예제 -> 8,5,6,2,4를 삽입 정렬 -> 비교 대상 1회전 : 8 5 6 2 4 -> 5 8 6 2 4 두 번째 값(5)을 첫 번째 값(8)과 비교하여 8보다 작은 5를 첫 번째 자리에 삽입하고 8을 한 칸 뒤로 이동시킨다. 2회전 : 5 8 6 2 4 -> 5 6 8 2..