정렬(Sort)이란?
: 파일을 구성하는 각 레코드를 특정 키 항목을 기준으로 오름차순/내림차순으로 재배열하는 작업을 말한다
정렬기법
1. 내부정렬기법
- 정의 : 데이터량이 적을 때 주기억장치 내에서 정렬하는 방법
- 특징 : 속도는 빠르나 정렬할 자료의 양이 많을 경우 부적합하다.
- 내부정렬의 종류
· 삽입 정렬(Insertion Sort)
: 이미 순서화된 파일에 새로운 레코드를 추가하여 순서에 맞게 배치 (2번째 값부터 시작한다)
· 쉘 정렬(Shell Sort)
· 선택 정렬(Select Sort)
: 레코드의 최소값을 찾아 첫번째 위치에 놓고 다음 최소값을 찾아 두번째 위치에 놓는 방법을 반복하여 정렬
· 버블 정렬(Bubble Sort)
: 인접한 값과 비교하여 정렬하는 방식. 끝에 값부터 정해진다.
· 퀵 정렬(Quick Sort)
· 힙 정렬(Heap Sort)
· 2-Way 합병 정렬(Merge Sort)
: 값들을 2개씩 묶어가면서 비교하여 정렬
· 기수 정렬(Radix Sort) = Bucket Sort
2. 외부정렬기법
- 정의 : 대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에
테이프나 디스크 내에서 각 서브파일을 합병하는 방법
- 특징 : 속도는 느리지만 자료의 양이 많은 경우 효과적이다.
- 외부정렬의 종류
· 진동 병합 정렬(Oscillating Merge Sort)
· 캐스케이드 병합 정렬(Cascade Merge Sort)
· 폴리파즈 병합 정렬(Polyphase Merge Sort)
· 균형 병합 정렬(Balance Merge Sort)
정렬 알고리즘의 선택시 고려사항
1. 키값들의 분포 상태
2. 소요공간 및 작업시간
3. 정렬에 필요한 기억공간의 크기
4. 데이터의 양
5. 초기 데이터의 배열상태
6. 사용 컴퓨터 시스템의 특성
: 파일을 구성하는 각 레코드를 특정 키 항목을 기준으로 오름차순/내림차순으로 재배열하는 작업을 말한다
정렬기법
1. 내부정렬기법
- 정의 : 데이터량이 적을 때 주기억장치 내에서 정렬하는 방법
- 특징 : 속도는 빠르나 정렬할 자료의 양이 많을 경우 부적합하다.
- 내부정렬의 종류
· 삽입 정렬(Insertion Sort)
: 이미 순서화된 파일에 새로운 레코드를 추가하여 순서에 맞게 배치 (2번째 값부터 시작한다)
· 쉘 정렬(Shell Sort)
· 선택 정렬(Select Sort)
: 레코드의 최소값을 찾아 첫번째 위치에 놓고 다음 최소값을 찾아 두번째 위치에 놓는 방법을 반복하여 정렬
· 버블 정렬(Bubble Sort)
: 인접한 값과 비교하여 정렬하는 방식. 끝에 값부터 정해진다.
· 퀵 정렬(Quick Sort)
· 힙 정렬(Heap Sort)
· 2-Way 합병 정렬(Merge Sort)
: 값들을 2개씩 묶어가면서 비교하여 정렬
· 기수 정렬(Radix Sort) = Bucket Sort
2. 외부정렬기법
- 정의 : 대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에
테이프나 디스크 내에서 각 서브파일을 합병하는 방법
- 특징 : 속도는 느리지만 자료의 양이 많은 경우 효과적이다.
- 외부정렬의 종류
· 진동 병합 정렬(Oscillating Merge Sort)
· 캐스케이드 병합 정렬(Cascade Merge Sort)
· 폴리파즈 병합 정렬(Polyphase Merge Sort)
· 균형 병합 정렬(Balance Merge Sort)
정렬 알고리즘의 선택시 고려사항
1. 키값들의 분포 상태
2. 소요공간 및 작업시간
3. 정렬에 필요한 기억공간의 크기
4. 데이터의 양
5. 초기 데이터의 배열상태
6. 사용 컴퓨터 시스템의 특성