힙 정렬(Heap Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort)

 

이번에는 정렬 중에서도 시간 복잡도가 조금 더 빠른 정렬들을 가지고 왔습니다.

 

힙 정렬, 병합 정렬, 퀵 정렬

이렇게 총 3가지 정렬을 설명 드리겠습니다.

 

힙 정렬(Heap Sort)

- 아래의 링크에 있는 힙에 대해 공부하고 오면 이해하기 매우 편하십니다.

https://naknak.tistory.com/123

힙(Heap)과 이진탐색트리(Binary Search Tree)

 

 

- 힙은 트리 형태의 구조로, 우선순위 큐를 구현하는데 주로 사용됩니다.

- 보통의 힙은 꺼낼 때 가장 작은 숫자부터 꺼내게 되는데, 힙 정렬에서는 내림차순 힙을 사용합니다.

(reverseOrder로 힙을 생성하여 가장 큰 값부터 꺼내야 합니다.)

 

ex) 정렬되지 않은 배열 int[] arr = {1,3,4,5,6,2,7}을 힙 정렬을 이용해 정렬하자.

1) 내림차순 힙을 하나 생성하고, 거기에 arr 배열에 있는 값들을 넣습니다.

2) 힙에 배열을 삽입할 때, O(n log n) 만큼 시간이 걸리게 된다.

3) 힙에서 하나를 꺼내고, 재구축 하는데 걸리는 시간도 O(n log n) 만큼 걸리게 된다. (하나의 라운드 당 O(log n)이라 n개의 라운드면 O(nlog n) 만큼 걸리게 된다.

4) 힙에서 하나씩 꺼내는데, 내림차순 힙이기 때문에 가장 큰 숫자부터 꺼내게 되므로, 배열의 맨 뒷부분부터 채워지게 된다.

 

힙에 넣는데 걸리는 시간복잡도 : O(n log n)

재구축하는데 걸리는 시간복잡도 : O(n log n)

 

결국 힙 정렬은 O(n log n) 만큼의 시간이 걸리게 된다.

 

병합 정렬(Merge Sort)

- 분할정복(divide and conquer)을 이용해 푸는 정렬 방법으로, 더 이상 나누어지지 않을때 까지 절반씩 나누고,

그 상태에서 한 그룹씩 합치면서 그룹별로 정렬하는 방식의 정렬입니다.

 

ex) int[] arr = {1,3,5,2}을 정렬하여라.

1) 나누어지지 않을때 까지 나누기. => {1}, {3}, {5}, {2}

2) 하나씩 합치면서 정렬을 합니다. => {1, 3}, {2, 5}

3) 2번을 한번 더 진행합니다. => {1, 2, 3, 5}

 

*두개 이상이 들어있는 배열에서 정렬을 할때는 각 배열의 맨 앞숫자 끼리 비교해서 작은 수 부터 새로운 배열에 넣어줍니다.

(1   =>   {3}, {2, 5}

1, 2  =>    {3}, {5}

1, 2, 3  =>   {5}

1, 2, 3 ,5)

 

시간복잡도

한 층을 병합하는데 걸리는 시간 : O(n)

층의 개수 : O(log n)

=> 전체 걸리는 시간 : O(n log n)

 

퀵 정렬(Quick Sort)

- 피봇(기준 점)을 하나 두고, 그 양 옆의 배열들을 정렬하는 방식의 정렬입니다.

- 양 옆의 배열을 정렬할 때에도, 재귀함수를 통해 새로운 피봇을 만들고 정렬 시킨다. 따라서 피봇을 잘 고를수록 걸리는 시간은 적어진다.

 

ex) int[] arr = {1,5,3,6}을 퀵 정렬을 이용해 정렬해보자.

1) 예시로 피봇을 5로 정해서 정렬하기.

피봇보다 작은 수		피봇	피봇보다 큰 수
1	3	5	6

 

2) 피봇보다 큰 수 배열을 정렬하자. (이미 숫자가 1개라 정렬할 필요가 없다.)

3) 피봇보다 작은 수 배열을 정렬하자. 피봇은 3으로 정해보겠다.

피봇보다 작은 수	피봇
1	3

 

이로서 배열 arr은 퀵 정렬을 이용해 정렬되었다.

 

시간복잡도

트리의 높이 : 전체적으로 O(log n)

각 층별 정렬 시간 : O(n)

전체 시간 : O(n log n)

* 피봇을 극단적으로 잘못 고르면 O(n^2)만큼의 시간이 걸리게 된다. 피봇은 최대한 중앙값으로 고르는 것이 좋다.