SFML) 정렬 알고리즘 그래픽으로 구현하기.

많은 사람들이 SFML과 같은 그래픽 라이브러리를 사용하면서 하는 것이 바로 알고리즘을 그래픽으로 구현해 가시화, 시뮬레이션 하는 것이다.

대표적으로 정렬 알고리즘을 많이 하는데 나도 직접 한번 구현해보기로 했다.

 

SFML에서 Rectangle 오브젝트를 가지고 긴 막대기로 각 Element의 value 값을 표시했다.

Element의 value 값이 클 수록 막대기는 위로 길쭉하게 나타나는 것이다.

그 다음 C++의 random 라이브러리를 이용해서 무작위로 섞고 정렬 알고리즘으로 다시 재정렬되는 과정을 그래픽화하였다.

 

#include <SFML/Graphics.hpp>
#include <iostream>
#include <random>
#include <chrono>
#include <vector>
#include <string>

// 정렬될 ELEMENT에 대한 정보.
#define ELEMENT_SIZE 100
#define ELEMENT_WIDTH 5
#define ELEMENT_HEIGHT_MULTIPLIER 2
#define BETWEEN_ELEMENT_SIZE 1
int elements[ELEMENT_SIZE] = {0, };

// Window에 대한 정보.
#define BELOW_BLANK_SIZE 300
#define ABOVE_BLACN_SIZE 50
#define WINDOW_SIZE_WIDTH (ELEMENT_WIDTH + BETWEEN_ELEMENT_SIZE) * (ELEMENT_SIZE + 2)
#define WINDOW_SIZE_HEIGHT ELEMENT_SIZE * ELEMENT_HEIGHT_MULTIPLIER + BELOW_BLANK_SIZE + ABOVE_BLACN_SIZE

// Text에 대한 정보.
sf::Font font;
sf::Text random_text;
sf::Text bubble_text;
sf::Text select_text;
#define TEXT_SIZE 24
#define GAP_BETWEEN_TEXT 10

sf::RenderWindow window(sf::VideoMode(WINDOW_SIZE_WIDTH, WINDOW_SIZE_HEIGHT), "Sorting Simulator");

std::vector<sf::RectangleShape> rect_vec;

// 각 Element에 대해서 그래픽으로 그림.
void DrawElements(int key_element) {
	int i;
	for (i = 0; i < ELEMENT_SIZE; i++) {
		sf::RectangleShape rect(sf::Vector2f(ELEMENT_WIDTH, elements[i] * ELEMENT_HEIGHT_MULTIPLIER));
		rect.setOrigin(0, elements[i] * ELEMENT_HEIGHT_MULTIPLIER);
		rect.setPosition(sf::Vector2f(ELEMENT_WIDTH * 2 + i * (ELEMENT_WIDTH + BETWEEN_ELEMENT_SIZE), WINDOW_SIZE_HEIGHT - BELOW_BLANK_SIZE));
		rect.setFillColor(sf::Color::Black);
		if(i == key_element)
			rect.setFillColor(sf::Color::Green);
		window.draw(rect);
	}
}

// Text에 대한 속성을 설정.
void SetText() {
	random_text.setFont(font);
	random_text.setString("RANDOMIZE");
	random_text.setOutlineThickness(5);
	random_text.setOutlineColor(sf::Color::Black);
	random_text.setPosition(50, WINDOW_SIZE_HEIGHT - BELOW_BLANK_SIZE);
	random_text.setCharacterSize(TEXT_SIZE);

	bubble_text.setFont(font);
	bubble_text.setString("BUBBLE SORT");
	bubble_text.setOutlineThickness(5);
	bubble_text.setOutlineColor(sf::Color::Black);
	bubble_text.setPosition(50, WINDOW_SIZE_HEIGHT - BELOW_BLANK_SIZE + (TEXT_SIZE + GAP_BETWEEN_TEXT));
	bubble_text.setCharacterSize(TEXT_SIZE);

	select_text.setFont(font);
	select_text.setString("SELECTION SORT");
	select_text.setOutlineThickness(5);
	select_text.setOutlineColor(sf::Color::Black);
	select_text.setPosition(50, WINDOW_SIZE_HEIGHT - BELOW_BLANK_SIZE + (TEXT_SIZE + GAP_BETWEEN_TEXT) * 2);
	select_text.setCharacterSize(TEXT_SIZE);
};

