정렬 알고리즘 모음

내가 보려고 올리는 정렬 알고리즘 모음

빠진 거 있을 수도 있음

왤케 안 외워지는지... 빡머갈인지.....＞︿＜.

그냥 저 버블정렬이랑만 살게 해주세요....

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

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

//선택정렬
//우선순위큐(무순리스트), O(n^2)
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[least] > list[j])
				SWAP(list[least], list[j], temp);
		}
	}
}

//삽입정렬
//우선순위큐(순서리스트), O(n^2)
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;
	}
}

//버블정렬
void bubble_sort(int list[], int n) {
	int i, j, temp;
	for (int i = n - 1; i > 0; i--) {
		for (int j = 0; j < i; j++)
			if (list[j] > list[j + 1])
				SWAP(list[j], list[j + 1], temp);
	}
}

//--------------------------------------------------------------------
//힙정렬
//O(nlogn) 우선순위 큐(힙으로 구현)
typedef struct {
	int heap[MAX_SIZE];
	int heap_size;
}HeapType;

void init(HeapType* h) {
	h->heap_size = 0;
}

void upHeap(HeapType* h) {
	int i = h->heap_size;
	int key = h->heap[i];

	//루트가 아닌 경우, 부모 노드의 값보다 작은 경우 swap
	while (i != 1 && key < h->heap[i / 2]) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}

	h->heap[i] = key;
}

void downHeap(HeapType* h) {
	int temp = h->heap[1];
	int parent = 1, child = 2;
	while (child <= h->heap_size) {
		if ((child < h->heap_size) && (h->heap[child] > h->heap[child + 1]))
			child++;
		if (temp <= h->heap[child]) break;

		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
}

void insertItem(HeapType* h, int key) {
	h->heap_size += 1;
	h->heap[h->heap_size] = key;
	upHeap(h);
}

int removeMin(HeapType* h) {
	int key = h->heap[1];
	h->heap[1] = h->heap[h->heap_size];
	h->heap_size -= 1;
	downHeap(h);
	return key;
}

void printHeap(HeapType* h) {
	for (int i = 1; i <= h->heap_size; i++) {
		printf("%d ", h->heap[i]);
	}

	printf("\n");
}

void  heap_sort(HeapType* h, int list[]) {
	HeapType heap;
	init(&heap);
	for (int i = 1; i <= h->heap_size; i++) {
		heap.heap[i] = h->heap[i];
		heap.heap_size++;
	}

	for (int i = 1; i <= h->heap_size; i++) {
		list[i] = removeMin(&heap);
	}
}

//제자리 힙정렬
void inPlaceHeapSort(HeapType* h) {
	int size = h->heap_size;
	int key;
	for (int i = 0; i < size; i++) {
		key = removeMin(h);
		h->heap[h->heap_size + 1] = key;
	}
}

//----------------------------------------------------------
//합병정렬
//분할통치 O(nlogn), 순차 데이터 접근
#define MAX_SIZE_MERGE 15

int sorted[MAX_SIZE_MERGE];

void merge(int list[], int left, int mid, int right) {
	int i = left, j = mid + 1, k = left;
	int l;

	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];
		}

	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); //정복
	}
}


//-------------------------------------------
//퀵정렬
//O(nlogn), 분할통치, 제자리, 무작위
#define MAX_SIZE_Q 15
int partition(int list[], int left, int right) {
	int pivot, temp, low, high;
	low = left;
	high = right + 1;
	pivot = list[left];

	do {
		do
			low++;
		while (list[low] < pivot);

		do
			high--;
		while (list[high] > pivot);

		//정렬 과정 출력(생략가능)
		for (int i = 0; i < MAX_SIZE_Q; i++)
			printf("[%d] ", list[i]);

		printf("\nlow=%d, high=%d\n", low, high); getchar();

		if (low < high)
			SWAP(list[low], list[high], temp);
	} while (low < high);

	SWAP(list[left], list[high], temp); //list[high]는 pivot보다 작은 값 중 가장 오른쪽 값
	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);
	}
}

//--------------------------------------
//기수정렬
//O(kn), 메모리사용 큼
#define MAX_SIZE_RADIX 15
#define BUCKETS 10
#define DIGITS 2

typedef int element;
typedef struct {
	element data[MAX_SIZE_RADIX];
	int front, rear;
}QueueType;

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_SIZE_RADIX == q->front;
}

void enqueue(QueueType* q, element item) {
	if (is_full(q)) exit(1);
	q->rear = (q->rear + 1) % MAX_SIZE_RADIX;
	q->data[q->rear] = item;
}

