내부 정렬

삽입 정렬(insertion Sort)

삽입 정렬은 가장 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시킨다음에 정렬하는ㄱ ㅓㅅ입니다.

평균과 최악 모두 수행 시간 복잡도는O(n2)입니다.

---

쉘 정렬(Shell Sort)

쉘 정렬은 삽입정렬을 확장한 개념입니다.

평균 수행 복잡도는 O(n1.5)이고, 최악의 수행 시간 복잡도는 삽입 정렬과 같습니다.

쉘 정렬의키워드는 매개변수입니다.

---

선택 정렬(Seletcion Sort)

선택 정렬은 n개의 레코드 중에서 최소값을 찾아 첫번째 레코드 위치에 놓고 나머지 (n-1)개 중에서 다시 최소값을 찾아 두번째 레코드 위치에 놓는 방식을 반복하는 것입니다.

평균과 최악 모두 수행 시간 복잡도는 O(n2)입니다.

---

버블 정렬(Bubble Sort)

• 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환합니다.
• 계속 정렬 여부를 플래그 비트로 결정합니다.
• 평균과 최악 모두 수행 시간 복잡도는 선택정렬과 같습니다.

---

퀵 정렬(Quick Sort)

레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬합니다.

작은 값은 왼쪽 큰 값을 오른쪽에 오도록 합니다.

정렬 방식 중에 제일 빠릅니다.

하지만 스택이라는게 필요하며 분할과 정복을 통해 자료를 정렬합니다.

평균 수행 시간 복잡도는 O(nlog2n)이고 최악의 수행 시간 복잡도는 O(n2)입니다,.

---

힙 정렬

전이진 트리(Complete Binary Tree)를 이용한 정렬 방식입니다.

구성된 전이진 트리를 Heap Tree로 변환시켜 정렬하며

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

자격증 필기 시험에 많이 나오는 정렬입니다.

---

2-Way 합병 정렬(Merge Sort)

이미 정렬되어 있는 두개의 파일을 한개의 파일로 병합하는 정렬 방식이라고 보면 될것 같습니다.

평균과 최악 모두 시간 복잡도는 O(nlog2n)입니다.

---

기수 정렬(Radix Sort) = Bucket Sort

기수 정렬은 Queue를 이용하여 정렬하며

평균과 최악 모두 시간 복잡도는 O(dn)입니다.

기수 정렬의 키워드는 "버킷"입니다.