void DrawText() {
	window.draw(random_text);
	window.draw(bubble_text);
	window.draw(select_text);
}

void BubbleSort() {
	int i, j, temp;
	sf::Event event;

	for (i = 0; i < ELEMENT_SIZE - 1; i++) {
		for (j = 0; j < ELEMENT_SIZE - i - 1; j++) {
			while (window.pollEvent(event)) {
				if (event.type == sf::Event::Closed) {
					window.close();
					return;
				}
			}

			window.clear(sf::Color::White);
			DrawElements(j);
			DrawText();
			window.display();
			if (elements[j] > elements[j + 1]) {
				temp = elements[j + 1];
				elements[j + 1] = elements[j];
				elements[j] = temp;
			}
		}
	}
}

void SelectionSort() {
	int i, j, least, temp;
	sf::Event event;

	for (i = 0; i < ELEMENT_SIZE - 1; i++) {
		
		least = i;

		for (j = i + 1; j < ELEMENT_SIZE; j++) {

			while (window.pollEvent(event)) {
				if (event.type == sf::Event::Closed) {
					window.close();
					return;
				}
			}

			window.clear(sf::Color::White);
			DrawElements(j);
			DrawText();
			window.display();

			if (elements[j] < elements[least])
				least = j;
		}

		if (i != least) {
			temp = elements[least];
			elements[least] = elements[i];
			elements[i] = temp;
		}
	}
}

int main() {
	int i;
	unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
	bool is_sorting_done = false;
	std::default_random_engine engine(seed);

	font.loadFromFile("Arial.ttf");
	SetText();

	for (i = 0; i < ELEMENT_SIZE; i++) {
		elements[i] = i + 1;
	}

	std::shuffle(elements, elements + ELEMENT_SIZE, engine);

	while (window.isOpen()) {
		sf::Event event;
		while (window.pollEvent(event)) {
			if (event.type == sf::Event::Closed)
				window.close();

		}
		if (sf::Mouse::isButtonPressed(sf::Mouse::Left)) {
			int mouse_x = sf::Mouse::getPosition(window).x;
			int mouse_y = sf::Mouse::getPosition(window).y;

			// randomize 버튼 클릭 시.
			if (random_text.getGlobalBounds().contains(mouse_x, mouse_y)) {
				std::cout << mouse_x << mouse_y;
				std::shuffle(elements, elements + ELEMENT_SIZE, engine);
				is_sorting_done = false;
			}
			// 버블 정렬 버튼 클릭 시.
			if (bubble_text.getGlobalBounds().contains(mouse_x, mouse_y) && is_sorting_done == false) {
				BubbleSort();
				is_sorting_done = true;
			}
			// 선택 정렬 버튼 클릭 시.
			if (select_text.getGlobalBounds().contains(mouse_x, mouse_y) && is_sorting_done == false) {
				SelectionSort();
				is_sorting_done = true;
			}
		}

		window.clear(sf::Color::White);
		DrawElements(-1);
		DrawText();
		window.display();
	}

	return 0;
}

Text의 속성을 처리하는 방식이 지저분한데, 아직 C++의 객체 지향에 익숙하지 않아서 나중에 좀 더 익숙해지면 다시 수정해야겠다.

 

결과.

보완할 점.

- 더 많은 정렬 알고리즘의 구현. (예를 들어, 퀵 정렬, 카운팅 정렬, 힙 정렬, 머지 소트 등)

- 경과 시간 표시로 성능을 수치화하여 비교해볼 수 있는 기능.