하나의 파일을 구성하고 있는 여러 개의 레코드들을 레코드 내의 특정한 항목(Key)을 기준으로 순서 있게 배열하고자할때 사용하는 방법으로 내부 순서배열과 외부 순서배열이 있습니다.
순서배열(정렬)(SORTING)에 대해 알아 보겠습니다.
【참고】키(Key)
파일 내의 레코드를 식별하기 위한 특정한 항목으로 정렬(Sort)과 검색(Search) 등에 사용한다.
【참고】정렬방법
Ascending : 오름차순. 작은 순서부터 큰 순으로 Sort한다.
Descending : 내림차순으로 큰 순부터 작은 순으로 Sort한다.
7-1. 내부순서 배열(Internal Sort)
자료 이동속도가 빠른 주기억 장치내에서 시행되는 Sorting으로 주기억장치내에서 이루어지는 관계로 보조기억장치를 이용하는 외부 SORT에 비해 적은 양의 데이터를 취급할 수 있다.
【참고】내부순서 배열(Internal Sort) 요약
7-1-1. 삽입법 ( Insertion sort)
(1) 삽입 소트( Insertion sort)
가장 간단한 순서배열의 하나로 이미 SORT된 부 파일에 새로운 한개의 Record를 입력하여 그순서를 찾아 삽입 시킨다.
【예】데이타의 수가 5인 경우 데이터가 5, 4, 3, 2, 1이라 할때의 삽입 소트
(2) 쉘 소트(Shell Sort)
입력파일을 여러개의 부파일로 간주하여 Insertion Sort의 기법으로 행하는 방법.
【예】N이 10인 입력파일 R=( 6, 5, 4, 3, 2, 1)와 5개의 매개 변수값 H=(1, 2, 3, 4, 5)이 주어져 있을때 의 Shell Sort.
결과 : 1, 2, 3, 4, 5, 6
7-1-2. 교환법
(1) 버블 소트(Bubble Sort)
주어진 파일(File)에서 인접한 2개레코드의 키를 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 소팅 방법. 총 레코드의 교환회수
【예】N=5인 경우의 입력 Record를 (5, 4, 3, 2, 1)이라고 할때 N-1회전, 즉 4번만에 Sort는 끝난다.
【예】20개의 자료를 버블 소팅(Bubble Sorting)하기 위한 최대 비교 횟수는
이며 (N은데이터 개수, (N-1)은 비교 횟수이다) 20*19/2=190회 비교하게 된다.
(2) 퀵 소트(Quick Sort)
list를 두개의 Sublist로 나누어 가운데값을 중심으로 Sort하는 가장 속도가 빠른 Sort이다.
7-1-3. 선택법
(1) 힢 소트(Heap Sort:Tree Sort)
Heap구조를 이용 Sort로 Heap구조는 Tree구조로 각 노드의 키값이 자 노드들의 키값보다 작지 않는 특징을 갖는다.
(2) 셀렉션 소트(Selection Sort)
n개의 Record로부터 최소값을 찾아 첫번 레코드 위치에 놓는 것이 1회전 결과이며 나머지(n-1)개중 최소값을 찾아 두 번째위치에 놓는것이 2회전 결과 이다. 최종적으로 (n-1)회전에서는 (n-1)번째 레코드와 n번째 레코드중 키값이 작은 레코드를 (n-1)번째에 놓음으로 작업을 끝낸다.
【예】N이 5인 경우의 입력레코드를(5, 4, 3, 2, 1)이라고 할때
Selection Sort를 적용하면 다음과 같다(오름차순)
7-1-4. 래딕스 소트(Radix Sort)
분배법의 Sort로 여러개의 키를 가진 다중키 정렬에 적합하며 카드소팅에 이용된다.
7-1-5. Merge법
(1) 2-Way Merge Sort
내부 순서배열에서 유일하게 Merge법을 사용하는 Sort로 순서 배열이 끝난 2개의 파일을 병합하여 완전히 배열을 갖춘 하나의 파일로 만든다. 메모리를 가장 많이 차지하며 패스 횟수는 [log2n]이고, 연산 시간은 0[log2n]이다.
【예】아래와 같이 Key값의 Record를 2Way Merge Sort 하여보자
| 보기 | (Key값 : 19 11 04 26 42 35 21 49) |
【연습】26, 5, 37, 9, 61, 11, 59, 15, 48, 12를 2Way Merge Sort하라.
7-1-6. 기수 변환 정렬
주어진 각 파일의 각 키를 다른 진수 특히 2진수로 변환하여 정렬하는 방식의 Sort방식이다.
7-2. 외부순서배열(External Sort)
외부배열순서배열은 테이프나 디스크 같은 보조기억 장치내에서 이루어지며 많은 양의 자료를 Sort할 수 있다. 보조기억장치를 사용하는 관계로 속도는 내부 Sort보다 느리다. (2Way, 3Tape필요)
⑴ 밸런스 머지(Balanced Merge Sort)
적어도 3개의 Tape가 필요하며, Key를 서로 비교하여 Sort한다.
⑵ 캐스케이드 정렬(Cascade Merge Sort)
6개 이내의 Tape를 Sorting하기에 편리하며, 여러개의 Tape를 Sort해 나가다 이중 1개의 Tape의 Sort가 끝나면 Sort를 마친다.
⑶ 다상 정렬(Polyphase Merge Sort)
Fibonacci수열의 개념을 이용한 Sort로 적어도 3개의 Tape필요
⑷ 오시레이팅(Oscillating Merge Sort)
Tape를 역 읽기(Back Read)성질을 이용한 Sort.
7-3. 소팅 알고리즘(Sorting Algorithm)
소팅 알고리즘에 영향을 미치는 주된 요인은 다음과 같다.
(1) 컴퓨터 시스템의 특성
(2) sorting해야할 자료의 양
(3) 초기 배열의 배열 상태
(4) key값의 분포
(5) 키의 비교횟수, 레코드의 이동수, 혹은 필요한 작업공간의 크기
이상 “순서배열(정렬)(SORTING)”에 대해 알아 보았습니다.
답글 남기기