1. 정렬이란?
- 파일을 구성하는 각 레코드들을 특정 키 항목을 기준으로 오름차순(Ascending) 또는 내림차순(Descending)으로 다시 배열하는 작업이다.
1-1. 내부 정렬
- 소량의 데이터를 주기억장치에만 기억시켜 정렬하는 방식이다.
- 내부 정렬의 종류로는 삽입 정렬, 버블 정렬, 선택 정렬, 퀵 정렬, 히프 정렬, 셸 정렬, 2-Way Merge 정렬 등이 있다.
1-2. 외부 정렬
- 대량의 데이터를 보조기억장치에 기억시켜 정렬하는 방식으로 대부분 병합 정렬(Merge Sort) 기법으로 처리한다.
- 외부 정렬의 종료로는 밸런스 병합 정렬, 캐스케이드 병합 정렬, 폴리 파즈 병합 정렬 등이 있다.
2. 주요 정렬
- 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식이다.
- 정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬의 대상이다.
5 3 8 1 2
오름차순 정렬 시
먼저, 3을 5와 비교하여 삽입할 위치 찾기
↓
3 5 8 1 2 ··· 1회전 결과(3, 5 정렬 완료)
↓
3 5 8 1 2
8을 정렬된 영역 중 삽입할 위치 찾기
8을 정렬된 영역 중 삽입할 위치 찾기
↓
3 5 8 1 2 ··· 2회전 결과(3, 5, 8 정렬 완료)
↓
3 5 8 1 2
1을 정렬된 영역 중 삽입할 위치 찾기
1을 정렬된 영역 중 삽입할 위치 찾기
↓
1 3 5 8 2 ··· 3회전 결과(1, 3, 5, 8 정렬 완료)
↓
1 3 5 8 2
2를 정렬된 영역 중 삽입할 위치 찾기
2를 정렬된 영역 중 삽입할 위치 찾기
↓
1 2 3 5 8 ··· 4회전 결과
2-2. 버블 정렬
- 주어진 파일에서 인접한 2개의 레코드 키 값을 비교하여 크기에 따라 레코드 위치를 서료 교환하는 정렬 방식이다.
8 5 6 2 4
오름차순 정렬 시
먼저, 5와 8 비교
↓
5 8 6 2 4
5 6 8 2 4
5 6 2 8 4
5 6 2 4 8 ··· 1회전 결과
↓
5 6 2 4 8
다시 첫번째, 두번째 비교
↓
5 6 2 4 8
5 2 6 4 8
5 2 4 6 8
5 2 4 6 8 ··· 2회전 결과
↓
5 2 4 6 8
다시 첫번째, 두번째 비교
↓
2 5 4 6 8
2 4 5 6 8
2 4 5 6 8
2 4 5 6 8 ··· 3회전 결과
2-3. 선택 정렬
- n개의 레코드 중, 최소값을 찾아 첫번째 레코드 위치에 놓고 나머지 레코드 중에서 다시 최소값을 찾아 두번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식이다.
9 4 5 11 8
오름차순 정렬 시
먼저, 9와 4 비교
↓
4 9 5 11 8
4 9 5 11 8
4 9 5 11 8
4 9 5 11 8 ··· 1회전 결과
↓
4 9 5 11 8
두번째, 세번째 비교
↓
4 5 9 11 8
4 5 9 11 8
4 5 9 11 8 ··· 2회전 결과
↓
4 5 9 11 8
세번째, 네번째 비교
↓
4 5 9 11 8
4 5 8 11 9 ··· 3회전 결과
↓
4 5 8 11 9
네번째, 마지막 비교
↓
4 5 8 9 11 ··· 4회전 결과
댓글 없음:
댓글 쓰기