Sorting Algorithm

정렬 알고리즘 - n개의 원소를 순서대로 배열하는 것

• 대부분 O(n²) ~ O(nlogn) 사이
• input이 특수한 성질을 만족하는 경우 O(n)도 가능

---

Basic Sorting Algorithm - 기본 정렬 알고리즘

1. 선택 정렬 (Selection Sort) : 가장 큰 원소 선택해 맨 뒤로 옮기기
2. 버블 정렬 (Bubble Sort) : 이웃한 수 비교해 큰 수를 맨 뒤로 옮기기
3. 삽입 정렬 (Insert Sort) : 앞에서부터 이미 정렬된 배열 부분과 비교해 자신의 위치에 삽입하는 과정 반복

Advanced Sorting Algorithm - 고급 정렬 알고리즘

1. 병합 정렬 (Merge Sort) : 입력을 반으로 나누며 전반부 후반부 독립적으로 정렬
2. 퀵 정렬 (Quick Sort) : 기준 원소 잡고 양쪽으로 재배치하며 정렬
3. 힙 정렬 (Heap Sort) : 힙 자료구조를 사용하는 정렬

---

---

요약

1. 선택, 버블, 삽입 정렬은 평균적인 경우와 최악의 경우 모두 Θ(n²)이 소요

2. 병합, 힙 정렬은 평균적인 경우와 최악의 경우 모두 Θ(nlogn)

3. 퀵 정렬은 평균적인 경우 Θ(nlogn)이 소요, 최악의 경우 Θ(n²)이 소요. 그러나 실제 현장에서 가장 많이 사용되는 정렬 알고리즘
   퀵 정렬의 품질은 분할의 균형에 영향을 많이 받음. 지나치게 균형이 깨진 경우 (한 쪽으로만 몰리는 경우) 좋지 않으나 드물다.

4. 두 원소의 비교에 근거한 정렬은 최악의 경우 Ω(nlogn) 보다 더 효율적일 수 없음. 두 원소 비교에 근거하지 않으면 선형 시간에 정렬 가능. 기수, 계수 정렬은 Θ(n)이 소요