[알고리즘 3주차] WIL - 힙, 정렬(버블, 선택, 삽입, 퀵, 머지, 힙)

Heap

완전이진트리로서 부모노드가 자식노드보다 크거나 작은 순서로 정렬되어있는 자료구조를 말합니다. 부모노드가 자식노드보다 작으면 최소힙이라고 부르고, 크면 최대힙이라고 부릅니다. 

여기서 완전이진트리란 트리의 왼쪽부터 봤을 때 노드가 비어있지 않은 구조를 말합니다. 

 

힙은 배열로 표현이 가능한데 루트노드를 1인 인덱스로 가정합니다. 루트노드를 중심으로 왼쪽 자식노드는 2 * 부모인덱스, 오른쪽 자식노드는 (2 * 부모인덱스) + 1 가 됩니다.

 

힙의 삽입 및 삭제에 대해서 알아보겠습니다.

최소힙을 기준으로 알아보겠습니다. 맨 위 루트 노드는 모든 노드중 가장 작은 노드가 될 것입니다. 

 

• 삽입

이 트리에 어떠한 값을 append합니다. 그리고 부모노드와 비교해 가면서 자신의 자리를 찾아갑니다.

 

• 삭제

삭제는 무조건 루트 삭제하게 됩니다. 최소힙의 경우 가장 작은 값이 먼저 나오게 될 것입니다.

이를 코드로 구현할 때 순서는 다음과 같습니다.

1. 리프노드와 루트노드를 교환합니다.

2. 루트노드(기존 리프노드)를 자식노드들과 비교하면서 제자리를 찾아갑니다.

 

힙에 관련된 문제를 풀 때 생각하면서 까다로웠던 점은 최대힙구현이었습니다. 파이썬은 최소힙을 기준으로 실행되고 이를 최대힙으로 바꾸기 위해서는 튜플형태로 만들거나 음수로 바꿔서 추출할 때 다시 '-'를 붙여서 빼오는 방법이 있습니다.

 

 

정렬

정렬에는 여러가지 알고리즘이 있습니다. 순서대로 차근차근 복습해보겠습니다.

 

1. Bubble Sort

맨 앞 두 수를 비교하여 큰 값을 뒤로 차근차근 보내는 알고리즘 입니다. 

n(n - 1) / 2 이므로 O(N^2)의 시간 복잡도를 가집니다.

 

2. Selection Sort

리스트 중 가장 작은 값을 찾아서 현재 인덱스와 값을 바꾸는 알고리즘입니다.

역시 버블정렬과 마찬가지로 n(n - 1) / 2 이므로 O(N^2)의 시간 복잡도를 가집니다.

 

3. Insertion Sort

정렬된 부분과 정렬되지 않은 두 부분으로 나눠서 정렬되지 않은 값을 정렬된 리스트에 맞는 인덱스에 넣는 알고리즘입니다.

오름차순으로 정렬할 때 최악의 경우는 내림차순으로 정렬되어있는 리스트이며 시간복잡도는 O(N^2)입니다.

 

4. Quick Sort

맨 뒤 값을 pivot으로 설정하고 맨앞부터 시작하여 pivot보다 작은 경우 그대로 두고 pivot보다 크면 자리를 교환합니다.

끝나면 pivot보다 작은값과 큰값으로 나눠지게 되는데 pivot을 그 사이에 위치합니다. 이 과정을 반복함으로써 정렬할 수 있습니다.

pivot이 중간값과 근사하지 않을 경우 최악의 경우인 O(N^2)의 시간복잡도를 가집니다.

 

5. Merge Sort

배열을 반으로 쪼개지지 않을 때까지 쪼갠 후 이를 다시 붙일 때 정렬하여 완성하는 알고리즘입니다. 쪼갤 때는 1/2로 나뉘기 때문에 높이는 logN이며 각 단계에서 N만큼 비교하기 때문에 총시간복잡도는 O(NlogN) 이 됩니다.

 

6. Heap Sort

파이썬에서 보통 heapq라는 라이브러리를 이용하며 최소힙이 디폴트로 실행됩니다. 힙에 넣음과 동시에 자동으로 정렬되며 데이터를 뽑을 때는 무조건 루트노드, 즉 최소값부터 나오게 됩니다.

삽입과 추출은 제일 위에서 힙에서 설명드렸던 방식대로 움직이게 됩니다.

시간복잡도는 O(NlogN) 을 가집니다.