Implementation (Part 1)

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

우리는 기수 정렬(Radix Sort)을 핵심 연산부터 차근차근 구현해 볼 것입니다.

챌린지

중급

기수 정렬(Radix Sort)의 각 단계는 단일 자릿수에 대한 안정 계수 정렬(stable counting sort)입니다. 먼저 이것을 구현해 봅시다.

비음수 정수 배열 arr와 자릿값 exp(일의 자리는 1, 십의 자리는 10, 백의 자리는 100, ...)를 인자로 받아 (x / exp) % 10 자릿수를 기준으로 정렬된 새 배열을 반환하는 countingSortByDigit 함수를 작성하세요. 이 정렬은 반드시 안정(stable)적이어야 합니다. 즉, 자릿수가 같은 요소들은 원래의 순서를 유지해야 합니다.

예를 들어, countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1)은 [170, 90, 2, 802, 24, 45, 75, 66]을 반환합니다(일의 자릿수를 기준으로 정렬됨).

직접 해보기

#include <stdlib.h>

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

실력 점검

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

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

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2