element dequeue(QueueType* q) {
	if (is_empty(q))exit(1);
	q->front = (q->front + 1) % MAX_SIZE_RADIX;
	return q->data[q->front];
}

void queue_print(QueueType* q) {
	if (!is_empty(q)) {
		int i = q->front;
		do {
			i = (i + 1) % MAX_SIZE_RADIX;
			printf("[%d] ", q->data[i]);
			if (i == q->rear)break;
		} while (i != q->front);
	}

	printf("\n");
}

void print_buckets(QueueType queues[]) {
	printf("\n===================\n");
	for (int b = 0; b < BUCKETS; b++) {
		printf("[%d]->",b);
		queue_print(&queues[b]);
	}
	printf("\n===================\n");
}

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]);// 첫째자리 위치에 list[i] 집어넣음

		print_buckets(queues);

		for (b = i = 0; b < BUCKETS; b++)
			while (!is_empty(&queues[b]))
				list[i++] = dequeue(&queues[b]);
		factor *= 10;
	}
}
int main() {
	int list_select[5] = { 1,4,2,19, 7 };
	selection_sort(list_select, 5);

	printf("---------------------\n선택정렬\n");
	for (int i = 0; i < 5; i++)
		printf("%d ", list_select[i]);
	printf("\n");

	int list_insert[5] = { 1,4,2,19, 7 };
	insertion_sort(list_insert, 5);

	printf("---------------------\n삽입정렬\n");
	for (int i = 0; i < 5; i++)
		printf("%d ", list_insert[i]);
	printf("\n");

	int list_bubble[5] = { 1,4,2,19, 7 };
	selection_sort(list_bubble, 5);

	printf("---------------------\n버블정렬\n");
	for (int i = 0; i < 5; i++)
		printf("%d ", list_bubble[i]);
	printf("\n");

	//힙정렬
	printf("---------------------\n힙정렬\n");
	HeapType heap;
	int list_h[MAX_SIZE] = { 0 };
	srand(time(NULL));
	init(&heap);
	for (int i = 0; i < 15; i++)
		insertItem(&heap, rand() % 100);

	printHeap(&heap);

	heap_sort(&heap, list_h);
	printf("힙정렬(오름차순)\n");
	for (int i = 1; i < heap.heap_size; i++) {
		printf("%d ", list_h[i]);
	}
	printf("\n\n");

	getchar();
	printf("제자리 힙정렬(내림차순)\n");
	inPlaceHeapSort(&heap);
	for (int i = 1; heap.heap[i] > 0; i++)
		printf("[%d] ", heap.heap[i]);

	printf("\n-------------------------------\n합병 정렬\n");
	int list_merge[MAX_SIZE_MERGE];
	srand(time(NULL));
	for (int i = 0; i < MAX_SIZE_MERGE; i++) {
		list_merge[i] = rand() % 100;
		//중복 제거
		for (int j = 0; j < i; j++)
			if (list_merge[i] == list_merge[j])
				i--;
	}

	for (int i = 0; i < MAX_SIZE_MERGE; i++)
		printf("[%d] ", list_merge[i]);
	printf("\n\n"); getchar();

	merge_sort(list_merge, 0, MAX_SIZE_MERGE - 1);

	for (int i = 0; i < MAX_SIZE_MERGE; i++) {
		printf("[%d] ", list_merge[i]);
	}
	printf("\n");

	printf("\n--------------------------\n퀵정렬\n");
	int list_quick[MAX_SIZE_Q];
	srand(time(NULL));
	for (int i = 0; i < MAX_SIZE_Q; i++)
		list_quick[i] = rand() % 100;
	for (int i = 0; i < MAX_SIZE_Q; i++)
		printf("[%d] ", list_quick[i]);
	printf("\n\n"); getchar();

	quick_sort(list_quick, 0, MAX_SIZE_Q - 1);

	for (int i = 0; i < MAX_SIZE_Q; i++)
		printf("[%d] ", list_quick[i]);
	printf("\n\n");

	printf("---------------------\n기수정렬\n");
	int list_radix[MAX_SIZE_RADIX];
	srand(time(NULL));
	for (int i = 0; i < MAX_SIZE_RADIX; i++)
		list_radix[i] = rand() % 100;

	for (int i = 0; i < MAX_SIZE_RADIX; i++)
		printf("[%d] ", list_radix[i]);
	printf("\n\n");

	radix_sort(list_radix, MAX_SIZE_RADIX);
	for (int i = 0; i < MAX_SIZE_RADIX; i++)
		printf("[%d] ", list_radix[i]);
	printf("\n\n");

	return 0;
}