데이터구조 17 ( Radix sort )

Radix sort

 

• 여러 Key에 대해 sort한다.
• 각 Key에 따라 우선 순위가 다르다.

 

ex) 학생 명단을 sort할 때,

학부 > 성명 > 학번으로 sort한다고 생각해보자.

 

가장 먼저 학부 순으로 sort --> 같은 학부에서는 이름 순으로 sort --> 이름까지 같다면 학번순으로 sort

 

Most significant key --> 학부

Least significant ket -->  학번

 

 

 예 ) 학부 > 학번 2개로 sort한다고 생각해보자

 

방법 1) Most significant key 에 대하여 먼저 sort

-- > 전체 명단을 학부별로 분리

-- > 각 학부별 명단을 학번 순으로 sort

-->  각 파일(array)을 순서대로 한 개로 결합. 

 

---

 

방법 2) Least significant key 에 대하여 먼저 sort

- 전체 명단을 학번순으로 sort

- 각 원소를 순서대로 학부 별 Queue에 넣는다.

- 학부 순서대로 queue 내용을 한 개로 결합한다.

 

 

---

Radix Sort

 

일정 자릿수의 int값을 key로 할 때, 각 자릿수를 서로 다른 key로 할 수 있다.

ex) 3286 --> k1 =3, k2=2, k3 =8, k4=6

 

이걸 할 때도 most significant랑 least로 나눔.

 

MSD (Most Significant Digit) sort : MSD 우선 순서로 sort

 

LSD (Least Significant Digit) sort : LSD 우선 순서로 sort

 

 

예제 )

 

1. 가장 높은 자리수가 100이고, 100의 자릿수가 나올 수 있는 경우는 10개이므로,

    백단위 digit 기준 10개의 배열[0~9]을 만든다.

 

2. 각 배열 원소에 대해 십 단위 digit 기준으로 10개의 배열로 또 구분한다.

 

3. 마지막으로 가장 작아진 각 배열을 순서대로 결합하여 하나로 결합하면 종료

 

 

---

예제 2) LSD

 

LSD sort algorithm 

 

1. 각 원소의 1의 자릿수에 맞춰 Queue를 만들어서 넣고, 재구성
--> 1의 자릿수가 sorted됨

 

2. 각 원소의 10의 자릿수에 맞춰 Queue를 만들어서 넣고, 재구성

--> 1과 10의 자릿수가 sorted됨

 

3. 각 원소의 100의 자릿수에 맞춰 Queue를 만들어서 넣고, 재구성

--> 모든 자릿수가 sorted됨

sorting 이 안 되는 것 같아도, 매 단계마다 sorting 된 자릿수까지는 sort되어있음

 

 

[ 첫 번째 결과 ] 를 보면, 모든 숫자가 1의 자릿수로만 sorted 됨

 

[ 두 번째 결과 ] 를 보면, 모든 숫자가 1과 10의 자릿수로만 sorted 됨

매커니즘으로 생각해보면 200자릿수에서 가장 작은 수(212)는 가장 앞에 와있고 그런 순서대로 감

[ 세 번째 결과 ] 를 보면, 모든 숫자가 sorted 됨

출처: 한동대학교 김호준 교수님 - 데이터구조 PPT