알고리즘에서 '기수 정렬(Radix Sort)'의 핵심 특징은?

Q: 알고리즘에서 '기수 정렬(Radix Sort)'의 핵심 특징은?

비교 없이 각 자릿수별로 분류하여 정렬하므로 특정 조건에서 O(nk) 시간에 동작한다 기수 정렬은 1의 자리, 10의 자리, 100의 자리 순서로 안정 정렬(주로 카운팅 정렬)을 반복합니다. n개의 k자리 수를 O(n×k)에 정렬하며, k가 작고 n이 큰 정수 배열에서 O(n log n) 비교 정렬보다 빠를 수 있습니다. LSD(최하위)와 MSD(최상위) 두 방식이 있습니다.

보통 freeCodeCamp

보기 및 정답

A 비교 없이 각 자릿수별로 분류하여 정렬하므로 특정 조건에서 O(nk) 시간에 동작한다

B 비교 기반으로 인접 원소를 교환하여 항상 O(n log n)에 동작하는 비교 기반 정렬이다

C 원소 간 비교를 직접 수행하는 비교 기반 정렬 중에서 가장 빠른 성능을 보인다

D 원소의 교환만으로 정렬하므로 별도의 추가 메모리 공간이 전혀 필요하지 않는다

해설

기수 정렬은 1의 자리, 10의 자리, 100의 자리 순서로 안정 정렬(주로 카운팅 정렬)을 반복합니다. n개의 k자리 수를 O(n×k)에 정렬하며, k가 작고 n이 큰 정수 배열에서 O(n log n) 비교 정렬보다 빠를 수 있습니다. LSD(최하위)와 MSD(최상위) 두 방식이 있습니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

알고리즘에서 '기수 정렬(Radix Sort)'의 핵심 특징은?

해설

코딩, 제대로 배우고 싶다면?

관련 문제

시장과 사람의 답을 봤다면,다음 결과물의 구조를 고릅니다.

시장과 사람의 답을 봤다면,
다음 결과물의 구조를 고릅니다.