[Algorithm] Sort 구현(Bubble, Quick, Stack, Queue) : C

 

Bubble sort

 

#include <stdio.h>

int array[10] = {10, 1, 2, 6, 9, 7, 8, 3, 4, 5};

void sort(int arr[]) {
	int temp = 0;
	int i,j;

	for (i=0; i<10; i++) {
		for (j=i+1; j<10; j++) {
			if (arr[i] > arr[j]) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

int main(void) {
	int i,j;
	int temp = 0;
	
	/*
	for (i=0; i<10; i++) {
		for (j=i+1; j<10; j++) {
			if (array[i] > array[j]) {
				temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
	}*/
	sort(array);	

	for (i=0; i<10; i++) {
		printf("%d ", array[i]);
	}
	printf("\n");

	return 0;
}

 

 

Quick sort

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

int array[10] = {10, 1, 2, 6, 9, 7, 8, 3, 4, 5};

int compare(const void *a, const void *b) {
	int num1 = *(int *)a;
	int num2 = *(int *)b;
	
	if (num1 < num2) return -1;
	if (num1 > num2) return 1;
	
	return 0;
}

int main(void) {
	int i,j;
	int temp = 0;
	
	qsort(array, sizeof(array)/sizeof(int), sizeof(int), compare);

	for (i=0; i<10; i++) {
		printf("%d ", array[i]);
	}
	printf("\n");

	return 0;
}

 

Stack

 

#include <stdio.h>
#define MAX_STACK_SIZE 100

#define true 	1
#define false 	0

int arraylist[MAX_STACK_SIZE];
int sp = -1;

int isEmpty() {
	if (sp < 0) {
		return true;
	} else {
		return false;
	}
}

int isFull() {
	if (sp >= MAX_STACK_SIZE-1) {
		return true;
	} else {
		return false;
	}
}

void push(int value) {
	if (isFull() != true) {	
		arraylist[++sp] = value;
	} else {
		printf("Stack is Full!\n");
	}
}

int pop(void) {
	if (isEmpty() != true) {
		return arraylist[sp--];
	} else {
		printf("Stack is Empty!\n");
		return -1;
	}
}

void print(void) {
	int i;
	for (i=0; i<=sp; i++) {
		printf("%d\n", arraylist[i]);
	}
	printf("-----\n");
}

int main(void) {
	push(1);
	push(5);
	push(7);
	print();
	pop();
	pop();
	print();
}

 

Queue

 

#include <stdio.h>

#define QUEUE_MAX_SIZE 100
#define TRUE 	1
#define FALSE	0

int queue[QUEUE_MAX_SIZE];
int front = -1;
int rear = -1;

int isEmpty(void) {
	if (front == rear) return TRUE;
	else return FALSE;
}

int isFull(void) {
	int tmp = (rear + 1) % QUEUE_MAX_SIZE;
	if (tmp == front) return TRUE;
	else if (front == -1 && rear == QUEUE_MAX_SIZE) return TRUE;
	else return FALSE;
}

void add(int value) {
	if (isFull()) {
		printf("Queue is Full!\n");
	} else {
		rear = (rear + 1) % QUEUE_MAX_SIZE;
		queue[rear] = value;
	}
}

int delete(void) {
	if (isEmpty()) {
		printf("Queue is Empty!");
		return -1;
	} else {
		front = (front + 1) % QUEUE_MAX_SIZE;
		return queue[front];
	}
}

int main(void) {
	add(1);
	add(3);
	add(7);
	printf("%d\n", delete());
	printf("%d\n", delete());
	printf("%d\n", delete());
	
	return 0;
}

 

C언어 특성상 배열 선언 시 배열의 크기를 지정함.

예를 들어 10개의 크기로 배열 선언 시, 0~9번 index까지 사용 가능.

따라서 순환 큐(Circular Queue)를 구현하기 위해 MAX Index 도달 시 다시 초기 value Index로 front의 위치를 바꿔줄 필요가 있다.

 

1) 삽입시 rear가 증가하며 점점 길어짐

2) 삭제 시 앞에서 부터 해야 하기 때문에 앞에 삭제 후 증가(Rear를 점점 따라감)

3) rear와 front의 value가 같으면 Queue는 비었다고 판단

4) front의 사이즈와 (rear + 1) % MAX가 같으면 가득 찼다고 판단할 수 있다.