[코테 합격자 되기] 13장 정렬

# 정렬의 의미

데이터를 특정 기준에 따라서 순서대로 배치하는 것을 의미한다

ex. 오름차순(점점 값이 커지는), 내림차순(점점 값이 작아지는),...

 

# 코테에서 정렬이 필요한 이유

특정 알고리즘을 사용하려면

정렬된 상태에서 사용해야 하는 경우가 있기에 필요하다

ex. 이진탐색, 병합정렬의 병합,...

 

---

 

# 삽입 정렬

삽입 정렬은 오른쪽의 비정렬된 영역의 값들을 하나씩

왼쪽의 정렬된 영역으로 이동시키면서 정렬을 하는 방법이다

 

기본적으로 오른쪽 영역의 하나의 값을

왼쪽의 영역으로 올바른 위치에 정렬하기 위해서

O(N)이 필요한데

해당 동작을 N번 반복해야하니

O(N^2)이 소요된다

값이 이미 어느 정도 정렬이 되어있는 경우라면

O(N)이 소요된다

 

---

 

# 머지 정렬

병합 정렬은 2가지 과정을 거친다

첫 번째, 리스트를 계속 반으로 나누어 각각 하나의 원소로 만든다

두 번째, 각각 서로 만나서 정렬을 하며 합친다

이처럼 나누고 합치는 과정에 O(logN)이 소요되고

각각의 원소들 하나하나 이 과정을 거치니

최종적으로 O(N * logN)이 소요된다

 

합치는 과정은 위의 그림처럼

서로 하나씩 비교를 하며 작은 것을 넣는 작업을 반복한다

 

---

 

# 힙 정렬

힙 정렬은 3가지 과정을 거친다

첫 번째, 모든 원소를 Hepify 한다

두 번째, 부모노드를 맨 끝으로 이동(삭제)하고 가장 마지막 원소를 부모노드로 한 상태에서 Hepify를 한다

세 번째, 두 번째 과정을 모든 원소가 없어질 때까지 무한 반복한다 

 

Hepify는

높은 값을 상위에 두는, Max_Hepify

낮은 값을 상위에 두는, Min_Hepify로 구분된다

Max_Hepify가 사용되는 경우로 아래 예시를 설명하겠다

Max_Hepify 경우에서는 위의 그림처럼

부모노드가 자식노드보다 항상 크게 구성되도록 스왑을 진행하는 것을 Hepify라고 한다

 

위의 그림처럼

트리의 모든 삼각형 구조에서

부모노드에 가장 큰 값을 놓도록 스왑 하는 Hepify를 진행해야 한다

이렇게 하면, 첫 번째 단계가 끝난다

 

두 번째 단계는 위의 그림처럼

부모노드를 맨 끝으로 이동해서 삭제하고

가장 마지막 원소를 부모노드로 한 상태에서 모든 원소를 Hepify를 하는 것이다

 

두 번째 단계를 계속 반복하면서

삭제된 원소들을 차곡차곡 쌓다 보면 위의 그림과 같이 정렬이 완료된다

 

이처럼 첫 번째 단계를 진행하면서 O(N)이 소요된다

두 번째 단계를 진행하는데는 O(logN)이 소요되는데

해당 두번째 단계를 N번 반복하는 세 번째 단계를 거치기에 O(N * logN)이 소요된다

그래서 첫 번째 단계 + 두 번째 및 세 번째 단계는

O(N) + O(N * logN)이고

최종적으로 상수는 무시되기에 O(N * logN)이 걸린다

 

그리고 이미 이렇게 정렬된 상태에서

삽입/삭제가 발생하면,

들어온 원소에 대해서만 Hepify를 한번 하니 O(logN)이 소요된다

 

추가적으로 Hepify 연산에서 주의할 점이 있다

노드번호 N/2부터 1까지 차례대로 진행한다는 점이다

그 이유는

위의 그림을 보다시피 총 힙 size는 9이다

9를 2로 나누면 4가 나온다

1번 원소부터 4번 원소(N/2)까지는 자식노드가 존재하고

4번 원소부터 나머지 원소(N)까지는 자식노드가 없는 리프노드이다

이처럼 리프노드는 자식이 없으니 Hepify를 할 필요가 없으니

N/2부터 1까지 진행한다는 것이다

또한, 역순으로 진행하는 이유는

상위 노드가 하위 노드의 힙 성질을 재정렬하며

전체 힙 구조를 완성할 수 있기 때문이다

 

힙정렬 관련 추천 추가 자료:

https://azrael.digipen.edu/~mmead/www/Courses/CS280/Heaps-1.html

 

---

 

# 우선순위 큐

기존 큐는 FIFO이지만

우선순위 큐는 In 순서와 상관없이 우선순위가 높은 원소 먼저 Out 된다

 

우선순위 큐에서는 

O(NlogN)이 걸리는 대부분 정렬 방법을 사용하지 않고

삽입/삭제 시 O(logN)이 보장되는 힙정렬을 사용한다

 

우선순위큐는 코테에서 최단경로 알고리즘(다익스트라, 밸만포드) 구현시

많이 사용된다

 

추가적으로, 우선순위를 비교연산자를 직접 만들어

원하는 우선순위를 활용할 수 있다

 

---

 

# 비교

특히, 힙정렬의 삽입/삭제의 경우는 O(logN)이 걸린다

 

---

 

# 코드 예시 - 우선순위 큐

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/priority_queue.cpp

 

# 코드 예시 - 우선순위 큐 with 비교 연산자 정의

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/priority_queue_with_priority.cpp

 

# 코드 예시 - 삽입정렬

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/insertionsort.cpp

 

# 코드 예시 - 머지정렬

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/mergesort.cpp

 

# 코드 예시 - 힙정렬

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/heapsort.cpp