[C언어로 쉽게 풀어쓴 자료구조] Chapter 12 - 정렬

*정렬(sorting) : 물건을 크기순으로 오름차순이나 내림차순으로 나열하는 것을 의미

정렬의 대상은 레코드 (recode) -> 레코드는 필드(field)라고 하는 단위로 구성되어 있음.

EX) 학생 레코드 : [school-num][name][age][address][p-num] -> 5개의 필드로 구성되어 있는 레코드

 

여기서 다른 레코드와 차별되는, 레코드를 특정해주는 필드를 키(key)값 이라고 한다.

즉, 정렬은 레코드를 키값을 기준으로 배열하는 것이다.

 

 

1. 선택 정렬 (selection sort)

// selection sort
#include <stdio.h>
#include <stdlib.h>
// 배열 크기 지정
#define MAX_SIZE 10
// SWAP 함수를 정의 , x와 y값을 바꾸어줌
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

int list[MAX_SIZE];
int n;

// 선택 정렬 함수
void selection_sort(int list[], int n)
{
    // i,j : 변수 , least : 최솟값 , temp : 교환을 위한 변수
	int i, j, least, temp;
	for (i = 0; i < n - 1; i++) {
		least = i;
		for (j = i + 1; j < n; j++) // 최소값 탐색
            // 기존 최솟값 보다 저 작은 값 발견시 최솟값 갱신
			if (list[j] < list[least]) least = j;
        // SWAP을 사용, 더 작은 값을 앞으로 보냄
		SWAP(list[i], list[least], temp);
	}
}


