[알고리즘] 기수 정렬(Radix Sort)이란?

정렬 알고리즘	정의
버블 (bubble)	데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식
선택 (selection)	대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식
삽입 (insertion)	대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식
퀵 (quick)	pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식
병합 (merge)	이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식
기수 (radix)	데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식

 

 

📌 기수 정렬이란?

• 값을 비교하지 않고 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식
• 시간 복잡도 : O(kn) ➡️ k는 데이터의 자릿수
  • ex) 234, 123을 비교하면 4와 3, 3과 2, 2와 1만 비교

 

📌 기수 정렬 과정

기수 정렬은 10개의 Queue를 이용한다. 각 큐는 값의 자릿수를 대표한다.

<Example>

16 80 18 77 03 24 88 23

1. 1의 자릿수를 기준으로 큐에 데이터를 저장
2. 1의 자리를 기준으로 데이터를 정렬 
3. 위에서 정렬한 상태로 10의 자릿수를 기준으로 데이터를 다시 큐에 저장

03 16 18 23 24 77 80 88

 

 

📌 기수 정렬의 특징

1. 빠른 속도
   • 기수 정렬은 데이터를 정렬할 때 각 자릿수를 기준으로 정렬 작업을 수행
   • 값들을 비교(compare)하지 않고, 자릿수의 숫자 값을 이용해 Queue에 넣는 방식으로 정렬하므로 이전에 배운 정렬들에 비해 빠른 성능을 가짐
   • 시간 복잡도는 O(k⋅n)로, k는 자릿수의 최대 길이, n은 데이터 개수를 의미
     ➡️ k가 작다면 매우 효율적!!
2. 안정 정렬
   • 기수 정렬은 안정 정렬
   • 동일한 자릿수 값을 가진 요소들의 순서가 기존의 입력 순서와 동일하게 유지됨
     ex) 값이 123과 124인 데이터가 이미 정렬되어 있다면, 기수 정렬을 수행하더라도 두 값의 순서는 변하지 않음
3. 추가 메모리 사용
   • 기수 정렬은 제자리 정렬이 아님
   • 정렬 과정에서 데이터를 자릿수에 따라 Queue로 분류하고, 이를 다시 병합하기 위해 추가 메모리 공간 필요
4. 제한 사항
   • 기수 정렬은 정렬하려는 데이터의 자릿수와 값의 범위가 제한적일 때 가장 효율적
   • 자릿수가 크거나 값의 범위가 매우 넓으면 k가 커져 효율이 떨어질 수 있음
   • 데이터 유형이 정수나 고정된 길이의 문자열처럼 자릿수로 분류 가능한 형태여야만 사용 가능

 

 

 

 

✅ 다음 게시글에서 예제 문제로 더 자세히 이해해보도록 하겠습니다!