[자료구조] 05 정렬, 탐색

▶ 정렬 (Sort)

: 버블 정렬 (Bubble Sort)

: 선택 정렬 (Selection Sort)

: 삽입 정렬 (Insertion Sort)

 

: 힙 정렬 (Heap Sort)

: 병합 정렬 (Merge Sort) (분할(Divide) → 정복(Conquer) → 결합(Combine) 기반 구현)

: 퀵 정렬 (Quick Sort) (분할(Divide) → 정복(Conquer) → 결합(Combine) 기반 구현)

 

: 기수 정렬 (Radix Sort)

 

---

 

▶ 순차 탐색 (Linear Search)

: 정렬 되지 않은 대상을 기반으로 하는 탐색

 

 

▶ 이진 탐색 (Binary Search)

: 정렬된 대상을 기반으로 하는 탐색

 

 

▶ 보간 탐색 (Interpolation Search)

: 데이터의 값과 그 데이터가 저장된 위치의 인덱스 값이 비례하다고 가정

: 이진 탐색의 비효율성을 개선한 탐색

: ex) 국어사전의 'ㄱ' 찾기

 

 

▶

LOW x x x S x x x x HIGH

LOW~S 길이 : Q = arr[S] - arr[LOW]

LOW~HIGH 길이 : A = arr[HIGH] - arr[LOW]

 

A : Q = (HIGH - LOW) : (S - LOW)

 

S = Q ÷ A × (HIGH - LOW) + LOW

 

X = arr[S] 로 치환

 

S = (X - arr[LOW]) ÷ (arr[HIGH] - arr[LOW]) × (HIGH - LOW) + LOW

 

단점으로 오차율 최소화를 위해 나눗셈을 해야한다.

 

---

 

▶ 이진 탐색 트리 (Binary Search Tree)

: 정렬 대상을 반으로 줄여가며 탐색

 

 

▶ AVL 트리 (Adelson-Velsky and Landis 트리)

: 이진 탐색 트리는 저장 순서에 따라 탐색의 성능에 큰 차이를 보인다.

: 이와 같은 단점 해결 → 균형 잡힌 이진 트리

 

 

▶ AVL 트리 특징

: 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

: |균형 인수| ≤ 2 → 트리 재조정

 

 

▶ 트리 재조정 (그림 필요)

LL 상태 → LL회전
RR 상태 → RR회전
LR 상태 → LR회전	부분 RR회전 + LL회전
RL 상태 → RL회전	부분 LL회전 + RR회전

균형 인수 ≥ 2	왼쪽 서브 트리 높이 > 0	→ LL 회전
	왼쪽 서브 트리 높이 ≤ 0	→ LR 회전
균형 인수 ≤ -2	오른쪽 서브 트리 높이 < 0	→ RR 회전
	오른쪽 서브 트리 높이 ≥ 0	→ RL 회전