정렬(Sorting)과 해싱(Hashing)

Presentation on theme: "정렬(Sorting)과 해싱(Hashing)"— Presentation transcript:

1 정렬(Sorting)과 해싱(Hashing)
CHAPTER 7 정렬(Sorting)과 해싱(Hashing)

2 7.1 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
파일을 하나의 기준 값을 중심으로 두 개의 서브파일로 분할하여, 앞쪽의 파일 내의 모든 키는 뒤쪽의 파일 내의 어떤 키보다도 작도록 분할한다. 나누어진 서브파일에 대해서 동일한 방식의 분할을 서브파일의 크기가 1이 될 때까지 재귀적으로 수행하면 최종적으로 서브파일의 크기가 1이 되면 완전히 정렬된 상태의 파일이 구성된다.

3 2가지 파일 분할방식 0번째 키를 기준값으로 설정하는 방식
1번째 키부터 시작 2, 3번 방향으로 기준값보다 큰 키값을 만나면 그 키를 선택, n-1번째 키부터 시작 n-2, n-3번 방향으로 기준값보다 작은 키 값을 가진 키를 만나면 그 키를 선택하여 두 키 값을 교환한다. 선택되었던 두 키의 다음 위치에서부터 동일한 과정을 반복한다. 양쪽 방향에서 진행하는 순서가 교차하면 정지한다. 가장 나중에 선택한 기준 키 값보다 작은 키를 기준 키와 교환한다. 2. 기준 키 값을 파일내의 중간위치에 있는 키 값으로 설정하는 방식 기준 키 값의 앞에서 기준 키 값보다 큰 값을, 뒤에서 기준 키 값보다 작은 값을 선택하여 교환한다.

4 퀵 정렬은 하나의 파일을 두 개의 파일로 나누어질 때 두 서브 파일의 크기가 비슷하게 되면 비교의 횟수가 감소하게 된다
퀵 정렬은 하나의 파일을 두 개의 파일로 나누어질 때 두 서브 파일의 크기가 비슷하게 되면 비교의 횟수가 감소하게 된다. 그러나 두 서브파일의 크기의 차가 크거나 또는 아예 하나의 서브파일 밖에 만들어지지 않는 경우 수행시간이 길어진다. 예를 들어, 정렬하고자 하는 순서의 역순으로 데이터가 나열되어 있는 경우에는 서브파일이 항상 하나 밖에 생성되지 않는다.

5 퀵 정렬의 수행시간 • 평균 비교횟수가 nLog2n => O(nLog2n)

6 • 최악의 경우(서브파일이 하나만 존재) => O(n2)
void quick_sort(int list[], int f, int n) {        //f는 시작위치, n은 끝 위치     int i, j, k, temp; void quick_sort(int list[], int f, int n);    void prnt(int list[]); if(f < n) {         i=f+1;         j=n;         k=list[f];                       //k는 기준값         if(i==j) {             if(list[j] < k) {                 temp=list[j];                 list[j]=k;                 list[f]=temp; }       } while(i < j) {             while((list[i] <= k) && (i<n))                 i++;             while(list[j] >= k && (j>f))                 j--;             if(i < j) {                  //기준값보다 큰, 작은 값을 교환                 temp=list[i];                 list[i]=list[j];                 list[j]=temp;             }         }         if(i > j) {             temp=list[f];                //기준값과 교환             list[f]=list[j];             list[j]=temp;         }         quick_sort(list, f, j-1);        //왼쪽 서브파일에 대해 반복         quick_sort(list, j+1, n);        //오른쪽 서브파일에 대해 반복     } }

7 • 최악의 경우(서브파일이 하나만 존재) => O(n2)

8 7.1 퀵정렬(Quick Sort) 주어진 데이터 파일을 피봇(pivot) 값에 의해 부분 파일로 분할하여 정렬하는 방법
정렬해야 될 데이터 파일 내의 중간에 있는 키 값에 의해 두 개의 부분 파일로 나눈다. 나누어진 부분 파일들을 각각 정렬한 다음 다시 합친다. 파일 내에 있는 임의의 데이터 x가 위치 i에 재배치되는 조건 ⅰ) 처음부터 i-1 번째 위치의 모든 데이터는 피봇의 값 x보다 같거나 작다.  ⅱ) i+1 번째 위치에서 파일의 마지막 위치까지 있는 모든 데이터는 피봇의 값 x보다 같거나 크다.

9 7.1 퀵정렬(Quick Sort) 알고리즘

10 7.1 퀵정렬(Quick Sort) 데이터 파일이 [ ]인 키 값을 갖는 10개의 레코드들로 구성된 파일의 퀵정렬 알고리즘 수행 과정

11 7.2 합병 정렬(Merge Sort) 이미 정렬된 두 개의 파일을 합쳐서 새로운 정렬된 파일을 만드는 방법이다.
정렬된 B와 C를 합쳐서 새로운 정렬 파일 만드는 방법. 알고리즘

12 7.3 해싱(Hashing) 해싱(hashing)이란? 해싱 함수 f 란?
레코드가 테이블에 저장되어 있을 때 레코드의 키 값을 주면, 이 키 값을 어떤 수학적 함수에 의하여 테이블의 주소로 변환 시켜서 원하는 레코드를 탐색하는 것. 해싱 함수 : 레코드의 키 값을 테이블의 주소로 변화시키는 수학적 함수. 해싱 테이블 : 레코드들이 테이블 형태로 저장되어 해싱 함수에 의해 접근, 호출될 때 이 테이블을 해싱 테이블이라 함. 해싱 함수 f 란? 레코드의 키를 해싱 테이블의 주소로 변환시키는 함수 X를 레코드들의 키들의 집합, Y를 해싱 테이블의 주소들의 집합이라고 할 때 f는 f : X -> Y 인 함수이다.

13 7.3 해싱(Hashing) 정적 해싱(Static Hashing)
이름(identifier)을 해싱 테이블(Hashing Table)이라는 일정크기의 테이블에 저장할 때 이름의 저장 주소 또는 위치 결정을 위해 해싱함수 f를 사용한다. x를 M으로 나눈 모듀러 값으로 변환하는 해싱 함수

14 7.3 해싱(Hashing) 정적 해싱(Static Hashing)
해싱 함수를 이용하여 저장할 때 이미 다른 레코드가 저장되어서 충돌이 발생하면 다음과 같은 해싱법을 사용. 개방 주소 방법(Linear Open Addressing) : 다음 빈 공간(table)에 저장 체이닝(Chaining) 방법 : 포인터를 이용하여 같은 해싱 함수를 갖는 레코드를 연결리스트로 연결

15 7.3 해싱(Hashing) (2) 동적 해싱(Dynamic Hashing)
DBMS와 같이 해싱 테이블을 모두 주기억장치에 둘 때 주기억장치 공간이 낭비되는데, 빠른 검색시간을 유지하면서 파일의 크기가 동적으로 증가 또는 감소할 수 있도록 확장한 기법이 동적 해싱이다. 2진(Binary) 표현의 자리 수를 이용하여 확장한 예)