IT_Architecture/자료구조 · 알고리즘

[펌] 기수 정렬(Radix Sort)

JJun ™ 2009. 4. 22. 11:37

출처: http://wiki.oracleclub.com/pages/viewpage.action?pageId=4555433#5.8%EA%B8%B0%EC%88%98%EC%A0%95%EB%A0%AC%28RadixSort%29-5.8%EA%B8%B0%EC%88%98%EC%A0%95%EB%A0%AC%28RadixSort%29

==========================================================================

5.8 기수 정렬(Radix Sort)

  • 컴퓨터 자료가 디지털 임을 착안하여 생긴 정렬방법. (2진수를 이용)

5.8.1 기수 교환 정렬(Radix Exchange Sort)의 전략

  • 왼쪽 비트에서 오른쪽 비트로 검사.
  • 재귀호출에 의한 정렬.
  • 약간의 스택(재귀호출을 위한)을 위한 메모리 필요.(소량)
    기수교환 정렬 알고리즘 (a, N, b)

    1. 만약 n > 1 이고 b <= 0 이면
    1.1 N크기의 a배열을 분할하여 비트 1이 시작되는 곳(분할 지점)을 j에 할당
    1.2 기수 교환 정렬 알고리즘(a, j, b-1)
    1.3 기수 교환 정렬 알고리즘(a+j, N-j, b-1)

5.8.2 기수 교환 정렬의 실제

  • p376 참고.
    알파벳 2진수
    O 01001111
    R 01010010
    A 01000001
    C 01000011
    L 01001100
    E 01000101
    C 01000011
    L 01001100
    U 01010101
    B 01000010

5.8.3 Java로 구현한 기수 교환 정렬 (거의 C로 구현한 것과 유사)

자바
package com.oracleclub.study.algorithm;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
public class RadixSort {
	private static final boolean DEBUG = false;
	int bits(int x, int k, int j) {
		if(DEBUG)
			System.out.println("x=" + x + ", k=" + k + ", j=" + j);
		return (x >> k) & ~(~0 << j);
	}
	/**
	 * 10진수->2진수
	 * @param decimal
	 * @param size
	 * @return
	 */
	public static String toString(int decimal, int size) {
		Stack<Byte> stack = new Stack<Byte>();
		while(decimal > 1) {
			byte binary = (byte) (decimal % 2);			
			stack.push(binary);			
			decimal /= 2;
		}
		stack.push((byte)decimal);
		StringBuffer sb = new StringBuffer();
		// 앞에 0 채우기.
		if(stack.size() < size) {
			int loop = size - stack.size();
			for(int i=0; i<loop; i++) {
				sb.append("0");
			}
		}
		// stack 처리.
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		return sb.toString();
	}
	/**
	 * 2진수->10진수
	 * @param binary
	 * @return
	 */
	public static int toDecimal(String binary) {
		int decimal = 0;                  // 10진수 값이 저장 될 변수 초기화
        int i = binary.length()-1;    // String 인덱스 카운터 (n-1 to 0)
        int j = 0;                            // 2진수 인덱스 카운터 (0 to n-1)
                                                // n = String 길이

        while (i >= 0) {
           // String 인덱스 값이 1일 경우 2의 j 배수만큼 decimal 변수에 합산
           if (binary.charAt(i) == '1')
               decimal += Math.pow(2, j);
           i--;          // String 인덱스 감소
           j++;          // 2진수 인덱스 증가
       }
       return decimal;         // 변환된 10진수 결과 값 리턴
	}
	/**
	 * 문자->2진수.
	 * @param c
	 * @return
	 */
	public static String toString(char c) {
		byte b = (byte) c;
		return toString(b, 8);
	}
	void radix_exchange_sort(List<Short> a, int begin_index, int n, short b) {
		if(DEBUG)
			System.out.println("radix_exchange_sort(List<Short>, " + begin_index 
								+ " , " + n + ", " + b + ")");
		short t;
		int i;
		int j;
		if(n>1 && b>=0) {
			i = begin_index;
			j = n -1;
			while(true) {
				while(bits(a.get(i), b, (short)1) == 0 && i < j) {
					i++;
				}
				if(DEBUG)
					System.out.println("left->" + i);
				while(bits(a.get(j), b, (short)1) != 0 && i < j) {
					j--;			
				}
				if(DEBUG)
					System.out.println("right->" + j);
				if(i>=j){
					break;
				}
				t = a.get(i);
				a.set(i, a.get(j));
				a.set(j, t);
				printList(a);
			}				
			if(bits(a.get(n-1), b, (short)1) == 0) {
				j++;
			}
			int bb = b-1;
			radix_exchange_sort(a, begin_index, j,  (short)bb);			
			radix_exchange_sort(a, begin_index + j, n-j, (short)bb);			
		}
	}
	public static void printList(List<Short> lst) {
		System.out.print("[[[");
		for(short s: lst) {
			byte aaa = (byte) (s & 0xff);
			System.out.print((char)aaa);
		}
		System.out.println("]]]");
	}
	public static void main(String[] args) {
		RadixSort sort = new RadixSort();
		List<Short> lst = new ArrayList<Short>();
		lst.add((short)RadixSort.toDecimal("01000001")); // A
		lst.add((short)RadixSort.toDecimal("01001100")); // L
		lst.add((short)RadixSort.toDecimal("01000111")); // G
		lst.add((short)RadixSort.toDecimal("01001111")); // O
		lst.add((short)RadixSort.toDecimal("01010010")); // R
		lst.add((short)RadixSort.toDecimal("01001001")); // I
		lst.add((short)RadixSort.toDecimal("01010100")); // T
		lst.add((short)RadixSort.toDecimal("01001000")); // H
		lst.add((short)RadixSort.toDecimal("01001101")); // M
		
		System.out.println(Collections.checkedList(lst, Short.class));
	}
}

