1장 - 데이터 입・출력 구현 | 섹션3. 정렬(Sort), 섹션4. 검색 - 이분 검색 / 해싱

2024년도 시나공 필기 책 내용 정리

---

섹션3. 정렬(Sort)

 

1. 삽입 정렬(Insertion Sort)

 

• 가장 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬
• 두 번째 키와 첫 번째 키를 비교해 순서대로 나열(1회전) 하고 이어서 세 번째 키를 첫 번째, 두 번째 키와 비교해 순서대로 나열(2회전)하고, 계속해서 n번째 키를 앞의 n - 1개의 키와 비교하여 알맞는 순서에 삽입하여 정렬하는 방식
• 평균과 최악 모두 수행 시간 복잡도는 O(n^2)임

초기상태 8,5,6,2,4를 삽입 정렬로 정렬

8

5

6

2

4

 

 

• 1회전 - 두 번째 값을 첫 번째 값과 비교하여 5를 첫 번째 자리에 삽입하고 8을 한 칸 뒤로 이동시킴
  

5

8

6

2

4

 

• 2회전 - 세 번째 값을 첫 번째, 두 번째 값과 비교하여 6을 8의 자리에 삽입하고 8은 한칸 뒤로 이동시킴

5

6

8

2

4

 

• 3회전 - 네 번째 값 2를 처음부터 비교하여 맨 처음에 삽입하고 나머지를 한 칸씩 뒤로 이동시킴

2

5

6

8

4

 

• 4회전 - 다섯 번째 값 4를 처음부터 비교하여 5자리에 삽입하고 나머지를 한칸씩 뒤로 이동시킴

2

4

5

6

8

 

---

2. 쉘 정렬(Shell Sort)

 

• 삽입 정렬(Insertion Sort)을 확장한 개념
• 입력 파일을 어떤 매개변수(h)의 값으로 서브파일을 구성하고 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식(보통 h = 3루트n) 즉, 임의의 레코드 키와 h값만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는 것을 반복하는 정렬 방식
• 입력 파일이 부분적으로 정렬되어 있는 경우에 유리한 방식
• 평균 수행 시간 복잡도는 O(n^1.5)이고, 최악의 수행 시간 복잡도는 O(n^2)임

---

3. 선택 정렬(Selction Sort)

 

• n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
• 평균과 최악 모두 수행 시간 복잡도는 O(n2)

초기상태 8,5,6,2,4를 삽입 정렬로 정렬

8

5

6

2

4

 

• 1회전

2

6

8

5

4

 

• 2회전

2

4

8

6

5

 

• 3회전

2

4

5

8

6

 

• 4회전 

2

4

5

6

8

 

---

4. 버블정렬(Bubble Sort)

 

• 주어진 파일에서 인접한 두개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
• 계속 정렬 여부를 플래그 비트(f)로 결정함
• 평균과 최악 모두 수행 시간 복잡도는 O(n^2)임

초기상태 8,5,6,2,4를 삽입 정렬로 정렬

8

5

6

2

4

 

• 1회전

5

6

2

4

8

 

• 2회전

5

2

4

6

8

 

• 3회전

2

4

5

6

8

 

• 4회전 - 이동 없음

2

4

5

6

8

---

5. 퀵 정렬(Quick Sort)

 

• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에, 큰 값을 오른쪽 서브파일로 분해시키는 방식으로 정렬
• 위치에 관계없이 임의의 키를 분할 원소로 사용할 수 있음
• 정렬 방식 중에서 가장 빠른 방식
• 프로그램에서 되부름을 이용하기 때문에 스택이 필요함
• 분할(Divide)과 정복(Conquer)을 통해 자료를 정렬
  
  • 분할(Divide) : 기준값인 피봇(Pivot)을 중심으로 정렬할 자료들을 2개의 부분집합으로 나눔
  • 정복(Conquer) : 부분집합의 원소들 중 피봇(Pivot)보다 작은 원소들은 왼쪽, 큰 원소들은 오른쪽 부분집합으로 정렬
  • 부분집합의 크기가 더이상 나누어질 수 없을 때까지 분할과 정복을 반복수행
• 평균 수행 시간 복잡도는 O(nlog2n)이고, 최악의 수행시간 복잡도는O(n^2)임

---

6. 힙 정렬(Heap Sort)

 

• 전이진 트리(Complete Binary Tree)를 이용한 정렬 방식
• 구성된 전이진 트리를 Heap Tree로 변환하여 정렬
• 평균과 최악 모두 시간 복잡도는 O(nlog2n)임

---

7. 2 - Way 합병 정렬(Merge Sort)

 

• 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
• 두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정함
• 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브리스트로 만듦
• 위 과정에서 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복
• 평균과 최악 모두 시간 복잡도는 O(nlog2n)임

71, 2, 38, 5, 7, 61, 11, 26, 53, 42를 2 - Way 합병 정렬로 정렬

 

