[정렬] 합병 정렬, 힙 정렬, 퀵 정렬, 트리 정렬

목차

1. 합병 정렬

2. 힙 정렬

3. 퀵 정렬

4. 트리 정렬

 

---

 

1. 합병 정렬 (Merge Sort)

  - 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식

  - 추가저장을 위한 메모리 필요 (인플레이스 정렬과 반대)

  - 알고리즘 복잡도 : O(nlogn)

 

 

2. 힙 정렬 (Heap Sort)

  - 힙 자료구조 형태의 정렬 방식

  - 기존 배열을 최대 힙으로 구조 변경 후 정렬 진행

  - 알고리즘 복잡도 : O(nlogn) 

 

 

3. 퀵 정렬 (Quick Sort)

  - 임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식

  - 한번 정렬 후 기준 값 왼쪽에는 기준값보다 작은 수만, 오른쪽에는 기준 값보다 큰 수만 존재

  - 알고리즘 복잡도 : O(n^2)

 

 

4. 트리 정렬 (Tree Sort)

  - 이진 탐색 트리(BST)를 만들어 정렬하는 방식

  - 알고리즘 복잡도 : O(nlogn)