💡 합병 정렬 (Merge Sort)
👉 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식이다.
👉 알고리즘 복잡도 : O(nlogn)
💡 합병 정렬 과정
- 배열의 가운데 인덱스를 기준으로 둘로 나눈다.
- 나눈 배열의 가운데 인덱스를 기준으로 다시 둘로 나눈다.
- 같은 방법으로 각 배열의 길이가 1이 될 때까지 분할한다.
- 각각 분할된 배열의 수를 비교하여 오름 or 내림 차순으로 붙여준다.
- 같은 방법으로 배열들을 다시 합쳐서 정렬한다.
정렬 - 1 에서 정리했던 버블, 삽입, 선택 정렬과 비교했을 때 배열들을 나누고 저장하는 메모리가 더 필요하지만, 트리 구조이기 때문에 속도는 더 빠르다.
💡 힙 정렬 (Heap Sort)
👉 힙 자료구조 형태의 정렬 방식이다.
👉 기존 배열을 최대 힙으로 구조 변경 후 정렬을 진행한다.
👉 알고리즘 복잡도 : O(nlogn)
💡 퀵 정렬 (Quick Sort)
👉 임의의 기준 값 (pivot) 을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식이다.
👉 알고리즘 복잡도 : O(n²) (일반적으로는 빠른 알고리즘 이지만, 기준 값이 최소값 또는 최대값으로 지정되는 경우)
💡 퀵 정렬 과정
- pivot 을 가장 왼쪽으로 임의로 지정했을 때, 왼쪽에서부터 pivot 보다 큰 값, 오른쪽에서는 pivot 보다 작은 값이 최초로 나오는 케이스를 찾는다.
- 두 수를 바꾸고 같은 방식을 반복한다.
- 왼쪽에서는 인덱스가 커지고 오른쪽에서는 작아지기 때문에 만나는 구간에서 종료하고 pivot 값과 자리를 바꿔준다.
- 바뀐 pivot 값을 기준으로 분할하여 같은 방식을 진행하여 정렬한다.
💡 트리 정렬 (Tree Sort)
👉 이진 탐색 트리 (Binary Search Tree) 를 만들어 정렬하는 방식이다.
👉 알고리즘 복잡도 : O(nlogn)
BE