정렬 알고리즘(병합 정렬, 힙 정렬)

 

 

💡병합 정렬(Merge sort)

- 병합 정렬은 분할 정복방법을 사용하여 리스트를 정렬하는 알고리즘입니다.

 

i) 병합 정렬 과정

병합 정렬 과정

- 리스트를 반으로 나눕니다.

- 각각을 재귀적으로 정렬합니다.

- 두 리스트를 다시 하나의 리스트로 합칩니다. 이때 두 리스트는 이미 정렬되어 있는 형태입니다.

 

 

ii) 병합 정렬 특징

• 병합 정렬은 안정적인 정렬 알고리즘입니다. 안정적인 정렬 알고리즘이란, 같은 값의 원소가 여러 개 존재할 경우, 입력 배열에서의 순서가 유지되는 정렬 알고리즘을 말합니다.
• 병합 정렬은 분할 정복 알고리즘을 사용합니다. 이는 문제를 작은 문제로 분할하여 해결하는 방법으로, 재귀적인 호출을 이용하여 문제를 해결합니다.
• 병합 정렬의 시간 복잡도는 평균적으로 O(nlogn)입니다. 이는 입력 크기가 커질수록 빠르게 정렬할 수 있음을 의미합니다.
• 병합 정렬은 리스트를 반으로 나누는 과정에서 추가적인 메모리 공간이 필요합니다. 이는 분할된 두 개의 리스트를 저장하기 위함입니다. 따라서, 대규모의 데이터를 정렬할 때는 메모리 사용에 주의해야 합니다.
• 병합 정렬의 최악의 경우에도 시간 복잡도가 O(nlogn)입니다. 이는 입력 배열을 반으로 나누는 과정에서 나머지가 생기더라도, 재귀 호출 횟수가 logn 이하로 유지되기 때문입니다.

 

 

iii) 병합 정렬 파이썬 코드

 

 

- 이 코드에서는 먼저 배열의 길이가 1이하일 경우 바로 해당 배열을 반환하도록 기저 조건을 설정합니다. 그 후, 배열을 반으로 나누고 각각에 대해 재귀적으로 merge_sort 함수를 호출합니다. 이를 통해 배열이 더 이상 나누어지지 않을 때까지 분할합니다.

 

- 분할된 두 배열을 합치는 작업에서는, 하나의 새로운 배열을 만들고, 두 배열의 첫 번째 원소부터 차례대로 비교하면서 작은 값부터 새로운 배열에 넣어줍니다. 이후 남은 원소들을 차례대로 새로운 배열에 추가해주면서 합병을 완료합니다.

 

 

 

💡힙 정렬(Heap sort)

- 힙 정렬은 힙 자료구조를 이용한 정렬 알고리즘입니다.

- 힙은 완전 이진 트리의 일종으로, 최대 힙과 최소 힙 두 가지 종류가 있습니다.

- 최대 힙에서는 부모 노드의 값이 자식 노드의 값보다 크거나 같고, 최소 힙에서는 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.

 

 

 

i)힙 정렬 과정 

힙 정렬 과정

- 주어진 배열을 최대 힙으로 변환합니다.

- 루트 노드와 마지막 노드를 교환합니다.

- 힙 크기를 1 감소시킨 후, 루트 노드를 다시 최대 힙의 성질을 만족하도록 재배치합니다.

- 힙의 크기가 1보다 크면, 2번부터 4번까지의 과정을 반복합니다.

 

 

 

 

ii) 힙 정렬 특징

• 힙 정렬은 안정 정렬이 아닙니다. 같은 값의 원소가 배열 내에서 서로 다른 위치에 있을 때, 정렬 후에도 같은 순서를 보장하지 않을 수 있습니다.
• 힙 정렬은 제자리 정렬(In-Place Sort)이 아닙니다. 원래 배열 외에 추가적인 메모리를 사용하여 최대 힙을 생성하고 정렬을 수행합니다.
• 힙 정렬의 시간복잡도는 O(nlogn)입니다. 이는 일반적으로 퀵 정렬과 병합 정렬과 비슷한 수준으로 간주됩니다.
• 힙 정렬은 최악의 경우에도 O(nlogn)의 성능을 보장합니다. 즉, 이미 정렬된 배열이나 거꾸로 정렬된 배열 같이 이미 정렬되어 있는 배열에 대해서도 항상 일정한 성능을 보장합니다.
• 힙 정렬은 데이터의 분포와는 무관하게 일정한 성능을 보장합니다. 따라서 다른 정렬 알고리즘이 데이터의 분포에 따라 성능이 크게 달라지는 경우에 비해, 힙 정렬은 안정적인 성능을 보장합니다.

 

 

iii) 힙 정렬 파이썬 코드

 

- heapify 함수는 주어진 배열 arr에서 특정 인덱스 i를 루트로 하는 서브트리를 최대 힙 구조로 만들어주는 함수입니다. heapify 함수는

아래와 같은 순서로 동작합니다.

• 현재 인덱스 i를 최댓값으로 설정합니다.
• 왼쪽 자식 노드(left)와 비교하여 더 큰 값이 있다면 largest 변수를 left로 업데이트합니다.
• 오른쪽 자식 노드(right)와 비교하여 더 큰 값이 있다면 largest 변수를 right로 업데이트합니다.
• 만약 largest 값이 i와 다르다면, i와 largest 인덱스에 해당하는 값을 서로 바꾸어줍니다. 이후 heapify 함수를 재귀적으로 호출하여 largest를 루트로 하는 서브트리도 최대 힙 구조로 만들어줍니다.

 

 

- heap_sort 함수는 주어진 배열 arr을 힙 정렬을 이용하여 정렬한 결과를 반환하는 함수입니다.  함수는 아래와 같은 순서로 동작합니다.

• n을 배열의 길이로 설정합니다.
• n//2 - 1부터 0까지 역순으로 반복문을 수행하며, 해당 인덱스를 루트로 하는 서브트리를 최대 힙 구조로 만들어줍니다. 이 과정을 통해 전체 배열을 최대 힙 구조로 만듭니다.
• n-1부터 1까지 역순으로 반복문을 수행하며, arr[0]과 arr[i]를 서로 바꾸어줍니다. 이후 heapify 함수를 호출하여 arr[0]을 새로운 루트로 하는 서브트리를 최대 힙 구조로 만들어줍니다.
• 배열의 모든 원소가 정렬될 때까지 2-3 과정을 반복합니다.

- heap_sort 함수를 호출하여 정렬된 결과를 반환하면, 오름차순으로 정렬된 배열이 출력됩니다.