[자료구조] - 정렬 /쉘 정렬/합병 정렬/퀵 정렬/기수 정렬

쉘 정렬 : 삽입 정렬 보안 정렬

이론 :

• 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고 각 부분 리스트를 삽입 정렬을 이용하여 정렬.
  모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만둔 후 개수가 1이 될 때까지 알고리즘을 되풀이한다.

구현 :

• 부분 리스트의 개수(간격) = gap
  간격이 1이 될 때가지 반으로 줄이면서 반복

최악의 경우 : O($N^2$)
평균적인 경우 : O($N^1.^5$)

장점 :

• 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 삽입 정렬은 한 번에 한 칸씩만 이동가능한 반면에 쉘 정렬은 더 큰 거리를 이동할 수 있다. 따라서 교환될 때 최종 위치에 더 가까이 있을 가능성이 높아진다.

// gap 만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last
inc_insertion_sort(int list[], int first, int last, int gap)
{
	int i, j, key;
	for (i = first + gap; i <= last; i = i + gap) {
		key = list[i];
		for (j = i - gap; j >= first && key<list[j]; j = j - gap)
			list[j + gap] = list[j];
		list[j + gap] = key;
	}
}
//
void shell_sort(int list[], int n)   // n = size
{
	int i, gap;
	for (gap = n / 2; gap>0; gap = gap / 2) {
		if ((gap % 2) == 0) gap++;
		for (i = 0; i<gap; i++)		// 부분 리스트의 개수는 gap
			inc_insertion_sort(list, i, n - 1, gap);
	}
}

합병 정렬

이론 :

• 1. 분활 : 입력 배열을 같은 크기의 2개의 부분 배열로 분활한다.
• 2. 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.
• 3. 결합 : 정렬된 부분 배열들을 하나의 배열에 통합한다.

합병 정렬 에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계이다. 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두개의 리스트의 요소 중에서 더 작은 요소를 새로운 리스트로 옮긴다.

구현 :

• merge_sort함수에서 배열을 2등분하고 재귀를 통해 부분 배열에 숫자가 하나 남을 때까지 계속된다.
• 분활 과정이 끝나면 정렬된 부분 배열에서 merge 함수를 통해 정렬되며 합병된다.

시간 복잡도는 n개의 데이터를 가지고 logn단계(합병 단계)를 거치기 때문에 O(nlogn)이 된다.

장점 :

• 입력 데이터가 무엇이든간에 정렬되는 시간은 동일. 즉 최악, 평균, 최선의 경우 다 같음.

단점 :

• 임시 배열이 필요, 레코드들의 크기가 큰 경우엔 이동 횟수가 많으므로 큰 시간적 낭비 초래

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;

	/* 분할 정렬된 list의 합병 */
	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}
	if (i>mid)	/* 남아 있는 레코드의 일괄 복사 */
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	else	/* 남아 있는 레코드의 일괄 복사 */
		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;
	if (left<right) {
		mid = (left + right) / 2;     /* 리스트의 균등 분할 */
		merge_sort(list, left, mid);    /* 부분 리스트 정렬 */
		merge_sort(list, mid + 1, right); /* 부분 리스트 정렬 */
		merge(list, left, mid, right);    /* 합병 */
	}
}

퀵 정렬

이론 :

• 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고, 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. 이 상태에서 피벗을 제외한 왼쪽리스트와, 오른쪽 리스트를 다시 정렬한다(재귀).

구현 :

• partition 함수에서
  • low : 왼쪽 부분 리스트 만드는데 사용
  • high : 오른쪽 부분 리스트 만드는데 사용
• low는 왼쪽에서 오른쪽으로 피벗보다 큰 원소를 탐색하다 멈춤
  high는 오른쪽에서 왼쪽으로 피벗보다 작은 원소를 탐색하다가 멈춰진 부분에서 서로 교환(swap)한다.
• 이러한 탐색-교환 과정에서 low와 high가 엇갈려서 지나가게 되면 피벗을 중앙으로 옮긴다.
• 피벗으로 배열이 나눠졌으면 왼쪽, 오른쪽을 위와 같은 방법으로 순환 호출한다(재귀).

분활-정복법에 근거 하여 레코드의 크기가 2배씩 줄어든다(O(logn)). 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어짐. --> O(nlogn)

장점 :

• 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는다.

단점 :

• 정렬된 리스트에 대해서는 오히려 수행시간이 더 많이 걸린다.
  --> O($N^2$)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 3
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

int list[MAX_SIZE];
int n;

