Sorting Simulator

 유튜브에서 알고리즘으로 다양한 sorting algorithm을 보여주는 영상들이 보여서 한 번 만들어 보기로 하였다. 모든 sorting 알고리즘을 다루지는 않았고 대표적인 몇 개만을 구현하였다. 구현한 Sorting은 Bubble sort, Insertion sort, Selection sort, Quick sort, Merge sort이다.

 각각의 정렬 방법을 선택하였을 때, 1부터 600까지 저장되어 있는 배열을 랜덤하게 섞은 후, 선택한 정렬 방법으로 오름차순으로 재정렬한 후, 정렬 과정을 화면으로 보여주는 것이 프로그램의 주요 내용이다. 또한 해당 과정을 보여주기 위해 몇 개의 장면을 저장하였는 지 출력하는 기능을 추가하였다. 저장된 장면의 수가 많을 수록 비교 혹은 Swap이 많이 이루어졌다는 의미가 되므로 정렬에 많은 시간이 소요되는 것을 의미한다.

 Sorting 알고리즘 자체는 워낙 유명하다 보니까 구현하는 데 큰 어려움이 없었다. 약간의 어려움을 겪었던 부분은 정렬 도중 비교를 하거나 교체되는 등 사건이 있을 때마다 어떨게 정렬 중인 배열을 보여줄 지에 대한 부분이었다. 나는 변화가 있을 때마다 보여주기 보다는 차라리 정렬 중에는 그 때의 배열 상태를 Deque에 저장해 두고, 정렬이 모두 완료된 후에 Deque의 앞부터 참조하여 화면을 그리는 방식을 채택하기로 하였다. 변화 때마다 일일이 보여주는 방식은 SFML로 구현하는 특성상 적합하지 않았기 때문이다. 구조도로 그리면 대략 이렇다.

 

 

 다음은 프로그램의 조작 방법이다.

 

• r : reset
• b : bubble sort
• i : insertion sort
• s : selection sort
• m : merge sort
• q : quick sort

 결과가 출력되는 동안은 별도의 입력이 먹히지 않는다. 만약 출력 중 프로그램을 끄고 싶다면 윈도우 창을 닫는 것이 아니라 콘솔 창을 닫는 방식으로 종료해야 한다.

 혹시라도 다른 sorting 알고리즘을 추가하고 싶다면 방법은 간단하다. 다음과 같은 방식을 따르기만 하면 된다.

1. 본인이 추가하고 싶은 함수를 구현한다. 이때 함수는 정수 배열과 std::deque<int*>&를 매개 변수로 받아야 한다.
2. swap 또는 비교가 일어난 후에는 snap(int* arr, std::deque<int*>& frames)를 추가하여 화면을 저장해야 한다.
3. main 함수의 입력부와 출력부에 해당 함수에 대한 입력과 출력을 추가해준다. 간단하게 if문 2개만 추가하면 된다. 

프로그램 전체 코드는 다음과 같다. 

 

#include <SFML/Graphics.hpp>
#include <SFML/Audio.hpp>
#include <iostream>
#include <Windows.h>
#include <deque>

#define ARR_SIZE 600

//draw
void draw(int* arr, sf::RenderWindow& window) {
	for (int i = 0; i < ARR_SIZE; i++) {
		sf::Vertex toDraw[2] = {
			sf::Vertex(sf::Vector2f(i, 600.0f), sf::Color::Blue), //x is right dir, y is downward(left top corner is standard)
			sf::Vertex(sf::Vector2f(i, 600-arr[i]), sf::Color::Blue)
		};

		window.draw(toDraw, 2, sf::Lines);
	}
}

//catch frame
void snap(int* arr, std::deque<int*>& frames) {
	int* frame = (int*)malloc(sizeof(int)*600);

	for (int i = 0; i < ARR_SIZE; i++)
		frame[i] = arr[i];

	frames.push_back(frame);
}

//clear frames
void clear(std::deque<int*>& frames) {
	while (!frames.empty()) {
		free(frames.back());
		frames.pop_back();
	}
}

//swap indexes
void swap(int* arr, int index_1, int index_2) {
	int temp = arr[index_2];
	arr[index_2] = arr[index_1];
	arr[index_1] = temp;
}

