정보처리기사 데이터베이스 요약 11

11장

 

1.     정렬

-      아이템이나 레코드에 포함된 필드의 키에 따라 정보의 요소들을 배열하는 것

-      주기억장치에서 이루어지는 내부 정렬 : 히프 정렬, 삽입 정렬, 셀 정렬, 버블 정렬, 퀵 정렬, 2-way 병합 정렬, 선택 정렬, 기수 정렬

---

2.     히프 정렬 (= 힙 정렬, Heap Sort)

-      전이진 트리를 이용한 정렬 방식

-      평균과 최악 모두 시간 복잡도는 O (nlog2n)

---

3.     삽입 정렬 (Insertion Sort)

-      하나씩 삽입하면서 정렬

---

4.     버블 정렬 ( Bubble Sort )

-      인접해 있는 자료를 비교하면서 정렬

---

5.     퀵 정렬

-      키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브 파일로 분해시키는 방식

-      위치에 관계없이 임의의 키를 분할 원소로 사용할 수 있음

-      순환 알고리즘을 사용해야 하므로 스택 공간을 필요로 함

---

6.     2-way 병합 정렬(Merge Sort)

-      2개의 자료를 하나로 합치면서 정렬

---

7.     선택 정렬 (Selection Sort)

-      최소값을 찾아 나머지 모두와 비교하면서 정렬