반응형
선택정렬
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
int list[MAX_SIZE];
int n;
void selection_sort(int list[], int n)
{
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(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;
}
삽입정렬
// 삽입정렬
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;
}
}
버블정렬
#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);
}
}
쉘 정렬
// 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);
}
}
합병 정렬
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); /* 합병 */
}
}
퀵 정렬
#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;
int partition(int list[], int left, int right)
{
int pivot, temp;
int low, high;
low = left;
high = right + 1;
pivot = list[left];
do {
do
low++;
while (list[low]<pivot);
do
high--;
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;
quick_sort(list, 0, n-1); // 퀵정렬 호출
for (i = 0; i<n; i++)
printf("%d ", list[i]);
printf("\n");
return 0;
}
히프 정렬
#include <stdio.h>
//heapify, 힙 상태 만들기
void heapify(int *arr, int size){
for(int i=1;i<size;++i){
int child = i;
do{
//자식 노드가 부모 노드보다 크면 교환
int root = (child-1)/2;
if(arr[root]<arr[child]){
int temp = arr[root];
arr[root] = arr[child];
arr[child] = temp;
}
child = root;
}while(child!=0); //최상단 노드까지 점검
}
}
//최상단 노드와 최하단 노드 교체
void heap(int *arr, int *size){
int temp = arr[0];
arr[0] = arr[*size-1];
arr[*size-1] = temp;
--(*size);
}
int main(){
int size = 10;
//무작위 배열
int arr[10] = {5, 6, 10, 4, 3, 8, 7, 1, 2, 9};
//힙정렬
for(int i=0;i<10;++i){
heapify(arr, size);
heap(arr, &size);
}
//출력
for(int i=0;i<10;++i){
printf("%d ", arr[i]);
}
return 0;
}
기수 정렬
#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
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++) // 데이터들을 자리수에 따라 큐에 삽입
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;
}
정렬 알고리즘의 비교
정렬의 응용: 영어 사전을 위한 정렬
include<stdio.h>
#include <string.h>
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
#define MAX_WORD_SIZE 50
#define MAX_MEANING_SIZE 500
#define SIZE 5
typedef struct {
char word[MAX_WORD_SIZE];
char meaning[MAX_MEANING_SIZE];
} element;
element list[SIZE]; /* 구조체 배열 선언 */
int main(void)
{
int i, j;
element temp;
printf("5개의 단어와 의미를 입력하시오\n");
for (i = 0; i < SIZE; i++) {
scanf("%s[^\n]", list[i].word); // 엔터키만을 제외하고 받는다.
scanf("%s[^\n]", list[i].meaning);// 엔터키만을 제외하고 받는다.
}
// 버블 정렬
for (i = 0; i < SIZE - 1; ++i) {
for (j = i + 1; j < SIZE; ++j) {
if (strcmp(list[i].word, list[j].word) > 0) {
SWAP(list[i], list[j], temp);
}
}
}
printf("\n정렬 후 사전의 내용: \n");
for (i = 0; i<SIZE; i++) {
printf("%s: %s \n", list[i].word, list[i].meaning);
}
return 0;
}
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 12장 연습문제 해설을 가져오도록 하겠습니다.
반응형