//shuffle
void shuffle(int* arr, std::deque<int*>& frames) {

	std::cout << "Now Shuffling!! : ";

	for (int i = 0; i < ARR_SIZE * 3; i++) {
		int index_1 = rand() % 600;
		int index_2 = rand() % 600;

		swap(arr, index_1, index_2);

		snap(arr, frames);
	}
}

//bubble sort
void bubble_sort(int* arr, std::deque<int*>& frames) {
	for (int i = ARR_SIZE - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[j+1]) {
				swap(arr, j, j+1);
			}
			snap(arr, frames);
		}
	}
}

//selection sort
void selection_sort(int* arr, std::deque<int*>& frames) {
	for (int i = 0; i < ARR_SIZE - 1; i++) {
		int min_index = i;
		for (int j = i + 1; j < ARR_SIZE; j++) {
			if (arr[min_index] > arr[j]) {
				min_index = j;
			}
			snap(arr, frames);
		}
		swap(arr, i, min_index);
	}
}

//insertion sort
void insertion_sort(int* arr, std::deque<int*>& frames) {
	int i, j, key;
	for (i = 1; i < ARR_SIZE; i++) {
		int key = arr[i];
		for (j = i - 1; j >= 0 && arr[j] > key; j--) {
			arr[j + 1] = arr[j];
			snap(arr, frames);
		}
		arr[j + 1] = key;
	}
}
//merge sort
void merge(int* arr, int left, int mid, int right, std::deque<int*>& frames) {
	int* buffer = (int*)malloc(sizeof(int)*ARR_SIZE);
	for (int i = 0; i < ARR_SIZE; i++)
		buffer[i] = arr[i];

	int i, j, k;
	i = left;
	j = mid + 1;
	k = left;

	while(i <= mid && j <= right) {
		if (arr[i] < arr[j])
			buffer[k++] = arr[i++];
		else
			buffer[k++] = arr[j++];

		snap(buffer, frames);
	}

	if (i > mid) {
		for (; j <= right; j++) {
			buffer[k++] = arr[j];
		}
	}
	else {
		for (; i <= mid; i++) {
			buffer[k++] = arr[i];
		}
	}

	snap(buffer, frames);

	for (int i = left; i <= right; i++) {
		arr[i] = buffer[i];
	}

	free(buffer);
}

void merge_sort(int* arr, int left, int right, std::deque<int*>& frames) {
	if(left < right) {
		int piviot = (right + left) / 2;
		merge_sort(arr, left, piviot, frames);
		merge_sort(arr, piviot+1, right, frames);
		merge(arr, left, piviot, right, frames);
	}
}

//quick sort
int partition(int* arr, int left, int right, std::deque<int*>& frames) {
	int low, high, pivot;

	low = left;
	high = right + 1;
	pivot = arr[left];

	do {
		do {
			low++; 
		} while (low <= right && arr[low] < pivot);

		do {
			high--; 
		} while (high >= left && arr[high] > pivot);

		if (low < high) {
			swap(arr, low, high);
		}

		snap(arr, frames);
	} while (low < high);

	swap(arr, low, high);

	snap(arr, frames);

	return high;
}

void quick_sort(int* arr, int left, int right, std::deque<int*>& frames) {
	if (left < right) {
		int q = partition(arr, left, right, frames);

		quick_sort(arr, left, q-1, frames);
		quick_sort(arr, q+1, right, frames);

		snap(arr, frames);
	}
}

//sort state check : true for completely ordered
bool isSorted(int* arr) {
	for (int i = 0; i < ARR_SIZE - 1; i++) {
		if (arr[i] > arr[i+1]) {
			return false;
		}
	}

	return true; 
}