• 1회전 : 두개 씩 묶은 후 각각의 묶음 안에서 정렬
  
  • (71, 2) (38, 5) (7, 61) (11, 26) (53, 42)
  • (2, 71) (5, 38) (7, 61) (11, 26) (42, 53)
• 2회전 : 묶여진 묶음을 두개씩 묶은 후 각각의 묶음 안에서 정렬
  
  • ((2, 71) (5, 38)) ((7, 61) (11, 26)) (42,53)
  • (2, 5, 38, 71) (7, 11, 26, 61) (42, 53)
• 3회전 : 동일 
  
  
  • ((2, 5, 38, 71,) (7, 11, 26, 61))(42, 53)
  • (2, 5, 7, 11, 26, 38, 61, 71)(42,53)
• 4회전 : 동일
  
  • ((2, 5, 7, 11, 26, 38, 61, 71) (42, 53))
  • 2, 5, 7, 11, 26, 38, 42, 53, 61, 71

---

8. 기수 정렬(Radix Sort) Bucket Sort

• Queue를 이용하여 자릿수(Digit)별로 정렬하는 방식
• 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배 하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
• 평균과 최악 모두 시간 복잡도는 O(dn)임

---

섹션4. 검색 - 이분 검색 / 해싱

 

1. 이분 검색

 

• 이분검색 (이진 검색,  Binary Search)은 전체 파일을 두 개의 서브파일로 분리해가면서 Key레코드를 검색하는 방식임
• 반드시 순서화된 파일이어야 검색할 수 있음
• 찾고자 하는 Key값을 파일의 중간 레코드 Key값과 비교하면서 검색함
• 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간이 적게 소요
• 중간 레코드 번호 M = (F + L) / 2 (단, F: 첫 번째 레코드 번호, L : 마지막 레코드 번호)

1 ~ 100까지의 숫자 중 15를 찾는 데 걸리는 횟수는?

 

• M = (1 + 100) / 2 = 50.5 -> 50(정수만 취함),50이 찾으려는 값과 같은지, 아니면 작은지, 아니면 큰지를 확인 -> 1회 비교
• M = (1 + 49) / 2 = 25, 연산결과를 비교 -> 2회 비교
• M = (1 + 24) / 2 = 12.5, 연산결과를 비교 -> 3회 비교
• M = (13 + 24) / 2 = 18,  연산결과를 비교 -> 4회 비교
• M = (13 + 17) / 2 = 15, 연산 결과를 비교 -> 5회 비교

---

2. 해싱(Hasing)

 

• 해시 테이블(Hash Table)이라는 기억공간을 할당하고, 해시 함수(Hash Function)를 이용하여 레코드 키에 대한 해시 테이블 내의 홈 주소(Hash Funcion)를 이용하여 레코드 키에 대한 해시 테이블 내의 홈 주소(Home Address)를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식

해시 테이블(Hash Table)

 

• 레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간, 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수도 있음

버킷(Bucket)	하나의 주소를 갖는 파일의 한 구역을 의미 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미
슬롯(slot)	한 개의 레코드를 저장할 수 있는 공간, n개의 슬롯이 모여 하나의 버킷을 형성함
Collision(충돌 현상)	서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
Synonym	충돌로 인해 같은 Home Address를 갖는 레코드들의 집합
Overflow	계산된 Home Address의 Bucket 내에 저장할 기억공간이 없는 상태로 Bucket을 구성하는 Slot이 여러개일 때 Collision은 발생해도 Overflow는 발생하지 않을 수 있음

 

*Collision(충돌 현상) 해결법

• 체이닝(Chaining) : Collision이 발생하면 버킷에 할당된 연결 리스트(Linked List)에 데이터를 저장하는 방법
• 개방 주소법(Open Addressing) : Collision이 발생하면 순차적으로 그 다음 빈 버킷을 찾아 데이터를 저장하는 방법
• 재해싱(Rehasing) : Collision이 발생하면 새로운 해싱 함수로 새로운 홈 주소를 구하는 방법

 

해싱 함수(Hashing Function)

제산법(Division)	레코드 키(K)를 해시표(Hash Table)의 크기보다 큰 수 중에서 가장 작은 소수(Prime, Q)로 나눈 나머지를 홈 주소로 삼는 방식, h(K) - K mod Q
제곱법(Mid-Square)	레코드 키 값(K)을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식
폴딩법(Folding)	레코드 키 값(K)을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적논리합)한 값을 홈 주소로 삼는 방식
기수 변환법(Radix)	키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고 이를 다시 주소 범위에 맞게 조정하는 방법
대수적 코딩법 (Algebraic Coding)	키 값을 이루고 있는 가 자리의 비트 수를 한 다항식의 계수로 간주하고 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식
숫자 분석법 (Digit Analysis, 계수 분석법)	키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식
무작위법(Random)	난수(Random Number)를 발생시켜 나온 값을 홈 주소로 삼는 방식