Implementation (Part 2)

Coddy의 힙 정렬 - DSA 시리즈 코스 레슨 — 9개 중 6번째.

이제 힙 구축과 최대값 반복 추출을 결합합니다.

챌린지

중급

이제 모든 것을 종합하여 전체 알고리즘을 완성해 보세요.

정수 배열을 입력받아 오름차순으로 정렬하여 반환하는 heapSort라는 이름의 함수를 작성하세요.

먼저 인덱스 n/2 - 1부터 0까지 모든 리프 노드가 아닌 노드들을 sift-down 하여 최대 힙(max-heap)을 구축하세요. 그런 다음 루트(가장 큰 값)를 힙의 마지막 요소와 반복적으로 교체하고, 힙의 크기를 하나씩 줄인 후 새로운 루트를 다시 sift-down 하세요.

힙의 크기를 점진적으로 줄일 수 있도록, 현재 힙의 size를 인자로 받는 sift-down 헬퍼 함수를 사용하세요.

직접 해보기

#include <stdlib.h>

int* heapSort(int* arr, int arr_size, int* returnSize) {
    // 여기에 코드를 작성하세요
    *returnSize = arr_size;
    return arr;
}

실력 점검

이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.

힙 정렬 - DSA 시리즈의 모든 레슨

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) 프로젝트 레슨

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2