[컴퓨터공학] radix sort
- 최초 등록일
- 2002.05.06
- 최종 저작일
- 2002.05
- 2페이지/ 한컴오피스
- 가격 1,000원
목차
기수 정렬(Radix sort)
(1) 기수 정렬 실행 단계
(2) 실행 예
본문내용
기수정렬은 사전식 정렬(lexical sort)의 개념을 기본으로 하여 여러개의 key 에 대한 순서
배열로 이용되는 다중키(multi key)에 대한 정렬 방식이 된다.
1~99번까지의 학생들의 시험지가 일정한 순서없이 나열되어 있을 때 번호순으로 정렬
하려면 우선 10개의 숫자(0~9)를 보관할 10개의 버킷(bucket)을 준비한 후 1의 자리가 0인
학생, 1인 학생, 2인 학생 등으로 분류한 다음 10의 자리가 0인 학생, 1인 학생, …, 9인학생
순서대로 나열하여 분류하면 모든 학생들의 번호가 정렬된다.
데이터가 디지털(digital) 데이터임에 착안하여 고안된 정렬 방법으로서, 분류하고자 하는
레코드의 각 자리에 대해 차례대로 분류하여 정렬을 수행하는 방식이다. 즉, 주기억 장치
내에서 분류 키의 아랫 자리중 숫자를 위해 10개, 영문자를 위해 26의 버켓을 설정하고,
여기에 분류되는 전체 레코드 항목을 저장한 다음 이를 버켓순으로 모아 다음 정렬에 사용
되는 연산을 최하위 자리(LSD : Least Significant Digit)에서부터 순차적으로 최상위의 자리
(MSD : Most Significant Digit)까지 반복 수행하면 레코드들이 순서대로 정렬이 된다.
참고 자료
없음