본문 바로가기
C/알고리즘

[C] 정렬 알고리즘

by 덤더리덤떰 2024. 2. 12.

1. Selection Sort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <stdbool.h>
#define DATASIZE 16

int* generateRand( int , int );
void selectionSort(int* data, int, int);
void swap(int*, int*);

int main() {

	int i;
	int* data = generateRand(100, DATASIZE);
	printf("\nBefor sorting array\n");
	for (i = 0; i < DATASIZE; i++) {
		printf("%d  ", data[i]);
	}
	printf("\n");

	selectionSort(data, DATASIZE, 1);
	for (i = 0; i < DATASIZE; i++) {
		printf("%d  ", data[i]);
	}
	printf("\n");

	int* data2 = generateRand(57, DATASIZE);
	printf("\nBefor sorting array\n");
	for (i = 0; i < DATASIZE; i++) {
		printf("%d  ", data[i]);
	}
	printf("\n");
	selectionSort(data2, DATASIZE, 2);
	for (i = 0; i < DATASIZE; i++) {
		printf("%d  ", data2[i]);
	}
	printf("\n");



	getchar();
	return 0;
}


int * generateRand(int mod, int size) {
	int* arr = (int*)calloc(size, sizeof(int));
	assert(arr != NULL);
	bool* exist = (bool*)calloc(mod, sizeof(bool));
	assert(exist != NULL);

	srand((unsigned int)time(NULL));

	for (int i = 0; i < size; i++) {
		int random = rand() % mod;
		if (exist[random]) {
			i--;
		}
		else {
			exist[random] = true;
			arr[i] = random;
		}
	}

	return arr;
}

void selectionSort(int* data, int size, int dir) {
	switch (dir) {
	case 1:
		printf("\nIncreasing Sort\n");
		for (int i = 0; i < size - 1; i++) {
			int min = i;
			for (int j = i + 1; j < size; j++) {
				if (data[min] > data[j]) {
					min = j;
				}
			}
			swap(&data[i], &data[min]);
		}
		break;
	case 2:
		printf("\nDecreasing Sort\n");
		for (int i = 0; i < size - 1; i++) {
			int max = i;
			for (int j = i + 1; j < size; j++) {
				if (data[max] < data[j]) {
					max = j;
				}
			}
			swap(&data[i], &data[max]);
		}
		break;
	}
	
}
void swap(int* opA, int*opB) {
	int temp = *opA;
	*opA = *opB;
	*opB = temp;
}

 

2. Bubble Sort

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>
#define DATASIZE 16
#define INCREASING 1
#define DECREASING 2

int* generateRandom();
void swap();
void bubbleSort();

int main() {

	int* data1 = generateRandom(100, DATASIZE);
	printf("\nBefore Sorting array\n");
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data1[i]);
	}
	bubbleSort(data1, DATASIZE, INCREASING);
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data1[i]);
	}

	int* data2 = generateRandom(57, DATASIZE);
	printf("\nBefore Sorting array\n");
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data2[i]);
	}
	bubbleSort(data2, DATASIZE, DECREASING);
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data2[i]);
	}


	getchar();
	return 0;
}

int* generateRandom(int mod, int size) {
	int* arr = (int*)calloc(size, sizeof(int));
	assert(arr != NULL);
	bool* exist = (bool*)calloc(size, sizeof(bool));
	assert(exist != NULL);

	srand((unsigned int)time(NULL));
	for (int i = 0; i < size; i++) {
		int random = rand() % mod;
		if (exist[random]) {
			i--;
		}
		else {
			exist[random] = true;
			arr[i] = random;
		}
	}

	return arr;
}

void swap(int* opA, int* opB) {
	int temp = *opA;
	*opA = *opB;
	*opB = temp;
}

void bubbleSort(int* arr, int size, int dir) {
	switch (dir) {
	case INCREASING:
		printf("\nIncreasing Sort\n");
		for (int i = size - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (arr[j] > arr[j + 1]) {
					swap(&arr[j], &arr[j + 1]);
				}
			}
		}
		break;
	case DECREASING:
		printf("\nDecreasing Sort\n");
		for (int i = size - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[j + 1]) {
					swap(&arr[j], &arr[j + 1]);
				}
			}
		}
		break;
	}
}

 

 

3.Insertion Sort

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

#define DATASIZE 16
#define INCREASING 1
#define DECREASING 2

int* generateRandom();
void insertionSort();

int main() {

	int* data1 = generateRandom(100, DATASIZE);
	printf("\nBefore Sorting array\n");
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data1[i]);
	}
	insertionSort(data1, DATASIZE, INCREASING);
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data1[i]);
	}

	int* data2 = generateRandom(57, DATASIZE);
	printf("\nBefore Sorting array\n");
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data2[i]);
	}
	insertionSort(data2, DATASIZE, DECREASING);
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data2[i]);
	}

	




	getchar();
	return 0;
}