5.8.4 기수 교환 정렬의 분석

  • 숫자의 대소를 따지지 않고, 비트를 따지기 때문에 입력 자료에 별 상관없이 뛰어난 성능 (p379)
  • 비트를 사용하기 때문에 비트가 많이 들어가는 자료형에서는 성능이 좋지 못하다.
  • 부동소숫점연산을 사용하는 데이터는 비트연산을 할 수 없다.
  • 32비트 시스템에서의 자료형.
    자바 자료형 비트
    Byte 8
    Short 16
    Integer 32
    Long 64
    String 무한대

5.8.5 기수 교환 정렬의 개선(비재귀판)

자바
package com.oracleclub.study.algorithm;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
public class RadixExSort {
	static final boolean DEBUG = false;
	int bits(int x, int k, int j) {
		if(DEBUG)
			System.out.println("x=" + x + ", k=" + k + ", j=" + j);
		return (x >> k) & ~(~0 << j);
	}
	void radix_exchange_sort1(List<Integer> list) {
		int n = list.size();
		int t, i, j;
		int l, r;
		int b;
		Stack<Integer> stack = new Stack<Integer>();
		b = 31;
		l = 0;
		r = n-1;
		stack.push(b);
		stack.push(r);
		stack.push(l);
		while(!stack.isEmpty()) {
			l = stack.pop();
			r = stack.pop();
			b = stack.pop();
			if(r>1 && b>=0) {
				i = l;
				j = r;
				while(true) {
					while(bits(list.get(i), b, 1) == 0 && i < j) {
						i++;
					}
					while(bits(list.get(j), b, 1) != 0 && i < j) {
						j--;						
					}
					if(i>=j) {
						break;
					}
					t = list.get(i);
					list.set(i, list.get(j));
					list.set(j, t);
				}
				if(bits(list.get(r), b, 1) == 0) {
					j++;
				}
				stack.push(b-1);
				stack.push(r);
				stack.push(j);
				stack.push(b-1);
				stack.push(j-1);
				stack.push(l);
			}
		}
	}
	public static void main(String[] args) {
		RadixExSort s = new RadixExSort();
		List<Integer> list = new ArrayList<Integer>();
		list.add(10);
		list.add(9);
		list.add(11);
		list.add(122);
		list.add(14);
		list.add(1);
		System.out.println("before=" + Collections.checkedCollection(list, Integer.class));
		s.radix_exchange_sort1(list);
		System.out.println("after=" + Collections.checkedCollection(list, Integer.class));
	}
}

