6일차

오늘은 C#을 좀 많이 공부해서 조금밖에 못할 것 같다.

하지만 오늘도 화이팅

 

1. 실습_6-6 셸 정렬 버전1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

void Shell(int a[], int n) {
	int i, j, h;
	for (h = n / 2; h > 0; h /= 2) {
		for (i = h; i < n; i++) {
			int tmp = a[i];
			for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
				a[j + h] = a[j];
			a[j + h] = tmp;
		}
	}
}

int main() {
	int i, nx;
	int* x;
	puts("셸 정렬");
	printf("요소 개수: ");
	scanf("%d", &nx);
	x = (int*)calloc(nx, sizeof(int));

	for (i = 0; i < nx; i++) {
		printf("x[%d]: ", i);
		scanf("%d", &x[i]);
	}

	Shell(x, nx);

	puts("오름차순으로 정렬했습니다.");
	for (i = 0; i < nx; i++)
		printf("x[%d] = %d\n", i, x[i]);
	free(x);

	return 0;
}

 

2. 실습_6-7 셸 정렬 버전2

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

void Shell(int a[], int n) {
	int i, j, h;
	
	for (h = 1; h < n / 9; h = h * 3 + 1);

	for (; h > 0; h /= 3) {
		for (i = h; i < n; i++) {
			int tmp = a[i];
			for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
				a[j + h] = a[j];
			a[j + h] = tmp;
		}
	}
}

int main() {
	int i, nx;
	int* x;
	puts("셸 정렬");
	printf("요소 개수: ");
	scanf("%d", &nx);
	x = (int*)calloc(nx, sizeof(int));

	for (i = 0; i < nx; i++) {
		printf("x[%d]: ", i);
		scanf("%d", &x[i]);
	}

	Shell(x, nx);

	puts("오름차순으로 정렬했습니다.");
	for (i = 0; i < nx; i++)
		printf("x[%d] = %d\n", i, x[i]);
	free(x);

	return 0;
}

 

3. 연습문제 Q12

요소의 이동 횟수를 계산할 수 있도록 버전 1과 버전 2를 수정한 프로그램을 작성하세요. 여러 가지 배열을 입력하고 프로그램을 실행하며 이동 횟수를 비교해 보세요.

내 답변: 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

void Shellver1(int a[], int n) {
	int i, j, h, move=0;
	for (h = n / 2; h > 0; h /= 2) {
		for (i = h; i < n; i++) {
			int tmp = a[i];
			for (j = i - h; j >= 0 && a[j] > tmp; j -= h){
				a[j + h] = a[j];
				move++;
			}
			a[j + h] = tmp;
			move++;
		}
	}
	printf("\nShellver1 func로 정렬 시 요소의 이동 횟수: %d\n", move);
}


void Shellver2(int a[], int n) {
	int i, j, h, move=0;

	for (h = 1; h < n / 9; h = h * 3 + 1);

	for (; h > 0; h /= 3) {
		for (i = h; i < n; i++) {
			int tmp = a[i];
			for (j = i - h; j >= 0 && a[j] > tmp; j -= h){
				a[j + h] = a[j];
				move++;
			}
			a[j + h] = tmp;
			move++;
		}
	}
	printf("\nShellver2 func로 정렬 시 요소의 이동 횟수: %d\n", move);
}

int main() {
	int i, nx;
	int* x;
	puts("셸 정렬");
	printf("요소 개수: ");
	scanf("%d", &nx);
	x = (int*)calloc(nx, sizeof(int));

	for (i = 0; i < nx; i++) {
		printf("x[%d]: ", i);
		scanf("%d", &x[i]);
	}

	// Shellver1(x, nx);
	Shellver2(x, nx);

	puts("오름차순으로 정렬했습니다.");
	for (i = 0; i < nx; i++)
		printf("x[%d] = %d\n", i, x[i]);
	free(x);

	return 0;
}

---

정답:

한 프로젝트 내에서 한 번에 풀라는 뜻은 아니었나보다. 나도 요소의 이동 횟수를 변수로(답지에는 count, 내가 쓴 거에선 move) 리턴할까 했는데 그럼 main 함수에서 코드가 길어지기도 하고, 나는 하나의 프로젝트로 합쳐놨으니 어떤 함수가 가동되었는지 콘솔창만 봐서는 알 수가 없어 void로 처리했다. 그리고 함수 내에서 출력하는 것으로 처리했다.

///*--- 셸 정렬(버전 1 : shell1.c를 수정) ---*/
//int shell(int a[], int n)
//{
//	int i, j, h;
//	int count = 0;					
//
//	for (h = n / 2; h > 0; h /= 2)
//		for (i = h; i < n; i++) {
//			int	 tmp = a[i];
//			for (j = i - h; j >= 0 && a[j] > tmp; j -= h) {
//				a[j + h] = a[j];
//				count++;
//			}
//			a[j + h] = tmp;
//			count++;
//		}
//	return count;
//}

///*--- 셸 정렬(버전 2 : shell2.c를 수정) ---*/
//int shell(int a[], int n)
//{
//	int i, j, h;
//	int count = 0;					
//
//	for (h = 1; h < n / 9; h = h * 3 + 1)
//		;
//
//	for (; h > 0; h /= 3)
//		for (i = h; i < n; i++) {
//			int	 tmp = a[i];
//			for (j = i - h; j >= 0 && a[j] > tmp; j -= h) {
//				a[j + h] = a[j];
//				count++;
//			}
//			a[j + h] = tmp;
//			count++;
//		}
//	return count;
//}

둘다 main 함수는 빼고 가져왔다.

 

4. 실습_6-8 퀵정렬(1)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define swap(type,x,y) do{type t=x;x=y;y=t;}while(0)

void partition(int a[], int n) {
	int i;
	int pl = 0;
	int pr = n - 1;
	int x = a[n / 2]; // 피벗

	do {
		while (a[pl] < x) pl++;
		while (a[pr] > x) pr--;
		for (i = pr; a[i] > x; i--);
		if (pl <= pr) {
			swap(int, a[pl], a[pr]);
			pl++;
			pr--;
		}
	} while (pl <= pr);

	printf("피벗의 값은 %d입니다.\n", x);
	printf("피벗 이하의 그룹\n");
	for (i = 0; i < pl; i++)
		printf("%d ", a[i]);
	putchar('\n');
	if (pl > pr + 1) {
		printf("피벗과 일치하는 그룹\n");
		for (i = pr + 1; i <= pl-1; i++)
			printf("%d ", a[i]);
		putchar('\n');
	}
	printf("피벗 이상의 그룹\n");
	for (i = pr + 1; i < n; i++)
		printf("%d ", a[i]);
	putchar('\n');
}

int main() {
	int i, nx;
	int* x;
	puts("배열을 나눕니다.");
	printf("요소 개수: ");
	scanf("%d", &nx);
	x = (int*)calloc(nx, sizeof(int));

	for (i = 0; i < nx; i++) {
		printf("x[%d]: ", i);
		scanf("%d", &x[i]);
	}

	partition(x, nx);

	free(x);

	return 0;
}

재밌다... 그리고 이거 생각해낸 사람은 진짜 머리가 좋은 것 같다. 설명 읽다가 감탄사가 절로 나왔다.