int main(void)
{
	int i;
	n = MAX_SIZE;
	srand(time(NULL)); // 시간의 흐름을 주어서 실행 때 마다 다른 난수를 출력하도록
	for (i = 0; i<n; i++)      	// 난수 생성 및 출력
		list[i] = rand() % 100; // 난수 발생 범위 0~99

	selection_sort(list, n); // 선택정렬 호출
	// 배열 출력
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

/*
4 4 11 41 45 77 79 81 83 84
*/

 

 

2. 삽입 정렬 

// insertion sort
#include <stdio.h>
#include <stdlib.h>
// 배열 크기 지정
#define MAX_SIZE 10

int list[MAX_SIZE];
int n;

void insertion_sort(int list[], int n)
{
	int i, j, key;
	for (i = 1; i<n; i++) {
		key = list[i]; // 삽입 가능성이 있는 요소
		// 인덱스 j에 위치한 요소를 j가 0보다 큰 상태동안,
		for (j = i - 1; j >= 0 && list[j]>key; j--)
			list[j + 1] = list[j]; /* 레코드의 오른쪽 이동 */
		list[j + 1] = key;
	}
}

int main(void)
{
	int i;
	n = MAX_SIZE;
	srand(time(NULL)); // 시간의 흐름을 주어서 실행 때 마다 다른 난수를 출력하도록
	for (i = 0; i<n; i++)      	// 난수 생성 및 출력
		list[i] = rand() % 100; // 난수 발생 범위 0~99

    // 기존 배열 출력
    printf("정렬전 배열 : ");
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");

	insertion_sort(list, n); // 선택정렬 호출
	// 배열 출력
	printf("정렬후 배열 : ");
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

/*
정렬전 배열 : 17 1 25 61 44 18 60 45 75 0
정렬후 배열 : 0 1 17 18 25 44 45 60 61 75
*/

 

 

3. 버블 정렬

// bubble_sort
#include <stdio.h>
#include <stdlib.h>
// 배열 크기 지정
#define MAX_SIZE 10

int list[MAX_SIZE];
int n;

#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
void bubble_sort(int list[], int n)
{
	int i, j, temp;
	for (i = n - 1; i>0; i--) {
        // 가장 큰 인덱스의 위치 부터 정렬
		for (j = 0; j<i; j++)
			/* 앞뒤의 레코드를 비교한 후 교체 */
			if (list[j]>list[j + 1])
				SWAP(list[j], list[j + 1], temp);
	}
}

int main(void)
{
	int i;
	n = MAX_SIZE;
	srand(time(NULL)); // 시간의 흐름을 주어서 실행 때 마다 다른 난수를 출력하도록
	for (i = 0; i<n; i++)      	// 난수 생성 및 출력
		list[i] = rand() % 100; // 난수 발생 범위 0~99

    // 기존 배열 출력
    printf("정렬전 배열 : ");
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");

	bubble_sort(list, n); // 선택정렬 호출
	// 배열 출력
	printf("정렬후 배열 : ");
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

/*
정렬전 배열 : 49 65 96 35 87 67 28 57 9 94
정렬후 배열 : 9 28 35 49 57 65 67 87 94 96
*/

 

 

4. 쉘 정렬 

// shell_sort
#include <stdio.h>
#include <stdlib.h>
// 배열 크기 지정
#define MAX_SIZE 10

int list[MAX_SIZE];
int n;

// 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++; // gap이 짝수인 경우 1을 더해준다.
		printf("현재 gap : %d\n", gap);
		for (i = 0; i<gap; i++)		// 부분 리스트의 개수는 gap
			inc_insertion_sort(list, i, n - 1, gap);
        printf("간격%d 정렬 후 전체 배열 : ",gap);
        for (int j=0; j<n; j++)
            printf("%d ",list[j]);
        printf("\n\n");
	}
}

int main(void)
{
	int i;
	n = MAX_SIZE;
	srand(time(NULL)); // 시간의 흐름을 주어서 실행 때 마다 다른 난수를 출력하도록
	for (i = 0; i<n; i++)      	// 난수 생성 및 출력
		list[i] = rand() % 100; // 난수 발생 범위 0~99

    // 기존 배열 출력
    printf("정렬전 배열 : ");
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n\n");

	shell_sort(list, n); // 선택정렬 호출
	// 배열 출력
	printf("정렬후 배열 : ");
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

/*
정렬전 배열 : 99 88 41 69 52 61 15 70 55 50

현재 gap : 5
간격5 정렬 후 전체 배열 : 61 15 41 55 50 99 88 70 69 52

현재 gap : 3
간격3 정렬 후 전체 배열 : 52 15 41 55 50 69 61 70 99 88

현재 gap : 1
간격1 정렬 후 전체 배열 : 15 41 50 52 55 61 69 70 88 99

정렬후 배열 : 15 41 50 52 55 61 69 70 88 99
*/

 

 

5. 합병 정렬 

// merge_sort
#include <stdio.h>
#include <stdlib.h>
// 배열 크기 지정
#define MAX_SIZE 10

int list[MAX_SIZE];
int num;
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;
	// 왼쪽 리스트 : index 0~mid
	// 오른쪽 리스트 : index mid+1 ~ n-1

	/* 분할 정렬된 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);    /* 합병 */
	}
}
int main(void)
{
	int i;
	num = MAX_SIZE;
	srand(time(NULL)); // 시간의 흐름을 주어서 실행 때 마다 다른 난수를 출력하도록
	for (i = 0; i<num; i++)      	// 난수 생성 및 출력
		list[i] = rand() % 100; // 난수 발생 범위 0~99

    // 기존 배열 출력
    printf("정렬전 배열 : ");
	for (i = 0; i<num; i++)
		printf("%d ", list[i]);
	printf("\n\n");

	merge_sort(list, 0, num-1); // 선택정렬 호출
	// 배열 출력
	printf("정렬후 배열 : ");
	for (i = 0; i<num; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

/*
정렬전 배열 : 82 68 23 19 8 33 28 24 74 46

정렬후 배열 : 8 19 23 24 28 33 46 68 74 82

*/

 

 

6. 퀵 정렬 

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

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

int list[MAX_SIZE];
int n;

// 분할 함수
// left ~ right : 정렬하고자 하는 범위
int partition(int list[], int left, int right)
{
    // pivot : 피벗, temp : SWAP 사용하기 위한 변수
	int pivot, temp;
	// low : 왼쪽 부분 리스트를 만드는데 사용하는 index
	// high : 오른쪽 부분 리스트를 만드는데 사용하는 index
	int low, high;

	low = left;
	high = right + 1;
	pivot = list[left];
	do {
		do
			low++;
        // 왼쪽 리스트에서 요소가 피벗 보다 크면, 그때의 low값과 함께 break!
		while (list[low]<pivot);
		do
			high--;
        // 오른쪽 리스트에서 요소가 피벗 보다 작으면, 그때의 high값과 함께 break!
		while (list[high]>pivot);
		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;

    // 기존 배열 출력
    printf("정렬전 배열 : ");
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n\n");

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

/*
정렬전 배열 : 55 71 55 25 22 28 99 94 19 63

정렬후 배열 : 19 22 25 28 55 55 63 71 94 99

*/

 

 

7. 히프 정렬

 

 

 

8. 기수 정렬 (radix sort) : 낮은 자리 수에서 점차 높은 자리수로 정렬해 나가는 정렬

// radix sort
#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 // 10진수
#define DIGITS  4
// 기수 정렬 함수
void radix_sort(int list[], int n)
{
	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++)			// 데이터들을 자리수에 따라 큐에 삽입 : n%10 => 일의 자리수
			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;
}

/*
3 9 15 26 36 49 80 87 91 97
*/