물마시니의 구구절절

이번에는 퀵 정렬 알고리즘이다

물론 역시 이산수학 과제로 나온 녀석이다

정렬은 뭐니뭐니해도 간만한 버블정렬 만한게 없다는..?!;;;;;

임은기 교수님이 들으면 싸닥션 맞을 소리를 덜덜;;

자세한 소스는 밑에서 +_+ㅋ

[spoiler]

// 이산수학 퀵소트 알고리즘 구현
#include <stdio.h>

#define ELEMENT int // 입력받을 자료형
#define MAX_LIST_SIZE 8 // 입력 받을 자료의 수

// 함수 프로토 타입
void quick_sort(ELEMENT list[], int left, int right); // 퀵정렬 함수

int partition(ELEMENT list[], int left, int right); // 퀵정렬 함수 안에서 피벗기준 왼쪽과 오른쪽으로 나누는 함수

void swap(int *row, int *high); // 값을 서로 교환해주는 함수

void display_list(ELEMENT list[]); // 리스트를 출력하는 함수

// 함수 본체
void display_list(ELEMENT list[])
{
int i;

for (i = 0; i < MAX_LIST_SIZE; i++) {
printf(”%d “, list[i]);
}
printf(”\n”);
}

void swap(int *row, int *high)
{
int temp;

temp = *row;
*row = *high;
*high = temp;
}

void quick_sort(ELEMENT list[], int left, int right)
{
int q; // 파티션 함수에서 반환되는 피벗 값을 저장

if (left < right) { // left가 right 와 만날때까지 제귀 호출
q = partition(list, left, right); // partition 함수 호출해서 피벗기준으로 2개의 리스트로 분할
quick_sort(list, left, q-1); // left 값에서 피벗 바로 앞 값까지 호출
quick_sort(list, q+1, right); // 피봇 바로 다음부터 right까지 호출
}
}

int partition(ELEMENT list[], int left, int right)
{
int pivot; // 피벗 값을 저장할 변수
int low, high; // low 값과 high 값을 저장할 변수

low = left; // low는 왼쪽에서부터
high = right + 1; // high 는 오른쪽부터
pivot = list[left]; // 피벗은 리스트의 가장 처음 값을 가진다

do { // low와 high가 만날때까지 반복한다

do {
low++; // list[low]값이 피벗보다 작으면 low 값을 계속 증가시킨다
}

while (low <= right && list[low] < pivot);

do {
high–; // list[high]값이 피벗보다 크면 high 값을 계속 감소시킨다
}

while (high >= left && list[high] > pivot);

if (low < high) swap (&list[low], &list[high]); // low가 high 보다 작을때 list[low]값과 list[high]값을 교환한다
display_list(list); // 중간과정 출력
}

while (low < high);

swap(&list[left], &list[high]); // 피벗을 리스트의 중앙에 위치시킨다

return high; // 피벗의 위치를 반환

}

void main ()
{
ELEMENT list[MAX_LIST_SIZE];

int i;

printf(”값을 입력해주세요\n”);

for (i = 0; i < MAX_LIST_SIZE; i++) {
printf(”%d 번째 값 : “, i+1);
scanf(”%d”, &list[i]);
}

display_list(list); // 사용자가 입력한 리스트를 우선 출력한다.

quick_sort(list, 0, MAX_LIST_SIZE-1); // 입력한 값을 정렬

}

[/spoiler]

이번에 이산수학 과제로 나온 최소 비용 신장 트리……

그래프 알고리즘에서 꽤나 많이 쓰인다는데……

(물론 다양하게 응용 가능?!)

이게 꽤나 머리를 써야 만드는 알고리즘이라서

일단 이해 하면서 외우는 방향으로 코딩하였다.

에휴 이런 알고리즘을 듣자마자 바로 짤수 있다면 얼마나 좋을까?

신이시여 나에게 천재적 재능을 제발;;;;;

자세한 소스는 밑에서 계속~

[spoiler]

#include <stdio.h>

#include <malloc.h>

typedef struct edge // 간선을 나타내는 구조체

{

int vertex[2]; // 시작점과 끝점

int cost; // 가중치

}Edge;

int **make_array(int n);// 배열 만들기

void read_array(FILE *file, int *G[], int n);// 파일에서 배열값 읽기

void convert_array_to_edge(int* G[], Edge E[], int n);// 배열을 간선으로 변환

void convert_edge_to_array(int* G[], Edge E[], int n, int m);// 간선을 배열로 변환

void print_edgy(Edge E[], int n);// 간선 집합 출력

void kruskal(int n, int m, Edge E[], Edge F[]);// 크루스칼 알고리즘

void bubble_sort(Edge E[], int m);// 거품 정렬

void find_merge(int p, int q, int U[]);// 집합을 합치는 함수

int find_set(int i, int U[]);// 해당 정점이 어떤 집합에 속하는지 찾는 함수

int main()

