#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);
}
