정렬(Sort) (2과목)

정보처리기사 준비

목록 보기

38/57

가장 간단한 정렬 방식, 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬한다.
두 번째 키와 첫 번째 키를 비교해서 순서대로 나열(1회전), 세 번째 키와 첫 번째, 두 번째 키를 비교하여 순서대로 나열(2회전), 계속해서 n번째 키를 비교하여 순서에 맞게 삽입 정렬한다.
8, 5, 6, 2, 4를 삽입정렬 한다.
8, 5를 비교하여 1회전을 마치면 5, 8, 6, 2, 4가 된다.
6을 5, 8과 비교하여 5, 6, 8, 2, 4가 된다.(2회전)
2를 5, 6, 8과 비교하여 2, 5, 6, 8, 4가 된다.(3회전)
4를 비교하여 2, 4, 5, 6, 8로 정렬을 마친다.(4회전)
평균과 최악 모두 수행 시간 복잡도는 O(n2)이다.
삽입 정렬의 keyword는 '이미 순서화된 파일에 n번째 키를 앞의 n-1개의 키와 비교'이다.

삽입 정렬을 확장한 개념
입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고 각 서브파일을 삽입 정렬 방식으로 정렬한다. 매개변수 h는 주로 3 $\sqrt{n}$ 으로 설정한다.
입력 파일이 부분적으로 정렬되어 있는 경우에 유리한 방식이다.
평균 수행 시간 복잡도는 O(n1.5)이고 최악 수행 시간 복잡도는 O(n2)이다.
쉘 정렬의 keyword는 '매개변수'이다.

최소값을 비교하여 앞에 두고 맨 앞부터 고정해버리는 정렬방식이다.
맨 앞을 고정하기 위해 1번째 자리 숫자를 뒤에 n번째까지 순서대로 비교한다.
평균과 최악 모두 수행 시간 복잡도는 O(n2)이다.
8, 5, 6, 2, 4를 선택 정렬한다.
1회전은 8과 5를 비교, 5, 8, 6, 2, 4가 되고 다시 5, 6을 비교, 5, 2를 비교해서 2, 8, 6, 5, 4가 되고 2와 4를 비교해서 앞에 값이 고정된다. 1회전을 종료했을 떄 2, 8, 6, 5, 4에 2가 고정이다.
2회전은 같은 방식으로 8부터 시작한다.
2, 8, 6, 5, 4 -> 2, 6, 8, 5, 4 -> 2, 5, 8, 6, 4 -> 2, 4, 8, 6, 5가 되어 2회전을 종료한다.
2, 4, 8, 6, 5 에서 3번째 자리를 고정하기 위한 3회전이 시작한다.
2, 4, 8, 6, 5 -> 2, 4, 6, 8, 5 -> 2, 4, 5, 8, 6으로 3회전이 종료된다.
2, 4, 5, 8, 6에서 4번째 자리를 고정하기 위해 시작한다.
2, 4, 5, 8, 6 -> 2, 4, 5, 6, 8로 4회전이 끝나고 정렬을 종료한다.
선택 정렬의 keyword는 'n개의 레코드 중에서 최소값을 찾아서'이다.

버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식이다.
계속 정렬 여부를 플래그 비트(f)로 결정한다.
평균과 최악 모두 수행 시간 복잡도는 O(n2)이다.
8, 5, 6, 2, 4를 버블 정렬한다.
인접한 두개를 순서대로 모두 비교한다.
1회전은 8, 5를 비교 5, 8, 6, 2, 4가되고 다시 8, 6을 비교한다. 5, 6, 8, 2, 4가 되고 8, 2를 비교해서 5, 6, 2, 8, 4가 되고 다시 8과 4를 비교해 5, 6, 2, 4, 8이된다. 즉, 선택정렬을 거꾸로 해서 맨 마지막 값을 고정하는 정렬방식이다.
2회전은 5, 2, 4, 6, 8이된다.
3회전 종료 시 2, 4, 5, 6, 8이 되며
4회전은 2, 4를 비교하고 종료된다.
버블 정렬의 keyword는 '인접한 두 개의 레코드'이다.

퀵 정렬은 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방식으로 키를 기준 작은 값은 왼쪽에, 큰 값은 오른쪽 서브파일로 분해시키는 방식으로 정렬한다.
정렬 방식 중에서 가장 빠른 방식이다.
프로그램에서 되부름을 이용하기 때문에 스택(Stack)이 필요하다.
분할과 정복을 통해 자료를 정렬한다.
퀵 정렬의 keyword는 '하나의 파일을 부분적으로 나누어'이다.