int partition(int list[], int left, int right)
{
	int pivot, temp;
	int low, high;	//low, high는 인덱스

	low = left;
	high = right + 1;
	pivot = list[left];
	do {
		do
			low++;
		while (list[low]<pivot);		// pivot보다 작으면 low를 계속 증가
		do
			high--;
		while (list[high]>pivot);		// 피벗보다 크면 high계속 감소
		if (low<high) SWAP(list[low], list[high], temp);	// 둘이 교차하기 전까지 교환
	} while (low<high);										// 둘이 교차하기전까지 반복

	SWAP(list[left], list[high], temp);						// 교차하면 피벗을 중앙에다 위치
	return high;											//피벗의 위치 반환
}
void quick_sort(int list[], int left, int right)	
{
	if (left<right) {
		int q = partition(list, left, right);	// 피벗 설정 후 중간에 넣음
		quick_sort(list, left, q - 1);			// 피번 왼쪽 다시 퀵정렬
		quick_sort(list, q + 1, right);			// 피벗 오른쪽 다시 퀵정렬
	}
}

//
int main(void)
{
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i<n; i++)      	// 난수 생성 및 출력 
		list[i] = rand() % 100; 

	quick_sort(list, 0, n-1); // 퀵정렬 호출 
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

퀵 정렬 라이브러리 함수

함수의 원형

void qsort(
	void *base, 	// 배열의 시작주소
    size_t num, 	// 배열 요소의 개수
    size_t width, 	// 배열 요소 하나의 크기(바이트 단위)
    int (*compare)(const void *, const void *)
    				// 포인터를 통하여 두개의 요소를 비교하여 비교 결과를 정수로 
                    // 반환하는 함수
 );

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

//
int compare(const void *arg1, const void *arg2)
{
	if (*(double *)arg1 > *(double *)arg2) return -1;
	else if (*(double *)arg1 == *(double *)arg2) return 0;
	else return 1;
}
//
int main(void)
{
	int i;
	double list[5] = { 2.1, 0.9, 1.6, 3.8, 1.2 };
	qsort((void *)list, (size_t)5, sizeof(double), compare);
	for (i = 0; i<5; i++)
		printf("%f ", list[i]);
	return 0;
}

기수 정렬 : 레코드를 비교하지 않고도 정렬하는 방법

O(kn) (대부분 k<=4) 의 시간 복잡도를 가지는데 추가 적인 메모리를 감안하더라도 다른 정렬 기법 (O(nlogn))보다 빠르기에 인기 있다.
-내부 루프 n번, 외부 자리수 루프 k번

이론 :

• 십진수 0~9까지의 숫자를 정렬한다고 하면 10개의 버킷(bucket)을 만들어서 입력 데이터를 각 자리수의 값에 따라 상자에 넣는다. 순차적으로 버킷 안에 들어 있는 숫자를 순차적으로 읽는다. 즉 각 자리수의 값에 따라 버킷에 넣고 빼는 동작을 되풀이 했을 뿐이다.

• 2진법을 사용하여 표현하고 정리한다면 버킷은 2개만 있으면 됨
• 알파벳 문자 -> 26개의 버킷

구현 :

• 각 버킷은 원형큐로 구현되어야 리스트 상에 있는 요소들의 상대적인 순서가 유지된다.
• 버킷에 숫자 집어넣는 연산 -> 원형큐의 삽입 연산
  버킷에서 숫자를 읽는 연산 -> 원형큐의 삭제 연산

단점 :

• 정렬에 사용되는 키 값이 숫자로 표현되어야 만이 적용이 가능하다.
  실수, 한글, 한자 등으로 이루어진 키 값을 기수 정렬할 경우 매우 많은 버킷이 필요하므로 적용이 불가능하다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 100
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);
}

// 공백 상태 검출 함수
void 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];
}

#define BUCKETS 10
#define DIGITS  4	// 4자리수 까지 정렬
void radix_sort(int list[], int n)	//1의 자리수 정렬-> 2째자리수 정렬->
									//3째자리수 정렬->4째자리수 정렬 이런식
{
	int i, b, d, 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++)  // 버킷에서 꺼내어 list로 합친다.
			while (!is_empty(&queues[b]))	//각각 버킷이 비어질때까지 반복
				list[i++] = dequeue(&queues[b]);
		factor *= 10;					// 그 다음 자리수로 간다.
	}
}

#define  SIZE 10

int main(void)
{
	int list[SIZE];
	srand(time(NULL));
	for (int i = 0; i<SIZE; i++)      	// 난수 생성 및 출력 
		list[i] = rand() % 100;

	radix_sort(list, SIZE); // 기수정렬 호출 
	for (int i = 0; i<SIZE; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}