int* generateRandom(int mod,int size) {
	srand((unsigned int)time(NULL));
	int* arr = (int*)calloc(size, sizeof(int));
	assert(arr != NULL);
	bool* exist = (bool*)calloc(size, sizeof(bool));
	assert(exist != NULL);
	for (int i = 0; i < size; i++) {
		int random = rand() % mod;
		if (exist[random]) {
			i--;
		}
		else {
			exist[random] = true;
			arr[i] = random;
		}
	}
	return arr;
}
void insertionSort(int * arr, int size, int dir) {
	switch (dir) {
	case 1:
		printf("\nIncreasing sort\n");
		for (int i = 1; i < size; i++) {
			int key = arr[i];
			int j;
			for (j=i-1; j >= 0 && arr[j] > key; j--) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = key;
		}

		break;

	case 2:
		printf("\nDecreasing sort\n");
		for (int i = 1; i < size; i++) {
			int key = arr[i];
			int j;
			for (j = i - 1; j >= 0 && arr[j] <key; j--) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = key;
		}

		break;
	}
}

 

4. Quick Sort

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

#define DATASIZE 15
#define INCREASING 1
#define DECREASING 2

void quickSort();
int* generateRandom();
void quickSort_increasing();
void quickSort_decreasing();

int main() {
	int* data1 = generateRandom(100, DATASIZE);
	printf("\nBefore Sorting array\n");
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data1[i]);
	}
	quickSort(data1, DATASIZE, INCREASING);
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data1[i]);
	}

	int* data2 = generateRandom(57, DATASIZE);
	printf("\nBefore Sorting array\n");
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data2[i]);
	}
	quickSort(data2, DATASIZE, DECREASING);
	for (int i = 0; i < DATASIZE; i++) {
		printf("%d  ", data2[i]);
	}





	getchar();
	return 0;
}
int* generateRandom(int mod, int size) {
	srand((unsigned int)time(NULL));
	int* arr = (int*)calloc(size, sizeof(int));
	assert(arr != NULL);
	bool* exist = (bool*)calloc(size, sizeof(bool));
	assert(exist != NULL);
	for (int i = 0; i < size; i++) {
		int random = rand() % mod;
		if (exist[random]) {
			i--;
		}
		else {
			exist[random] = true;
			arr[i] = random;
		}
	}
	return arr;
}

void quickSort(int* arr, int size, int dir) {
	switch (dir) {
	case 1:
		printf("\nIncreasing sort\n");
		quickSort_increasing(arr, size, 0, size - 1);
		break;
	case 2:
		printf("\nDecreasing sort\n");
		quickSort_decreasing(arr, size, 0, size - 1);
		break;

	}
}

void quickSort_increasing(int* arr, int size, int left, int right) {
	int pL = left;
	int pR = right;
	int pivot = arr[(left + right) / 2];
	while (pL <= pR) {
		while ( arr[pL] < pivot) {
			pL++;
		}
		while ( arr[pR] > pivot) {
			pR--;
		}
		if (pL <= pR) {
			int temp = arr[pL];
			arr[pL] = arr[pR];
			arr[pR] = temp;
			pL++;
			pR--;
		}
	}
	if (left < pR) {
		quickSort_increasing(arr, size, left, pR);
	}
	if (right > pL) {
		quickSort_increasing(arr, size, pL, right);
	}
}

void quickSort_decreasing(int* arr, int size, int left, int right) {
	int pL = left;
	int pR = right;
	
	int pivot = arr[(left + right) / 2];
	while (pL <= pR) {
		while (arr[pL] > pivot) {
			pL++;
		}
		while (arr[pR] < pivot) {
			pR--;
		}
		if (pL <= pR) {
			int temp = arr[pL];
			arr[pL] = arr[pR];
			arr[pR] = temp;
			pL++;
			pR--;
		}
	}
	if (left < pR) {
		quickSort_decreasing(arr, size, left, pR);
	}
	if (right > pL) {
		quickSort_decreasing(arr, size, pL, right);
	}
}

cf. 왜 pivot을 설정할 때 pivot =arr[(left+right)/2]하면 잘 수행이 되는데 pivot = (left+right)/2를 하고 while문에서 arr[pivot]을 적용시키면 정렬이 안되는지 처음에 이해가 안갔었는데 while문을 수행하며 pL과 pR이 서로 지나치기 전까지는 배열값들이 계속 서로 바뀐다. 그렇기때문에 서로 지나치지만 않으면 pL또는 pR이 pivot 인덱스가 되어 값이 바뀔 수가 있기에 while문에서 arr[pivot]을 하면 맨 처음에 설정했던 left와 right의 중간인 pivot의 값을 얻지 못할 수 있다 

'C > 알고리즘' 카테고리의 다른 글

[C] Prim Algorithm 코드 보완  (0) 2024.02.13
[C] AVL TREE (코드 보완)  (1) 2024.02.12
[C] 이진 탐색 트리 (BST)  (0) 2024.02.08
[C] 이중 연결 리스트  (0) 2024.02.06
[C] AVL TREE  (0) 2023.12.10

관련글

티스토리툴바