{

int n, m; // n개의 정점과 m개의 간선을 저장할 변수

int **G; // 더블 포인터로 동적 배열을 생성할 변수 선언

int **result; // 최소신장 트리를 인접배열로 나타내기 위한 변수 선언


Edge *E, *F;

FILE* file;

file = fopen(”kruskal_array.txt”, “r”);

if(file == NULL) {

perror(”File open error”);

return 0;

}

fscanf(file, “%d %d”, &n, &m); // 파일로부터 m, n을 입력 받는다

E = (Edge *) malloc(sizeof(Edge)*(m-1)); // 처음 입력 받은 배열을 간선으로 저장하기 위한 Edge

F = (Edge *) malloc(sizeof(Edge)*(n-2)); // 최소비용 신장트리 결과를 저장할 Edge

G = make_array(n); // 배열 만들기

result = make_array(n);

read_array(file, G, n); // 파일에서 배열 정보 읽기

convert_array_to_edge(G, E, n); // 배열 정보를 간선 정보로 변환

printf(”\n## Kruskal 최소 비용 신장 트리 ##\n”); // 크루스칼 알고리즘을 돌린 최소 비용 신장 트리를 F 간선 집합에 삽입

kruskal(n, m, E, F); // 최소 비용 신장 트리 결과 출력

printf(”\n최소 비용 신장 트리 결과\n”);

print_edgy(F, n);

printf(”\n최소 비용 신장 트리 결과(인접 배열)\n”);

convert_edge_to_array(result, F, n, m); // n-1개의 간선이 F에 포함되므로

fclose(file);

return 0;

}

void print_edgy(Edge E[], int n) // 간선 집합 출력

{

int i;

for(i = 0; i < n; i++) {

if(E[i].cost != 0)

printf(”v%d -> v%d, 가중치 = %d\n”, E[i].vertex[0]+1, E[i].vertex[1]+1, E[i].cost);

}

}

int** make_array(int n) // N x N 배열 만들기

{

int i, j;

int** array; // N x N 동적 배열을 할당받을 더블 포인터 변수를 선언

n–;

array = (int**)malloc(sizeof(int*)*n);

for(i = 0; i <= n; i++) {

array[i] = (int*)malloc(sizeof(int)*n);

}


for (i = 0; i <= n; i++) {

for (j = 0; j <= n; j++) {

array[i][j] = 0;

}

}


return array; // array의 주소값을 반환해준다

}

void read_array(FILE *file, int *G[], int n) // 파일에서 배열 값을 읽어 배열 G에 저장

{

int i, j;

for(i = 0; i < n; i++) {

for(j = 0; j < n; j++) {

fscanf(file, “%d”, &G[i][j]);

}

}

}

void convert_array_to_edge(int *G[], Edge E[], int n)// 배열 정보를 간선 정보로 변환

{

int i, j, num = 0;

for(i = 0; i < n; i++) { // 배열의 정보를 간선 구조체에 삽입

for(j = i; j < n; j++) {

if( G[i][j] != 0 && G[i][j] != 99 ) { // 가중치의 값이 1에서 99 사이로 존재할때

E[num].vertex[0] = i; // i를 배열 첫번째 요소에 넣는다(간선의 시작점)

E[num].vertex[1] = j; // j를 배열 두번째 요소에 넣는다(간선의 끝점)

E[num].cost = G[i][j]; // 가중치를 넣는다

num++; // E의 다음배열을 증가시켜준다

}

}

}

}

void convert_edge_to_array(int* G[], Edge F[], int n, int m)

{

int i, j;

int sum = 0;

int num = 0;

while (num < m) {

for (i = 0; i < n; i++) {

if (F[num].vertex[0] == i) {

for (j = 0; j < n; j++) {

if (F[num].vertex[1] == j) {

G[j][i] = F[num].cost;

G[i][j] = F[num].cost;

sum += F[num].cost;

continue;

}

}

}

}

num++;

}

for (i = 0; i < n; i++) {

for (j = 0; j < n; j++) {

printf(”%2d “, G[i][j]);

}

printf(”\n”);

}

printf(”총비용 : %d\n”, sum);

}

void kruskal(int n, int m, Edge E[], Edge F[]) // 크루스칼 알고리즘

{

int start_vertex, end_vertax, i, current_edge;

int p, q; // 서로소 체크를 위한 집합을 가리키는 변수

int num = 0;

int* U = (int*)malloc(sizeof(int)*(n-1)); // 집합 선언

Edge edge_temp;

printf(”\n정렬 전 Edge E\n”);

print_edgy(E, m);

bubble_sort(E, m); // E에 속한 m개의 간선을 가중치가 작은 것부터 차례로 정렬

printf(”\n정렬 후 Edge E\n”);

print_edgy(E, m);

for (i = 0; i < n; i++) {// 집합 Initialize

U[i] = i;

}

current_edge = 0;

while(num < n-1) { // 간선의 수가 n-1보다 작을 동안

edge_temp = E[current_edge]; // 아직 고려하지 않은 간선 중 가중치가 최소인 간선

start_vertex = E[current_edge].vertex[0]; // i, j = e에 연결된 정점

end_vertax = E[current_edge].vertex[1];

p = find_set(start_vertex, U); // start_vertax가 속하는 집합을 p에 저장

q = find_set(end_vertax, U); // end_vertax가 속하는 집합을 q에 저장

if(p != q ) { // p와 q 가 서로 속한 집합이 다르다면

find_merge(p, q, U); // p, q가 속한 집합을 합침

F[num] = edge_temp; // edge_temp를 F에 추가

num++;

}

current_edge++;

}

}

int find_set(int i, int U[]) // i가 집합 U의 어느 집합에 속하나?

{

int j;

j = i;

while(U[j] != j) {

j = U[j];

}

return j;

}

void find_merge(int p, int q, int U[]) // p, q를 집합 U에 합칩

{

if (p < q) { // p는 합병된 집합을 가리키는 포인터

U[q] = p; // q는 더 이상 집합을 가리키는 포인터가 아님

}

else {

U[p] = q;

}

}

void bubble_sort(Edge E[], int m) // E 엣지 집합의 가중치를 정렬하기 위한 함수

{

int i, Sorted = 0;

Edge tmp;

while( !S
orted ) {// 정렬이 완료되지 않았으면

Sorted = 1;

for(i = 1; i < m; i++) {

if( E[i-1].cost > E[i].cost ) {

tmp = E[i-1];

E[i-1] = E[i];

E[i] = tmp;

Sorted = 0;

}

}

}

}

[/spoiler]