[Selection Sort]
Idea
- 왼쪽과 오른쪽 2개의 리스트 생성한 후, 초기 상태에서 모든 숫자를 오른쪽에 넣고, 오른쪽에서 가장 작은 숫자를 왼쪽으로 옮긴다. 이 과정을 오른쪽 리스트가 공백이 될 때까지 반복한다. 하지만 이런 방식으로 구현하면 정렬하려는 리스트와 크기가 같은 리스트를 하나 더 만들어줘야 하므로 메모리가 소비된다.
- 따라서 추가적인 리스트를 생성하지 않고 정렬하는 방법을 선택하도록 하자. 입력 배열에서 최솟값을 발견한 다음, 이 최솟값을 배열의 첫번째 원소와 교환(swap)한다. 이 절차를 (정렬하고자하는 숫자 개수 - 1)번 반복하면 숫자를 정렬할 수 있다.
Psuedo Code
selection_sort(A, n); //A는 정렬하고자 하는 리스트, n은 원소의 개수
for i<-0 to n-2 do //(n-1)번 정렬하면 마지막 원소만 남으므로 더 이상 정렬할 필요가 없다.
least<-A[i+1], A[i+2], ... , A[n-1] 중 가장 작은 값의 인덱스;
A[i]와 A[least] 교환;
i++;
C implementation
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t)) //두 원소를 교환하기 위해 SWAP매크로 정의
void selection_sort(int list[], int n)
{
int i, j, least, temp; //temp는 SWAP매크로에서 사용하기 위해 정의
for(i=0;i<n-1;i++){ //0부터 n-2까지(총 n-1번의 swap이후에 모든 원소가 정렬됨.)
least = i;
for(j=i+1;j<n;j++) //least값보다 오른쪽에 있는 원소 개수만큼 반복
if (list[least]>list[j]) least = j; //오른쪽 리스트의 최솟값의 인덱스를 least로 지정
SWAP(list[i], list[least], temp);
}
}
Time Complexity
- 외부 for loop: 0 부터 n-2까지 n-1번 반복
- 내부 for loop: {(n-1)-i} 번 반복
- key값들의 비교 operation은 내부 반복문에서 일어난다. i=0일때는 연산이 (n-1)번, i=1일때는 (n-2)번, ... , i=n-2일때는 1번 수행되므로 총 (n-1)+(n-2)+...+1 = n(n-1)/2 번 수행된다.
- SWAP operation은 외부 for loop안에서 일어나고, 한 번 일어날 때마다 3번의 비교 연산이 진행되므로 time complexity는 3(n-1)이다.
- 따라서 Big O notation을 따르는 time complexity 는 O(n^2)이다.
- 위의 C implementation방식으로 selection sort를 구현하면 i값이 실제 최솟값일때도 불필요한 비교 연산과 이동 연산을 진행하게 된다. 이 부분을 약간 개선하려면 SWAP코드를 실행할지 말지 결정하는 if문을 추가하면 된다.
if (i != least)
SWAP(list[i], list[least], temp);[Insertion Sort]
Idea
- 손 안의 카드를 크기 순으로 정렬하는 방식과 유사하다.
- Selection Sort와 마찬가지로 전체 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나눈다. 이후 정렬되지 않은 부분의 첫번째 숫자가 정렬된 리스트의 어느 부분에 삽입될지 판단한 후 해당 위치에 숫자를 삽입한다.
- 삽입 후에는 정렬된 리스트의 크기가 1만큼 커지고, 정렬되지 않은 리스트의 크기가 1만큼 줄어든다. 이 과정을 정렬되지 않은 리스트의 크기가 0이 될 때까지 반복한다.
Psuedo Code
insertion_sort(A, n)
for i <- 1 to n-1 do //인덱스 값 1부터 시작함. 인덱스 0번은 이미 정렬된 것으로 볼 수 있다.
key <- A[i]; //삽입하고자 하는 숫자를 key값에 복사
j <- i-1; //i-1부터 역순으로 비교 진행(추가하고자 하는 인덱스가 i이므로 0부터 i-1까지가 정렬된 배열이다.)
while j>=0 and A[j]>key do //j가 음수가 아니고 삽입하고자 하는 key값보다 정렬된 리스트의 원소가 크다면
A[j+1] <- A[j]; //원소의 인덱스를 하나 키운다. (j번째 원소를 j+1번째로 이동한다.)
j <- j-1; //j를 하나 감소한다.(while문의 다음 주기에는 한 칸 앞의 원소와 비교연산하기 위함)
A[j+1] <- key //j번째 원소가 key값보다 작으므로 배열의 j+1번째 자리에 key값이 들어가야 한다.
C implementation
void insertion_sort(int list[], int n)
{
int i, j, key;
for(i=1, i<n; i++) {
key = list[i];
for( j = i-1; j >= 0 && list[j] > key; j--) //역순으로 비교연산 수행
list[j+1] = list[j]; //배열 내 원소의 오른쪽 이동
list[j+1] = key;
}
}
Time Complexity
[Merge Sort]
Idea
- Divide-and-Conquer 방식을 사용한다. 전체 배열을 두 개의 동일한 크기의 배열로 계속해서 나눠서 모든 원소를 분리한다. 이후 동일한 크기의 배열을 2개씩 merge(합병)한다. 리스트를 합병하는 과정에서 정렬이 이루어진다.
- 리스트를 합병하기 위해서는 추가적인 리스트가 필요하다. 2개의 리스트의 원소들을 처음부터 하나씩 비교해 더 작은 값을 새로 만든 리스트에 추가한다. 둘 중 한 리스트가 공백이 될 때까지 수행을 계속하고, 둘 중 하나의 리스트가 공백이 되면 나머지 리스트의 모든 원소들을 새로 만든 리스트에 복사한다. (마지막 과정에서 정렬이 아닌 복사를 해도 문제 없는 이유는, 이 전의 과정들에 의해 merge단계에서 만들어진 배열들은 이미 정렬된 상태이기 때문이다.)
Pseudo Code
//재귀 호출을 사용해 리스트를 분할하고 분할된 리스트를 합병한다.
merge_sort(list, left, right):
if left < right //나누어진 리스트의 크기가 1 이상이면
mid = (left+right)/2; //중간 위치를 계산
merge_sort(list, left, mid); //왼쪽 부분 배열을 정렬하기 위해 merge_sort를 재귀 호출
merge_sort(list, mid+1, right); //오른쪽 부분 배열을 정렬하기 위해 merge_sort를 재귀 호출
merge(list, left, mid, right); //정렬된 부분 배열을 merge 해서 결과 출력
//두 개의 인접한 배열 list[left, ..., mid]와 list[mid+1, ..., right]를 합병(merge)하는 함수
merge(list, left, mid, right):
i <- left;
j <- mid+1;
k <- left;
merge된 배열을 저장할 임시 배열 sorted 생성;
while i<=mid and j<=right do
if(list[i] < list[j]) //두 부분 배열의 원소 값 중 작은 것을 선택
then
sorted[k] <- list[i]; //sorted 배열에 추가
k++; //sorted 배열의 인덱스 증가
i++; //원소를 sorted에 추가한 배열의 경우 다음 주기에서 다음 원소의 비교를 위해 인덱스 증가
else
sorted[k] <- list[j]; //sorted 베열에 추가
k++;
j++;
//둘 중 하나의 부분 배열이 공백이 되면(모든 원소를 sorted에 저장한 상태)
요소가 남아있는 부분 배열을 sorted로 복사한다;
sorted를 list로 복사한다;
C implementation
int sorted[MAX_SIZE]; //정렬한 부분 배열들을 임시로 저장할 배열 생성
//i는 정렬된 왼쪽 리스트에 대한 인덱스
//j는 정렬된 오른쪽 리스트에 대한 인덱스
//k는 정렬될 리스트에 대한 인덱스
void merge(int list[], int left, int mid, int right)
{
int i, j, k, l;
i= left; j= mid+1; k= left;
//분할 정렬된 리스트의 합병(merge)
while( i ,+mid && j <= right) {
if(list[i] <= list[j])
sorted[k++] = list[i++];
else
sorted[k++] = list[j++];
}
if(i>mid) //오른쪽에 남아 있는 리스트가 존재한다면 sorted에 일괄 복사
for(l=j;l<=right;l++)
sorted[k++] = list[l];
else //왼쪽에 남아 있는 리스트가 존재한다면 sorted에 일괄 복사
for(l=i;l<=mid;l++)
sorted[k++] = list[l];
//sorted[]배열을 다시 list[]로 복사
for(l=left;l<=right;l++)
list[l] = sorted[l];
}
void merge_sort(int list[], int left, int right)
{
int mid = (left+right)/2; //리스트 균등 분할
if(left<right){
merge_sort(list, left, mid); //부분 리스트 정렬
merge_sort(list, mid+1, right); //부분 리스트 정렬
merge(list, left, mid, right); //합병
}
Time Complexity
[Quick Sort]
Idea
Pseudo Code
C implementation
Time Complexity
[Radix Sort]
Idea
- 입력 데이터에 대해 어떠한 비교 연산도 진행하지 않고 정렬하는 방법이다. 기존에 소개한 정렬들은 시간 면에서O(nlogn)라는 이론적인 하한선을 가지는데, Radix Sort는 이 하한선을 깰 수 있는 유일한 방법이다.
- 정렬하고자 하는 수를 자릿수별로 나눈 후 낮은 자릿수부터 높은 자릿수 순으로 정렬한다. 십진수의 경우 10개의 버킷을 만들어 입력 데이터를 각 자리수별로 크기에 따라 정렬 후 버킷에 넣는다.
- 버킷에 먼저 들어간 수는 먼저 나와야 한다. 그러므로 버킷은 큐를 사용해 구현해야 한다. 큐로 구현해야 리스트 상의 요소들의 상대적인 순서가 유지된다. 버킷에 수를 넣는 연산은 큐의 삽입연산이고, 버킷에서 숫자를 읽는 연산은 삭제 연산으로 대체하면 된다.
Pseudo Code
RadixSort(list, n):
for d<-LSD의 위치 to MSD의 위치 do
{
d번째 자릿수에 따라 0번부터 9번 버킷에 집어넣는다.
버킷에서 숫자들을 순차적으로 읽어서 하나의 리스트로 합친다.
d++;
}
C implementation
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
#define BUCKETS 10
#define DIGITS 4
#define SIZE 10
typedef int element;
typedef struct {
element data[MAX_QUEUE_SIZE];
int front, rear;
}QueueType;
//오류 처리
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
//queue 초기화
int init_queue(QueueType *q)
{
q->front = q->rear =0;
}
//공백 상태 검출 함수
int is_empty(QueueType *q)
{
return( q->front == q->rear);
}
//포화 상태 검출 함수
int is_full(QueueType *q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
//삽입 함수
void enqueue(QueueType *q, element item)
{
if(is_full(q))
error("큐가 포화 상태입니다.");
q->rear = (q->rear +1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
//삭제 함수
element dequeue(QueueType *q)
{
if(is_empty(q))
error("큐가 공백 상태입니다.");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
//Radix Sort
void radix_sort(int list[], int n)
{
int i, b, d;
int factor = 1;
QueueType queues[BUCKETS];
for(b=0;b<BUCKETS;b++)
init_queue(&queues[b]); //큐들을 초기화함
for(d=0;d<DIGITS;d++){
for(i=0;i<n;i++) //데이터를 자릿수별로 큐에 삽입
enqueue(&queues[(list[i] / factor) % 10], list[i]);
for(b=i=0;b<BUCKETS;b++)
while(!is_empty(&queues[b]))
list[i++] = dequeue(&queues[b]);
factor *= 10; //다음 자릿수로 이동
}
}
int main(void)
{
int list[SIZE];
srand(time(NULL));
for(int i=0;i<SIZE;i++) //난수 생성 및 출력
list[i] = rand() % 10;
radix_sort(list, SIZE); //radix sort
for(int i=0;i<SIZE;i++)
printf("%d", list[i]);
printf("\n");
return 0;
}
Time Complexity
- 입력 리스트가 n개의 정수를 가지고 있다면 radix sort 알고리즘의 내무 for loop는 n번 반복되고, 각 정수가 d개의 자릿수를 가지고 있다고 하면 외부 루프는 d번 반복된다. 따라서 radix sort는 O(d*n)의 시간복잡도를 가진다.
- 일반적으로 32bit 컴퓨터의 경우, 대개 10개 정도의 자릿수만을 가지기 때문에 대부분 d는 n에 비해 아주 작다. 따라서 radix sort는 O(n)의 시간복잡도를 가진다고 해도 무방하다.
댓글