1. 정렬(Sort)이란?
: 데이터를 정해진 순서대로 가지런하게 나열하는 것.
![[정렬예제]](https://notedailyit.co.kr/wp-content/uploads/2023/08/IMG_0890.jpeg)
1. 1. 삽입 정렬(Insertion Sort)
: 정렬된 파일에 새로운 하나의 레코드를 순서에 따라 삽입시켜 정렬하는 방법.
Ex) 삽입 정렬을 이용한 오름차순 정렬
![[삽입 정렬]](https://notedailyit.co.kr/wp-content/uploads/2023/08/IMG_0891.jpeg)
1.
a. 두 번째 배열 값을 키(Key)값으로 지정.
b. ‘키값(5)‘과 ’키값의 앞 배열의 값(6)‘을 비교하여 키값보다 크면 한 칸을 뒤로 밀어주고(c) 밀린 배열의 자리에 키값을 삽입한다.
![[삽입 정렬]](https://notedailyit.co.kr/wp-content/uploads/2023/08/IMG_0892.jpeg)
2. 다음 배열의 값을 키값으로 지정한 후 a,b,c의 과정을 반복한다.
1. 2. 버블 정렬(Bubble Sort)
: 인접한 데이터를 비교하면서 그 크기에 따라 데이터의 위치를 바꾸어 정렬하는 방법.
Ex) 버블 정렬을 이용한 오름차순 정렬
![[버블 정렬]](https://notedailyit.co.kr/wp-content/uploads/2023/08/IMG_0893.jpeg)
1. 첫 번째 배열부터 인접한 1, 2번 배열의 크기를 비교하여 작은 값이 앞으로 위치하도록 치환한다.
2. 다음 인접한 2, 3번 배열의 크기를 비교하여 동일작업을 수행한다.
3. 1번의 회전이 끝나면 가장 큰 수가 가장 뒤로 온다.
1. 3. 선택 정렬(Selection Sort)
: n개의 레코드 중에서 최소값(or 최대값)을 찾아 첫번째 레코드 위치에 놓고, 나머지 n-1개의 레코드 중에서 최소값(or 최대값)을 찾아 두번째 레코드 위치에 놓는 방법.
Ex) 선택 정렬를 이용한 오름차순 정렬
![[선택 정렬]](https://notedailyit.co.kr/wp-content/uploads/2023/08/IMG_0894.jpeg)
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²) |