개념

  • 숫자의 자릿수별로 차례대로 정렬해 나가는 방법
    • 비교 기반이 아닌 정렬
  • 한 자리씩 (1의 자리, 10의 자리, 100의 자리...) 순서대로 정렬
  • 각 자릿수 정렬은 주로 Counting Sort를 사용해서 안정적으로(stable) 처리

사용방식

  • 가장 작은 자리수부터 정렬 (LSD: Least Significant Digit)
  • Counting Sort로 해당 자리만 기준으로 정렬
  • 다음 자리수로 이동해서 반복

사용처

  • 수가 작은 정수일 때 (자릿수 작음)
  • 문자열 길이가 고정돼 있을 때
  • ID 번호, 학번처럼 포맷이 일정한 데이터
  • ※ 일반 정렬이 더 나을 수 있으니 남용 x {문자 길이 우선 정렬 등 <- 문자열 길이가 일관x}*

주의 사항

  • Counting Sort 메모리 소모 주의

시간 복잡도

단계 시간
각 자리별 정렬 O(N + K)
자리 수 (d자리)만큼 반복 d번

'공부 > 알고리즘공부' 카테고리의 다른 글

Counting Sort  (0) 2025.04.29
2진수의 사칙연산  (0) 2025.03.01
정렬알고리즘 #단순정렬  (0) 2022.07.11
In-place & Stable ?  (0) 2022.05.01
Two Point 알고리즘  (0) 2022.04.29

+ Recent posts

let textNodes = document.querySelectorAll("div.tt_article_useless_p_margin.contents_style > *:not(figure):not(pre)"); textNodes.forEach(function(a) { a.innerHTML = a.innerHTML.replace(/`(.*?)`/g, '$1'); });