C 정렬 코드

선택 정렬

#include <stdio.h>

int size; // 배열의 크기

void selectionSort(int a[], int size) {
	int t, temp;
	printf("\n정렬할 원소 : ");
	for (t = 0; t < size; t++) {
		printf("%d ", a[t]); // 정렬되기 전에 배열 출력
	}
	printf("\n\n<<<<<<<<<<< 선택정렬 수행<<<<<<<<<<<\n");
	for (int i = 0; i < size-1; i++) {
		for (int j = i + 1; j <size; j++) {
			if (a[j] < a[i]) {
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		printf("%d단계 : ", i + 1);
		for (t = 0; t < size; t++) {
			printf("%d ", a[t]); // 정렬된 후에 배열 출력
		}
		printf("\n");
	}
}

int main() 
{
	int list[8] = { 69,10,30,2,16,8,31,22 };
	size = 8;
	selectionSort(list, size);
}

버블 정렬

#include <stdio.h>

int size; // 배열의 크기

void selectionSort(int a[], int size) {
	int t, temp;
	printf("\n정렬할 원소 : ");
	for (t = 0; t < size; t++) {
		printf("%d ", a[t]); // 정렬되기 전에 배열 출력
	}
	printf("\n\n<<<<<<<<<<< 버블정렬 수행<<<<<<<<<<<\n");
	for (int i = size-1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (a[j] > a[j+1]) {
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
		printf("%d단계 : ", i + 1);
		for (t = 0; t < size; t++) {
			printf("%d ", a[t]); // 정렬된 후에 배열 출력
		}
		printf("\n");
	}
}

int main() 
{
	int list[8] = { 69,10,30,2,16,8,31,22 };
	size = 8;
	selectionSort(list, size);
}

삽입 정렬

#include <stdio.h>

void insertionSort(int data[], int index) { // data배열, index=8
	int temp, j;
	printf("정렬 전 : [ ");
	for (int i = 0; i < index; i++) {
		printf("%3d", data[i]);
	}
	printf(" ]\n");

	printf("정렬 후 : ");
	for (int i = 0; i < index; i++) {
		temp = data[i]; // 예)temp->data[1]=20
		for (j = i; j > 0 && data[j - 1] > temp; j--) { // j=0,j>0,예)data[0]=60>temp=20,j--
			data[j] = data[j - 1]; // data[1]=20>data[0]60으로 변경
		}
		data[j] = temp; // data[1]=20 값을 넣음
		printf("\n %d단계 : ", i + 1);
		for (int i = 0; i < index; i++) {
			printf("%3d", data[i]);
		}
	}
}

int main() 
{
	int data[8] = { 60,20,15,1,3,90,45,70 };
	int index = 8;
	insertionSort(data, index);
}

퀵 정렬

#include <stdio.h>

int size;
int j=0;
int partition(int a[], int begin, int end) {
	int pivot, L, R, temp, t;
	L = begin;
	R = end;
	pivot = (int)((begin + end) / 2); // 중간에 위치한 원소를 피봇원소로 선택
	printf("\n[%d단계 : pivot = %d]\n", ++j, a[pivot]);
	// 퀵정렬 알고리즘
	while (L < R) {
		while (a[L] < a[pivot] && L < R) {
			L++;
		}
		while (a[R] >= a[pivot] && L < R) {
			R--;
		}
		if (L < R) {
			temp = a[R];
			a[R] = a[L];
			a[L] = temp;
		}
	}
	temp = a[pivot];
	a[pivot] = a[R];
	a[R] = temp;
	for (t = 0; t < size; t++) {
		printf("%3d ", a[t]);
	}
	return R;
}

void quickSort(int a[], int begin, int end) {
	int p;
	if (begin < end) {
		p = partition(a, begin, end); // 피봇의 위치
		quickSort(a, begin, p - 1); // 피봇의 왼쪽 부분 집합에 대해 퀵 정렬
		quickSort(a, p + 1, end); // 피봇의 오른쪽 부분 집합에 대해 퀵 정렬
	}
}

int main()
{
	int list[8] = { 69,10,30,2,16,8,31,22 };
	size = 8;

	printf("\n[초기상태]\n");
	for (int i = 0; i <= size - 1; i++) {
		printf(" %d", list[i]);
	}
	quickSort(list, 0, size - 1);
}

쉘 정렬

#include <stdio.h>

void intervalSort(int data[], int begin, int end, int interval) { // begin=0,end=7,interval=4
	int i,j, item;
	for (i = begin + interval; i <= end; i = i + interval) { // i=4,end=7,i=8
		item = data[i]; // a[4] = 3
		for (j = i - interval; j >= begin && item < data[j]; j = j - interval) { // j=0,begin=0,16<19,j=-4
			data[j + interval] = data[j]; // 0+4->data[4]=data[0]
		}
		data[j + interval] = item; // data[0]
	}
}

void shellSort(int data[], int index) {
	int i, t, interval;
	printf("\n정렬할 원소 : ");
	for (t = 0; t < index; t++) {
		printf("%3d", data[t]);
	}
	printf("\n\n<<<<<<<<<< 셀 정렬 수행 >>>>>>>>>>");
	interval = index / 2; // interval=4
	while (interval >= 1) { 
		for (int i = 0; i < interval; i++) {
			intervalSort(data, i, index - 1, interval);
			printf("\n interval = %d >>", interval);
			for (t = 0; t < index; t++) {
				printf("%3d", data[t]);
			}
			printf("\n");
			interval = interval / 2; // interval=2 -> interval=1
		}
	}
}

int main() 
{
	int data[8] = { 60,20,15,1,3,90,45,70 };
	int index = 8;
	shellSort(data, index);
}

병합 정렬

#include <stdio.h>

int index = 8;
int sorted[30];

void merge(int data[], int begin, int middle, int end) {
	int i, j, k, t;
	i = begin; // 첫번째 부분집합(시작위치) i=0
	j = middle + 1; // 두번째 부분집합 시작위치 j=4
	k = begin; // sorted배열에 배열 병합 
	while (i <= middle && j <= end) {
		if (data[i] <= data[j]) {
			sorted[k] = data[i];
			i++;
		}
		else {
			sorted[k] = data[j];
			j++;
		}
		k++;
	}
	if (i > middle) {
		for (t = j; t <= end; t++) {
			sorted[k++] = data[t];
		}
	}
	else {
		for (t = i; t <= middle; t++) {
			sorted[k++] = data[t];
		}
	}
	for (t = begin; t <= end; t++) {
		data[t] = sorted[t];
	}
	printf("\n병합된 배열 : ");
	for (t = 0; t < index; t++) {
		printf("%3d", data[t]);

	}
}

void mergeSort(int data[], int begin, int end) {
	int middle;
	if (begin < end) {
		middle = (begin + end) / 2; // middle=3
		mergeSort(data, begin, middle); // 앞부분에 대한 분할 작업 수행 0,1,2,3
		mergeSort(data, middle + 1, end); // 뒷부분에 대한 분할 작업 수행 4,5,6,7
		merge(data, begin, middle, end); // 부분집합의 정렬과 병합 작업 수행 begin=0,middle=3,end=7
	}
}

int main() {
	int data[8] = { 60,20,15,1,3,90,45,70 };
	printf("\n 정렬할 원소 >>");
	for (int i = 0; i < index; i++) {
		printf("%3d", data[i]);
	}
	printf("\n\n<<<<<<<< 병합 정렬 수행 >>>>>>>>\n");
	mergeSort(data, 0, index - 1);
}