7일차

오늘은 알고리즘 말고 유니티를 계속 마저할까 했는데

(유니티 교과서는 진짜 짧다. 벌써 4챕터 밖에 안 남았다 아마 정말 기초만 담았나보다.) 

 

알고리즘은 하루 건너뛰면 왠지 빨리 잊을 것 같기도하고... 퀵 정렬이 꽤 재밌어서 빨리 그 다음 내용도 공부하고 싶어서 오늘도 알고리즘을 공부하기로 했다. 오늘도 화이팅!

 

1. 실습_6-9

#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 Quick(int a[], int left, int right) {
	int pl = left;
	int pr = right;
	int x = a[(pl+pr) / 2]; // 피벗

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

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

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

	free(x);

	return 0;
}

 

2. (Q13) 아래 형식으로 동작하는 quick_sort 함수를 구현하세요. 두 번째 매개변수인 n은 요소의 개수입니다.

void quick_sort(int a[], int n);

#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 Quick(int a[], int left, int right) {
	int pl = left;
	int pr = right;
	int x = a[(pl + pr) / 2]; // 피벗

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

void Quick_sort(int a[], int n) {
	Quick(a, 0, n - 1);
}
// 이런 함수는 왜 만들라고 한 거지...?
// 파라미터를 하나 덜 쓰는 함수가 쓰고 싶어서?
// 아니면 n-1처리를 놓치지 않는지 확인하려고?

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

	Quick_sort(x, nx);
    // 생각해보면 매개변수가 줄었고 -1처리를 여기서 안 하니 나중에 코드해석할 때 헷갈리지 않고 좋은 것 같기도.
	puts("오름차순으로 정렬했습니다.");
	for (i = 0; i < nx; i++)
		printf("x[%d] = %d\n", i, x[i]);

	free(x);

	return 0;
}

---

정답:

///*--- 퀵 정렬 ---*/
//void quick(int a[], int left, int right)
//{
//	int pl = left;				/* 왼쪽 커서 */
//	int pr = right;				/* 오른쪽 커서 */
//	int x = a[(pl + pr) / 2];	/* 피벗(가운데 요소 선택) */
//
//	do {
//		while (a[pl] < x) pl++;
//		while (a[pr] > x) pr--;
//		if (pl <= pr) {
//			swap(int, a[pl], a[pr]);
//			pl++;
//			pr--;
//		}
//	} while (pl <= pr);
//
//	if (left < pr)  quick(a, left, pr);
//	if (pl < right) quick(a, pl, right);
//}
//
///*--- 퀵 정렬(배열, 요솟수) ---*/
//void quick_sort(int a[], int n)
//{
//	quick(a, 0, n - 1);
//}

 

3. 보충_6C-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 Quick(int a[], int left, int right) {
	int pl = left;
	int pr = right;
	int x = a[(pl + pr) / 2]; // 피벗


	printf("a[%d]~[%d]: {", left, right);
	for (int i = left; i < right; i++)
		printf("%d, ", a[i]);
	printf("%d}\n", a[right]);

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

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

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

	free(x);

	return 0;
}

 

4. 실습_6-10

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

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

void Quick(int a[], int left, int right) {
	IntStack lstack;
	IntStack rstack;

	Initialize(&lstack, right - left + 1);
	Initialize(&rstack, right - left + 1);

	Push(&lstack, left);
	Push(&rstack, right);

	while (!IsEmpty(&lstack)) {
		int pl = (Pop(&lstack, &left), left);
		int pr = (Pop(&rstack, &right), right);
		int x = a[(left + right) / 2];
		do {
			while (a[pl] < x) pl++;
			while (a[pr] > x) pr--;
			if (pl <= pr) {
				swap(int, a[pl], a[pr]);
				pl++;
				pr--;
			}
		} while (pl <= pr);

		if (left < pr) {
			Push(&lstack, left);
			Push(&rstack, pr);
		}
		if (pl< right) {
			Push(&lstack, pl);
			Push(&rstack, right);
		}
	}

	Terminate(&lstack);
	Terminate(&rstack);
}

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

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

	free(x);

	return 0;
}