int main() {
	//variables
	int frames_cnt = 0;

	int arr[ARR_SIZE] = { 0, };
	for (int i = 0; i < ARR_SIZE; i++) {
		arr[i] = i + 1;
	}

	//here is where frames saved
	std::deque<int*> frames;

	char action_type = 0;

	sf::RenderWindow window(sf::VideoMode(600, 600), "Sorting_Simulation", sf::Style::Close|sf::Style::Titlebar);

	bool onDrawing = false;

	std::cout << "Sorting Simulation, Here is instruction!!\n"
		<< "bubble sort : b\n"
		<< "selection sort : s\n"
		<< "insertion sort : i\n"
		<< "merge sort : m\n"
		<< "quick sort : q\n"
		<< "bubble sort : b\n"
		<< "reset : r\n";

	while (window.isOpen()) {

		//user input
		sf::Event event;
		while (window.pollEvent(event)&&!onDrawing) {
			switch (event.type)
			{
			case sf::Event::Closed :
				window.close();
				break;
			case sf::Event::TextEntered:
					//reset
					if (event.text.unicode == 'r') action_type = 'r';
					//bubble sort
					else if (event.text.unicode == 'b') action_type = 'b';
					//selection sort
					else if (event.text.unicode == 's') action_type = 's';
					//insertion sort
					else if (event.text.unicode == 'i') action_type = 'i';
					//merge sort
					else if (event.text.unicode == 'm') action_type = 'm';
					//quick sort
					else if (event.text.unicode == 'q') action_type = 'q';
				break;
			default:
				break;
			}
		}

		window.clear(sf::Color::Black);
		if (action_type != 0 && action_type != 'r') {
			if (!onDrawing) {
				//shuffle
				shuffle(arr, frames);

				//sort here
				if (action_type == 'b') {
					std::cout << "bubble sorting\n";
					bubble_sort(arr, frames);
					frames_cnt = frames.size() - 1800;
					onDrawing = true;
				}
				else if (action_type == 's') {
					std::cout << "selection sorting\n";
					selection_sort(arr, frames);
					frames_cnt = frames.size() - 1800;
					onDrawing = true;
				}
				else if (action_type == 'i') {
					std::cout << "insertion sorting\n";
					insertion_sort(arr, frames);
					frames_cnt = frames.size() - 1800;
					onDrawing = true;
				}
				else if (action_type == 'm') {
					std::cout << "merge sorting\n";
					merge_sort(arr, 0, ARR_SIZE-1, frames);
					frames_cnt = frames.size() - 1800;
					onDrawing = true;
				}
				else if (action_type == 'q') {
					std::cout << "quick sorting\n";
					quick_sort(arr, 0, ARR_SIZE-1, frames);
					frames_cnt = frames.size() - 1800;
					onDrawing = true;
				}
			}
			else {
				if (!frames.empty()) {
					draw(frames.front(), window);
					free(frames.front());
					frames.pop_front();
				}
				else {
					action_type = 'r';
					std::cout << "Frame's count(the more, the slower) : " << frames_cnt << std::endl;
					frames_cnt = 0;
				}
			}
		}
		else if (action_type == 'r') {
			for (int i = 0; i < ARR_SIZE; i++) {
				arr[i] = i + 1;
			}
			draw(arr, window);
			onDrawing = false;
			action_type = 0;
		}
		else if (action_type == 0) {
			draw(arr, window);
		}

		window.display();
	}

	clear(frames);

	return 0;
}

 

 깃허브 주소는 다음과 같다.

https://github.com/youngSeok0413/PlayGround/tree/main/sorting_simulation/sorting_simulation

GitHub - youngSeok0413/PlayGround: Playground is for repsotiroy to save what i learned and studied!!

 

 SFML 라이브러리를 이용하여 프로그램을 짜는 것이 상당히 재미있었다. 중간에 파일 입출력에 있어서 문제가 있어서 한참 구글링을 하다가 코드의 문제가 아닌 해당 파일을 프로젝트에 추가해주지 않아서 생긴 문제라는 것을 알고 허탈함을 느낀 일도 있었다. 뭐 이런 것도 코딩 중 발생하는 하나의 재미라고 생각된다. 배열이 정렬되는 것을 눈으로 직접 보는 것은 흥미로운 일이었다. 아쉬웠던 점은 quick sort는 워낙 정렬이 빠르게 이루어져서 순식간에 장면이 지나갔다는 것이다.

 SFML은 좀 더 사용해보기로 하였다. 쉽게 윈도우 프로그램을 만들 수 있다는 점과 관련된 여러 유틸들을 가지고 있어서 재밌는 프로그램을 만들 수 있겠다는 생각이 들었다. 다음 글에서 다시 만나는 것으로 하고 이번 글을 마친다.