04. 정렬, 탐색기법

제1항 정렬, 탐색기법

(１) 정렬

1) 정렬(sort)의 정의

① 레코드나 데이터에 담긴 키값에 따라 순서대로 나열하는 것

② 정렬은 정렬되지 않은 항목 또는 레코드의 리스트를 각 레코드의 값에 기초한 기준에 따라 순서 있게 나열하는 것이다.

③ 초기에 정렬되지 않은 레코드의 순서를 정렬될 때까지 재배치하는 과정

 

그림 37. 정렬의 종류

 

2) 정렬기법

① 내부정렬기법

ü 정의

• 데이터량이 적을 때 주기억장치 내에서 정렬하는 방법

ü 특징

• 속도는 빠르나, 정렬할 자료의 양이 많은 경우 부적합

ü 종류

• 히프 정렬(heap sort)

• 기수 정렬(radix sort)

• 선택 정렬(selection sort)

• 버블 정렬(bubble sort)

• 퀵 정렬(quick sort)

• 삽입 정렬(insertion sort)

• 쉘 정렬(shell sort)

 

② 외부정렬기법

ü 정의

• 대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에 테이프나 디스크 내에서 각 서브 파일을 합병하는 방법

ü 특징

• 속도는 느리지만 정렬하고자 하는 자료의 양이 많을 경우 효과적 (주기억장치+보조기억장치)

ü 종류

• 진동 병합 정렬(oscillating merge sort)

• 밸런스 병합 정렬(balanced merge sort)

• 캐스캐이드 병합 정렬(cascade merge sort)

• 폴리파즈 병합 정렬(polyphase merge sort)

 

 

3) 정렬기법 종류

① 버블 정렬(bubble sort)

• 버블정렬은 인접한 두 키를 비교한 결과로 정렬하는데 만약 비교하였을 때 두 키의 순서가 다르다면 교환하고 그렇지 않다면 그대로 두는 방법이다.

• 정렬과정이 물속 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 붙여진 이름이다.

 

 

 

② 삽입 정렬(insertion sort)

• 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘

- 데이터 집합에서 정렬 대상이 되는 요소들을 선택합니다. 이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개이지만 알고리즘 반복횟수가 늘어날 때마다 1개씩 커집니다. 정렬 대상의 최대 범위는 “데이터 집합의 크기 – 1” 이 됩니다.

- 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 있는지 확인합니다. 만약 그렇지 않다면, 이 요소를 정렬 대상에서 뽑아내고, 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾습니다. 여기서 적절한 곳이라 함은 데이터 집합의 가장 왼쪽을 기준으로 했을 때 자신보다 더 작은 요소가 없는 위치를 말합니다.

- 뽑아 든 요소를 삽입할 적절한 곳을 찾았다면, 정렬 대상 내에서 삽입할 값보다 큰값을 갖는 모든 요소를 한자리씩 오른쪽으로 이동시키고 새로 생긴 빈 자리에 삽입시킵니다.

- 전체 대이터 집합의 정렬이 완료될 때까지 1~3를 반복합니다.

 

• 이 정렬 알고리즘은 지급 완료 수표나 카드를 정렬된 채로 손에 쥐고서 그것들 사이에 적당한 위치에 정렬되지 않은 것을 한 개씩 삽입할 때 발생할 수 있다.

 

 

③ 선택 정렬(selection sort)

• 레코드의 최소값을 찾아 첫 번째 위치에 놓고 다음 최소값을 찾아 두 번째 위치에 놓는 방법을 반복하여 정렬함.

 

④ 히프 정렬(heap sort)

• 연산 시간이 최악과 평균의 경우, 모두 0(n logⁿ)으로 빠른 속도를 가짐

• 전이진 트리(complete tree)를 이용한 정렬 방식

• 이진 트리를 힙 정렬로 변환

- 주어진 레코드들을 순서대로 넣어 진이진 트리로 구성

- 전이진 트리의 노드의 역손으로 자식노드와 부모노드를 비교하여 큰값을 위로 올림

- 교환된 노드들을 다시 검토하여 위의 고정을 반복한다.

 

 

⑤ 퀵 정렬(quick sort)

• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽에 모이도록 서로 교환시키는 부분 교환 정렬법

 

⑥ 기수 정렬(radix sort)

• 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬하는 기법

 

⑦ 2-way 합병 정렬

• 주어진 입력 파일을 크기가 2인 서브 파일로 모두 나누어서 각 서브 파일들을 정렬하는 방법

 

4) 정렬 알고리즘의 선택 시 고려사항

① 키 값들의 분포상태

② 소요 공간 및 작업시간

③ 정렬에 필요한 기억공간의 크기

④ 데이터의 양

⑤ 초기 데이터의 배열상태

⑥ 사용 컴퓨터 시스템의 특성

 

 

(２) 탐색기법

1) 탐색기법의 종류

① 이진 검색(binary search)

ü 일정한 순서로 배열된 레코드를 2개 부분으로 되풀이하여 나누어서 한 부분은 버리고 남은 부분을 검색하는 방법

ü 자료가 반드시 정렬되어 있어야 함 (이진 검색의 선행 조건)

ü 정렬된 연접 리스트에서 특정 레코드가 있다고 알려진 리스트의 남겨진 반쪽 부분을 되풀이하여 보면서 특정 레코드를 찾는 빠른 방법

ü 다음과 같이 R={2,3,5,7,8,9,10} 일 때, 이진 검색 방법으로 8을 찾을 경우 비교 횟수는?

 

 

 

