[2023 정보처리기사] 2과목 – 2. 정렬, 해싱 함수

1. 정렬(Sort)이란?

: 데이터를 정해진 순서대로 가지런하게 나열하는 것.

  1. 1. 삽입 정렬(Insertion Sort)

: 정렬된 파일에 새로운 하나의 레코드를 순서에 따라 삽입시켜 정렬하는 방법.

Ex) 삽입 정렬을 이용한 오름차순 정렬

1.

a. 두 번째 배열 값을 키(Key)값으로 지정.

b. ‘키값(5)‘과 ’키값의 앞 배열의 값(6)‘을 비교하여 키값보다 크면 한 칸을 뒤로 밀어주고(c) 밀린 배열의 자리에 키값을 삽입한다.

2. 다음 배열의 값을 키값으로 지정한 후 a,b,c의 과정을 반복한다.

  1. 2. 버블 정렬(Bubble Sort)

: 인접한 데이터를 비교하면서 그 크기에 따라 데이터의 위치를 바꾸어 정렬하는 방법.

Ex) 버블 정렬을 이용한 오름차순 정렬

1. 첫 번째 배열부터 인접한 1, 2번 배열의 크기를 비교하여 작은 값이 앞으로 위치하도록 치환한다.

2. 다음 인접한 2, 3번 배열의 크기를 비교하여 동일작업을 수행한다.

3. 1번의 회전이 끝나면 가장 큰 수가 가장 뒤로 온다.

  1. 3. 선택 정렬(Selection Sort)

: n개의 레코드 중에서 최소값(or 최대값)을 찾아 첫번째 레코드 위치에 놓고, 나머지 n-1개의 레코드 중에서 최소값(or 최대값)을 찾아 두번째 레코드 위치에 놓는 방법.

Ex) 선택 정렬를 이용한 오름차순 정렬

1. 첫 번째 (6)값을 기준값으로 선택하고 기준값 뒤의 값들과 하나씩 비교하여 기준값보다 작은 경우 위치를 치환한다.

2. 1번의 회전이 끝나면 가장 작은 수가 가장 앞으로 온다.

 

2. *해싱함수

*해싱: 해싱함수(Hashing Function)를 이용하여 레코드키에 대한 해시 테이블(Hash Table)내의 홈 주소(Home Address)를 계산하여 주어진 레코드에 접근하는 방식.

  2. 1. 해싱함수 종류

• 폴딩법(중첩 방법): 레코드 키를 여러 부분으로 나누고, 나눈 부분의 각 숫자를 더하거나 XOR한 값을 홈 주소로 사용하는 방법.
• 제산법: 레코드키로 해시표의 크기보다 큰 수 중에서 가장 작은 소수로 나눈 나머지를 홈주소로 사용하는 방법. 나머지 연산자(%)를 사용.
• 기수변환법: 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수를 절단하고, 이를 다시 주소 벙위에 맞게 조정하는 방법.
• 숫자분석법(계수분석법): 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 사용하는 방식..
• 중간 제곱 방법: 레코드 키 값을 제곱한 후에 결과값의 중간 부분에 있는 몇 비트를 선택하여 해시 테이블의 홈주소로 사용하는 방법.

 

3. 알고리즘에 따른 시간 복잡도

대표 알고리즘	설명	복잡도
해시 함수	항상 일정한 속도로 작동. (상수형 복잡도)	O(1)
이진 탐색	문제를 해결하기 위해 log2N번의 수행시간을 가짐. (로그형 복잡도)	O(logN)
순차 탐색	수행 시간이 자료 크기와 직접적 관계 (선형 복잡도)	O(n)
퀵 정렬 합병 정렬	문제를 해결하기 위해 Nlog2N번의 수행시간을 가짐	O(NlogN)
선택 정렬 버블 정렬 삽입 정렬	N의 크기가 작을 땐 N²이 NlogN보다 느릴 수 있음	O(N²)