I. 기수 정렬 (Radix Sort)의 개요
가. 기수 정렬의 정의
- 레코드를 비교하지 않고 준비된 버킷을 이용하여 정렬하는 방법
나. 기수 정렬의 특징
- O (n log2 n) 이라는 이론적인 하한선을 깰 수 있는 유일한 방법
- 시간 복잡도 : O(kn) k : 버킷 수
- 정렬 레코드 타입 제한
Ⅱ. 기수 정렬의 개념 및 사례
가. 기수 정렬의 개념
나. 기수 정렬 사례 (Sorting a sequence of 4-bit integers)
코드 구현
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
public void Radix_Sort(int[] data)
{
int maxsize = getMaxlength(data);
ArrayList<Linear_Queue> bucket = new ArrayList();
int powed=1;
int index = 0;
for(int i=0;i<10;i++) //버킷 생성
{
bucket.add(new Linear_Queue(10));
}
for(int i=1;i<=maxsize;i++) //자리수가 가장 큰 수만큼 전체 반복문을 반복합니다.
{
for(int j=0;j<data.length;j++)
{
bucket.get((data[j]/powed)%10).EnQueue(data[j]); //각 자리수의 맞는 index의 bucket에 넣습니다.
}
for(int k=0;k<10;k++) //버킷에서 데이터를 가지고옵니다.
{
int bucket_num = bucket.get(k).rear;
for(int n=0;n<=bucket_num;n++)
{
data[index] = bucket.get(k).DeQueue();
index++;
}
}
index =0;
powed *=10;
}
}
public int getMaxlength(int[] data)
{
int maxsize = 0;
for(int i=0;i<data.length;i++)
{
int length = (int)Math.log10((double)data[i])+1;
if(maxsize <length)
{
maxsize = length;
}
}
return maxsize; //가장 큰 자리수를 반환합니다.
}
}
|
다음 소스는 Queue 자료 구조 Class입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
public class Linear_Queue {
int rear = -1;
int front = 0;
int maxsize = 0;
int[] Linear_Queue;
public Linear_Queue(int maxsize)
{
this.maxsize = maxsize;
Linear_Queue = new int[maxsize];
}
public void EnQueue(int num)
{
if(rear != maxsize-1)
{
Linear_Queue[++rear] = num;
}
else
{
System.out.println("데이터 다참");
}
}
public int DeQueue()
{
if(rear!=front || (rear==0 && front==0))
{
int tmp =Linear_Queue[front];
for(int i=1;i<=rear;i++)
{
Linear_Queue[i-1] = Linear_Queue[i];
}
rear--;
return tmp;
}
else
{
return -1;
}
}
}
|
[Algorithm] 이진 탐색 (Binary Search)
[Algorithm] 이진 탐색 (Binary Search)
개념정렬된 데이터 집합에서 탐색 범위를 1/2씩 줄여 나가면서 수행하는 방식 I. 이진 탐색 (Binary Search)의 개요 가. 이진 탐색의 정의- 정렬된 데이터 집합에서 탐색 범위를 1/2씩 줄여 나가면
infoofit.tistory.com
[용어/개념] 프로세스(Process) vs 쓰레드(Thread) 비교 정리
[용어/개념] 프로세스(Process) vs 쓰레드(Thread) 비교 정리
프로세스의 정의- 레지스터(register), 스택(stack), 포인트(point), 프로그램, 데이터 등의 집합체로 실행 중인 프로그램 비 동기적 행위, 프로시저(procedure)가 활동 중인 것, 실행 중인 프로시저의 제어
infoofit.tistory.com