② 보간 검색(Interpolation search)

ü 찾고자 하는 레코드 키가 있음직한 위치를 추정하여 검색하는 방법

 

2) 해싱(hashing)

① 해싱의 정의

ü 키 값으로부터 레코드가 저장되어 있는 주소를 직접 계산하여, 산출된 주소로 바로 접근하는 방법, 키-주소 변환 방법이라고도 함

ü 검색 방법 중 속도는 가장 빠르지만 충돌현상 시 오버플로 해결의 부담이 과중되며 많은 기억공간을 요구하는 검색 방법

 

② 해시 테이블(hash table)

ü 자료가 저장되는 전체 저장소를 해시 테이블(hash table)이라고 한다.

ü 해시 테이블은 여러 개의 버킷(bucket)으로 나누어지는데 데이터를 삽입할 때 데이터의 값으로부터 적절한 버킷을 선택해서 삽입해야 한다.

ü 버킷은 여러 개의 슬롯(slot)으로 구성되는데 슬롯은 버킷에 데이터가 저장되는 단위이다. 예를 들면 주소록의 각 페이지별로 한 명만 적을 수 있는 것이 아니라 여러명을 적을 수 있어야 하는데 이때 한명의 주소를 적는 칸을 슬롯이라고 한다.

ü 버킷(bucket)

• 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미

ü 슬롯(slot)

• 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성

ü 충돌(collision)

• 레코드를 삽입할 때 2개의 상이한 레코드가 똑 같은 주소로 해싱 되는 것을 의미

ü 동의어(synonym)

• 해싱 함수의 값이 같은 키들의 집합

 

③ 해싱함수의 종류

ü 중간제곱(mid-square) 방법

• 레코드의 키를 제곱한 후 그 중간 부분의 값을 목적 주소로 사용하는 방법

ü 숫자분석(digit analysis) 방법

• 레코드 키를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여 목적 주소로 사용하는 방법

ü 제산(division) 방법

• 레코드의 키를 해시테이블의 크기보다 큰 소수로 나누는 방법

ü 중첩(접지) 방법(Folding method)

• 주어진 키를 여러 부분으로 나누고, 각 부분의 값을 더하거나 배타적 논리합(XOR, exclusive OR) 연산을 통하여 나온 결과로 주소를 취하는 방법

ü 기수(radix) 변환법

• 어떤 진법으로 표현된 주어진 레코드 키 값을 다른 진법으로 간주하고 키 값을 변환하여 홈 주소로 취하는 방식

 

④ 오버플로 처리방법

ü 충돌(collision)이 발생했을 때 버킷에 저장할 슬롯이 없다면 오버플로우가 발생한다.

ü 재해싱 방법(rehashing)

• 여러 개의 해싱함수를 준비하였다가 충돌 발생시 새로운 해싱함수를 적용하여 새로운 해시표를 생성하는 방법

ü 개방 주소법(open addressing)

• 충돌(collision)이 발생했을 때 순서대로 다음 버킷에 저장하는 방법

ü 체인방법

• 오버플로우 발생시 이를 별도의 기억 공간에 두고 링크로 연결하여 사용하는 방법

ü 폐쇄 주소법(close addression)

• 별도의 오버플로우 영역에 저장하고 체인(chain)으로 홈 버킷에 연결한다.

• Direct chaining: 해시 테이블 내의 빈 공간에 오버플로우 레코드를 보관한다.

• Indirect chaining: 해시 테이블과는 별도의 기억공간에 오버플로우 레코드를 보관한다.

 

 

 

제2항 인덱스구조

(１) 인덱스 (index)

1) 인덱스의 정의

① 검색을 빠르게 하기 위해 만든 보조적인 데이터 구조

② B트리, B+트리, 트라이 등의 자료구조를 사용하여 구현함

③ 인덱스 파일

ü 검색수를 줄이기 위해 다단계 인덱스를 사용

2) 인덱스의 특징

① 인덱스는 하나 이상의 필드로 만들어도 됨

② 인덱스를 통해서 테이블의 레코드에 대한 액세스를 빠르게 수행할 수 있음

3) 트라이 (trie)

① 검색을 위한 키값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키값을 구성하는 구조

② 트라이의 차수는 키 값을 표현하기 위해 사용하는 문자의 수(radix)에 의해 결정함

③ 키 값의 분포를 미리 예측할 수 있다면 기억장소를 절약할 수 있음

④ 트라이의 크기는 나타내려고 하는 키 값의 기수와 키 필드 길이에 의해 결정됨

⑤ 키 값이 문자열 또는 숫자일 경우 일련의 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되었을 때, 즉 전체 키 값의 길이보다 키 값들 사이에 별개의 전위(prefix) 수가 작을 때 적합함

⑥ 가변 길이의 키 값을 효과적으로 나타낼 수 있으며, 삽입 및 삭제 시 노드의 분열과 병합이 없음

 

4) 인덱스 구분

① 정적인덱스

ü 데이터 파일의 레코드가 삽입되거나 삭제됨에 따라 인덱스의 내용은 변하지만 구조자체는 변하지 않음

 

② 동적인덱스

ü 인덱스나 데이터파일을 블록으로 구성하고 각 블록에는 추가로 삽입될 레코드를 감안하여 빈 공간을 미리 예비해두는 인덱스 방법

ü 레코드의 삽입으로 인해 블록에 레코드가 가득 차면 동적으로 분열 됨

 

ü 레코드의 삭제로 인해 일정 수의 레코드가 블록에 유지되지 않으면 블록의 합병이 일어남