정렬(3) - 키를 비교하지 않고 정렬하는 알고리즘: 기수정렬

키를 비교하여 정렬하는 알고리즘

2차시간 정렬 알고리즘: 삽입정렬(Insertion Sort), 교환정렬(Exchange Sort), 선택정렬(Selection Sort)

Θ(n lg n) 정렬 알고리즘: 합병정렬(Merge Sort), 빠른정렬(Quick Sort), 힙정렬(Heap Sort)

키를 비교하지 않고 정렬하는 알고리즘: 기수정렬(Radix Sort)

---

기수정렬(radix sort)

순서를 매길 수 있다는 것 이외에 키에 대한 정보가 없는 경우, 앞서 알아본 키를 비교하는 방법 이외에 할수 있는 정렬방법은 없다.

기수 정렬은 키가 음이 아닌 10진수 정수라는 것을 알 때 사용할 수 있다. 자리수(digit)를 따라 분배하여 정렬하는 알고리즘이다.

정렬하려 하는 숫자가 3자리 숫자라 가정하면, 100의 자리에서 0..9까지 더미로 숫자를 분배할 수 있다. 이 안에서 다시 10의 자리에서 0..9까지 분배 하고 마지막으로 1의 자리에서 0..9까지 분배하면 자동적으로 정렬이 되게 된다.

따라서 이 알고리즘은 분배에 의한 정렬(sorting by distribution)이다.

숫자가 아니라 알파벳 또한 분배할 수 있다. 이 경우에는 0..9까지의 10개 더미가 아니라 a..z까지의 26개의 더미로 나눠서 분배해야 한다.

http://rightwayman2013.blogspot.kr/2010/09/algo-83-radix-sort.html

C++ 스타일 수도코드

// 아래는 연결된리스트의 구현에 필요한 노드의 선언이다.
struct nodetype
{
	keytype key;
	nodetype* link;
};

typedef nodetype* node_pointer;

// 아래는 알고리즘이다.
void radixsort ( node_pointer& marsterlist, int numdigits )
{
	index i;
	node_pointer list[0..9];

	for ( i = 1; i <= numdigits; i++ ) {
		distribute ( masterlist, list, i );
		coalesce( masterlist, list );
	}
}

void distribute ( node_pointer& masterlist, node list[], index i )
{
	index j;
	node_pointer p;

	for ( j = 0; j <= 9; j++ )
		list[j] = NULL;
	p = masterlist;
	whild ( p != NULL ) {
		j = p->key에서 i자리 값;
		p를 list[j]의 끝에 링크;
		p = p -> link;
	}
}

void coalesce ( node_pointer& masterlist, node list[] )
{
	index j;

	masterlist = NULL;
	for ( j = 0; j <= 9; j++ )
		list[j]에 있는 마디들을 masterlist의 끝에 링크;
}

Java 구현 코드

import main.Print;

public class Radix {

	public static node radixsort(node masterlist, int numdigits) {
		
		node[] list = new node[10];
		
		for (int i = 1; i <= numdigits; i++) {
			distribute(masterlist, list, i);
			
//			for(int j = 0; j < list.length; j++) {
//				node temp = list[j];
//				System.out.print(j + ":");
//				while (temp != null) {
//					System.out.print(" [" + temp.key + "]");
//					temp = temp.link;
//				}
//				System.out.println();
//			}
			
			masterlist = coalesce(masterlist, list);
//			int[] arr = masterlist.getResult();
//			Print.printArray(arr);
		}
		
		return masterlist;
	}
	
	private static void distribute(node masterlist, node[] list, int i) {
		
		int j;
		node p;
		
		for(j = 0; j <= 9; j++) {
			list[j] = null;
		}
		p = masterlist;
		while (p != null) {
			j = (int) ((p.key % Math.pow(10, i)) / Math.pow(10, (i-1)));
			node temp;
			
			if (list[j] == null) {
				temp = p;
				list[j] = temp;
			} else {
				temp = list[j];
				while(temp.link != null) {
					temp = temp.link;
				}
				temp.link = p;
				temp = temp.link;
				
			}
			
			p = p.link;
			temp.link = null;
		}
	}
	
	private static node coalesce(node masterlist, node[] list) {
		
		masterlist = null;
		node temp = null;
		for (int j = 0; j <= 9; j++) {
			if (list[j] != null) {
				if (masterlist == null) {
					masterlist = list[j];
					temp = masterlist;
				} else {
					temp.link = list[j];	
				}
				while (temp.link != null) {
					temp = temp.link;
				}
			}
		}
		
		return masterlist;
	}
	
	public static class node {
		public int key;
		public node link;
		
		public int[] getResult() {
			
			int[] result;
			int size = 1;
			
			node temp = link;
			while (temp != null) {
				temp = temp.link;
				size++;
			}
			
			result = new int[size];
			
			temp = link;
			for (int i = 0; i < size; i++) {
				if (temp != null) {
					if (i == 0) {
						result[i] = key;
					} else {
						result[i] = temp.key;
						temp = temp.link;
					}
				}
			}
			
			return result;
		}
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Radix.java

중간에 주석은 테스트를 위한 출력 코드이다. 출력에 필요한 관련 클래스는 github에서 나머지 코드를 찾아보시라.

모든 경우 시간복잡도

단위연산: 비교연산이 없기 때문에 다른 연산을 찾아야 한다. coalesce에서 masterlist의 끝에 노드를 추가하는 연산, distribute에선s while루프의 일부 또는 전체를 단위연산으로 취급할 수 있다. 

입력크기: masterlist에서 정수의 개수 n, 각 정수에서 십진숫자의 최대 개수 numdigits

masterlist 전체를 처음부터 차례로 따라가려면 항상 distribute의 while루프를 n번 수행해야 한다. masterlist에 리스트를 모두 추가하려면 항상 coalesce의 for 루프를 10번 수행해야 한다. (여기서는 마지막 포인터도 두어, 위의 java 코드와는 달리 while루프 없이 한번에 저장할 수 있는 더 효율적인 알고리즘이라 하자)

이 프로시저는 radixsort에서 numdigits번 for문에 의해 호출된다.

따라서,

numdigits와 n을 기준으로 한계값을 표현하기 때문에, 이 알고리즘은 Θ(n)이 아니다. numdigits값을 임의로 크게 하여 n을 기준으로, 임의로 큰 시간복잡도를 만들 수 있다. 10억 자리(numdigits)의 숫자 10개(n)을 정렬한다고 고려 하면 Θ(n^2) 시간이 걸린다. 보통은 numdigits이 훨씬 작다. 최선의 경우 시간 복잡도는 Θ(n lg n)이고, 보통은 최선의 경우에 수렴한다.

추가적인 저장장소 사용

masterlist와 더미를 나타내는 리스트에서 새로운 노드를 만들지 않는다. masterlist의 노드가 더미 리스트로 이동하고, 다시 masterlist로 정렬되는 방식이다. 다만 노드에서 key와 쌍이되는 link가 사용되기 때문에 Θ(n) 링크 만큼 추가 공간을 필요로 한다.

---

내용 출처

Foundations of Algorithms Using C++ Pseudocode 3rd Edition 알고리즘; Richard Neapolitan, Kumarss Naimipour; 도경구 역; 사이텍미디어