5.8.6 직접 기수 정렬(Straight Radix Sort)의 전략

  • 오른쪽 비트에서 왼쪽 비트로 검사.
  • 분포수세기에 의한 비 재귀적 방법으로 정렬.
    • 키가 많이 중복되는 경우에 가장 효율적.
    • 기수정렬은 비트연산(0 또는 1)만 사용하기 때문에, 키가 많이 중복된다.
  • 분포를 저장하기 위한 배열과 똑같은 크기의 배열이 필요
  • 하지만 속도는 정렬중에서 가장 빠름. => 메모리를 많이 사용할수록 속도가 빨라짐.

5.8.7 직접 기수 정렬의 실제

  • p382 참고.
    알파벳 2진수
    O 01001111
    R 01010010
    A 01000001
    C 01000011
    L 01001100
    E 01000101
    C 01000011
    L 01001100
    U 01010101
    B 01000010

5.8.8 Java로 구현한 직접 기수 정렬 (거의 C로 구현한 것과 유사)

자바
package com.oracleclub.study.algorithm;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
 * 직접 기수 정렬.
 * @author 장선웅
 *
 */
public class RadixSort2 {
	static final boolean DEBUG = false;
	static final int W = 16;
	static final int M = 4;
	static final int MV = 1 << M;
	int bits(int x, int k, int j) {
		if(DEBUG)
			System.out.println("x=" + x + ", k=" + k + ", j=" + j);
		return (x >> k) & ~(~0 << j);
	}
	public void straight_radix_sort(List<Integer> list) {
		int n = list.size();
		int i, j;
		int b[] = new int[n]; 
		int count[] = new int[MV];
		for(i=0; i<W/M; i++) {
			for(j=0; j<MV; j++) {
				count[j] = 0;
			}
			for(j=0; j<n; j++) {
				count[bits(list.get(j), i*M, M)]++;
			}
			for(j=1; j<MV; j++) {
				count[j] = count[j] + count[j-1];
			}
			for(j=n-1; j>=0; j--) {
				b[--count[bits(list.get(j), i*M, M)]] = list.get(j);
			}
			for(j=0; j<n; j++) {
				list.set(j, b[j]);
			}			
		}
		b = null;
		count = null;
	}
	public static void main(String[] args) {
		RadixSort2 s = new RadixSort2();
		List<Integer> list = new ArrayList<Integer>();
		list.add(10);
		list.add(9);
		list.add(11);
		list.add(122);
		list.add(14);
		list.add(1);
		System.out.println("before=" + Collections.checkedCollection(list, Integer.class));
		s.straight_radix_sort(list);
		System.out.println("after=" + Collections.checkedCollection(list, Integer.class));
	}
}
결과
before=[10, 9, 11, 122, 14, 1]
after=[1, 9, 10, 11, 14, 122]

5.8.9 직접 기수 정렬의 분석

장점 :
1. 직접기수정렬은 입력자료에 무관하다.
2. if문이 없는 분포수세기를 활용하였기 ?문에 아주 빠른 속도를 나타낸다.
단점 :
3. 메모리를 너무 많이 사용한다.
4. 정렬키의 비트수가 일정하고, 적어야 한다.

5.8.10 두 가지 기수 정렬법의 일반화

  • 제한된 정렬키를 가지고 있기때문에 일반화하기 어렵다.
  • 결국 각 상황에 맞게 사용해야한다.

문서에 대하여

  • 이 문서의 내용은 C로 배우는 알고리즘 (1) 교재를 스터디 하면서 정리한 내용 입니다.
  • 최초작성자 : [VLDB]
  • 최초작성일 : 2009년 4월 8일
  • 이 문서는 오라클클럽 자바 웹개발자 스터디 모임에서 작성하였습니다.
  • 이 문서를 다른 블로그나 홈페이지에 퍼가실 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^^

'IT_Architecture > 자료구조 · 알고리즘' 카테고리의 다른 글

Tail Recursion  (0) 2011.06.07
[펌] 해쉬 함수의 종류와 특징   (0) 2010.12.27
C로 구현한 정렬 (sort) 알고리즘  (0) 2007.12.25
[펌_java를 이용한 자료구조] 힙(Heap)  (0) 2007.07.02
[펌_java를 이용한 자료구조] 탐색(Searching)  (0) 2007.07.02

'IT_Architecture/자료구조 · 알고리즘'의 다른글

  • 현재글[펌] 기수 정렬(Radix Sort)

관련글

티스토리툴바