20240130_병합 정렬, 힙 정렬

오늘의 TIL은 어제에 이어서 정렬 알고리즘에 대한 내용이다.

 

어제 알아봤던 버블 정렬, 선택 정렬, 삽입 정렬은 N^2(삽입 정렬은 최적의 경우 N)의 시간 복잡도를 가지는

 

데이터의 양이 많아지면 사용하기 어려워지는 정렬 알고리즘이었다.

 

오늘은 nlogn을 가지는 보다 효율적인 정렬 알고리즘인 병합 정렬과 힙 정렬을 알아보려고 한다.

 

 

1. 병합 정렬(merge Sort)

병합 정렬은 분할 정복(Divide and Conquer) 방식을 이용한 정렬 방법으로,

 

하나의 리스트를 두 개의 리스트로 분할한 다음,

 

각각의 분할된 리스트를 정렬한 후 합쳐서 정렬된 하나의 리스트로 만드는 방법이다.

 

병합 정렬이 가지는 또 하나의 특징은, 두 개의 리스트를 분할하여 정렬하는 과정을

 

원래 있는 리스트가 아닌 새로운 리스트에서 작업한다는 점이다

 

(정렬한 데이터를 저장하는 추가적인 임시 공간을 사용한다는 점이다)

 

병합 정렬이 작동하는 과정을 살펴보면

 

1) 분할(Divide) - 주어진 리스트를 최소한의 단위로 분할한다.

 

2) 정복(Conquer) - 분할된 리스트를 정렬한다.

 

3) 결합(Combine) - 정렬된 두 개의 리스트를 하나의 리스트로 결합한다.

 

그림으로 나타내면 아래와 같다.

 

주어진 리스트를 최소 단위(1개의 숫자)로 분할을 반복한 후에,

 

가장 가까운 인덱스의 단위와 합치며 정렬을 한다(정복과 결합을 동시에 수행).

 

이 방법을 모든 단위를 합쳐질 때까지 반복하며 데이터를 정렬한다.

 

이 과정은 시간 복잡도 면에서 nlogn을 가지게 되므로, N^2을 가지는 버블, 선택, 삽입 정렬보다 효율적이다.

 

단, 이 과정을 새로운 공간에서 작업하므로 추가 공간이 필요하고,

 

데이터가 많은 경우에는 이 과정이 시간과 공간을 많이 사용하게되는 단점이 존재한다.

 

 

2. 힙 정렬(Heap Sort)

힙 정렬은 자료 구조인 힙(Heap)을 사용하여 만들어진 정렬 알고리즘으로

 

최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법이다.

 

내림차순 정렬을 위해서는 최대 힙을 구성, 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

 

이 정렬의 알고리즘을 살펴보면

 

Queue를 이용하는 정렬 방식으로, Queue를 이용하여 최대 힙 트리를 만든 후에,

 

원소를 꺼내서 배열의 뒤에서(최대 힙 트리이므로, Queue의 머리는 최대 값이 된다)부터 값을 저장한다.

 

저장하는 과정에서 최대 값을 빼낸 후에, 만약 최대 힙 속성이 유지되지 않는다면 재정렬한다.

 

이 과정을 힙의 크기가 1보다 클 때까지 반복한다.

 

 

힙 정렬은 힙 생성 알고리즘(Heapify Algorithm)을 사용한다.

 

(힙 생성 알고리즘은 자신과 연결된 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다)

 

이를 사용하여 자기 자신과 연결된 가장 아래의 노드까지 탐색하며 가장 큰 수를 자신과 바꾸게 된다.

 

이 과정을 통해서 전체 트리를 힙 구조를 가지는 트리로 만들 수 있다.

 

 

1. 최대 힙 만들기

 

위의 이미지처럼 배열이 주어지면 이진 트리의 방식으로 트리를 만드는데,

 

4개 이상의 데이터가 들어가면 새로운 트리를 만들며 힙 생성 알고리즘을 수행하게 된다.

 

따라서 배열을 차례대로 트리를 만드는 동시에 최대 값이 가장 상위로 가는 최대 힙을 만들 수 있게 된다.

 

2. 최상단의 노트를 빼낸 후에 새로운 최대 값을 최상단으로 위치시키기

 

 

위의 이미지와 같이 최상단에 있는 노드를 배열의 맨 뒤로 보낸 후에, 가장 마지막 값을 최상단의 노드에 위치시킨다. 

 

이후에 힙 생성 알고리즘을 적용시켜 남아있는 수 중에서 최대값을 최상단으로 옮긴다.

 

이 과정을 반복해서 배열을 완성시킨다.

 

 

힙 정렬은 병합 정렬과 마찬가지로 nlogn의 시간 복잡도를 가지는 효율적인 정렬 방식이라는 장점이 있다.

 

또, 병합 정렬과는 달리 별도의 공간(메모리)을 사용하지 않는 제자리 정렬(in-place sorting) 방식이라는 장점이 있다.

 

특히, 가장 큰 몇개의 값, 가장 작은 몇개의 값을 찾는 경우에 매우 효율적으로 사용할 수 있다는 장점이 있다.