11장 정렬 분배 방식<기수 정렬>

정렬

순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것이다. 정렬 방법은 수행되는 위치에 따라서 컴퓨터 메모리 내부에서 수행하는 내부 정렬과 메모리의 외부인 보조 기억 장치에서 수행하는 외부 정렬로 분류할 수 있고, 수행 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있다.

 

내부 정렬

1. 교환 방식 - 키를 비교하고 교환하여 정렬하는 방식(선택, 버블, 퀵)

2. 삽입 방식 - 키를 비교하고 삽입하여 정렬하는 방식(삽입, 셸)

3. 병합 방식- 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합)

4. 분배 방식 - 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수)

5. 선택 방식 - 이진 트리를 사용하여 정렬하는 방식(힙, 트리)

 

정렬되지 않은 { 69, 10, 30, 2, 16, 8, 31 }을 예시로 들겠다.

기수 정렬

기수 정렬은 분배방식의 정렬 방법으로 정렬할 원소의 키값에 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복한다. 기수 정렬은 원소의 키를 표현하는 값의 기수만큼의 버킷이 필요하고, 키값의 자리수만큼 기수 정렬을 반복한다.

 

1. 큐를 사용하여 0부터 9까지 10개의 버킷을 만든다.

2. 키값의 일의 자리에 대해서 기수 정렬을 수행한다. 정렬할 원소의 키값의 일의 자리에 따라서 순서대로 버킷에 분배한다.

3. 버킷에 분배된 원소들을 순서대로 꺼내서 다시 저장한다.

4. 키값의 십의 자리에 대해서 기수 정렬을 수행한다. 정렬할 원소의 십의 자리 값에 따라서 순서대로 버킷에 분배한다.

5. 버킷에 분배된 원소들을 순서대로 꺼내서 다시 저장한다.