2037: [정렬]힙정렬(py)
[만든사람 : ]
문제 설명
힙 정렬(heap sort)는 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다.
이 정렬의 알고리즘은 다음과 같다.
이 정렬의 알고리즘은 다음과 같다.
- n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
- 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
- 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
- 2와 3을 반복한다.
힙정렬은 힙을 재구성하기 위한 과정인 heapify() 함수와 이를 통해 힙 정렬을 수행하는 heapsort() 함수로 이루어져 있다.
입력되는 자료를 오름차순으로 정렬하기 위해 다음과 같이 코드를 작성하였을 때 heapify() 코드를 작성하여 제출하시오.
입력되는 자료를 오름차순으로 정렬하기 위해 다음과 같이 코드를 작성하였을 때 heapify() 코드를 작성하여 제출하시오.
def heapSort(arr):
n = len(arr)
for i in range(n//2, -1, -1):
heapify(arr,n,i)
for i in range(n-1,0,-1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr=list(map(int, input().split()))
heapSort(arr)
print(*arr)
입력 설명
함수의 매개변수로 다음과 같은 정보가 입력된다.
arr : 정렬 데이터가 저장된 배열
n : 힙 구조를 만들 배열의 크기
i : 힙 구성을 위해 조정할 노드의 인덱스
arr : 정렬 데이터가 저장된 배열
n : 힙 구조를 만들 배열의 크기
i : 힙 구성을 위해 조정할 노드의 인덱스
출력 설명
전달받은 arr의 배열의 값을 변경하며, 별도의 반환값은 없다.
입력 예시 Copy
1 12 9 5 6 10
출력 예시 Copy
1 5 6 9 10 12