🚀 What I Will Learn

  • 기수 정렬((Radix Sort)의 원리를 이해한다

기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘. 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.


기수 정렬 알고리즘

1️⃣ 기수 정렬이란?

  1. 자릿수를 기준으로 차례대로 데이터를 정렬하는 정렬 알고리즘
  2. 각 데이터를 자릿수를 기준으로 분류하므로, 가장 큰 자릿수를 D라고 했을 때 0(DN)의 시간 복잡도를 가진다
  3. 자릿수의 개수만큼 반복


✔️ 기수 정렬 알고리즘 예시

  • 각 자릿수를 확인해서 배열에 값을 증가시킨다.
  1. 자릿수: 1의 자리

  1. 계수 정렬과 비슷하지만, 차이점은 누적값을 가진다. 누적값을 구하는 이유는 결과배열을 만들기 위해서이다.
  • 총 7개의 원소에 대해서 누적해서 갯수를 구한다

  1. 결과배열은 원소의 뒤에서 부터 확인한다.
  • 가장 뒤에 있는 34부터 시작.
  • 34의 1의 자리가 4이므로,
  • 기존에 4가 있는 누적값을 찾아
  • 결과배열의 4번째에 해당하는 자리에 34를 추가한다

  1. 34를 처리했으니 -1을 처리해서 3이 되었다

  1. 그 다음 원소도 동일한 방법으로 처리한다

  1. 1의 자리까지 정렬 완료!

  1. 자릿수: 10의 자리
  • 동일한 방법으로 누적값을 구하고,
  • 결과배열을 구한다

  • 10의 자리까지 정렬 완료!

  1. 자릿수: 100의 자리
  • 동일한 방법으로 정렬한다

  • 100의 자리까지 정렬 완료!

  1. 정렬 완료



✨ tl;dr

  • 기수 정렬은 시간 복잡도가 𝑂(ㅇ𝑁)인 정렬 알고리즘이다
  • 개수 정렬보다 약간 더 느리지만 숫자가 매우 큰 상황에서도 사용할 수 있다