バブルソートとクイックソートを可視化して比較する

#はじめに
こちらはC/C++ ([DXライブラリ](http://dxlib.o.oo7.jp/))を使って、バブルソートとクイックソートを可視化して比較する記事です。
ソートアルゴリズムとして有名な**"バブルソート"**と**"クイックソート"**のソート回数を数えていきます。

#可視化してみた

![sort2.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/ef4feffe-d323-c101-cf06-6c1c9eff0cf7.gif)

クイックソートはやっ！

個数を20個、SEED値22にしてみたところ、
クイックソートは20回、バブルソートは100回のソートで終わりました。
(非常にきりがいいですね！)

**"なんと５倍もはやい結果となりました。"**


↓他の値で比べてみたらこんな感じ。

|SEED|Bubble Sort|Quick Sort|
|:---:|:---:|:---:|
|22|100|20|
|0|85|21|
|1|96|22|
|2|94|16|
|100|84|19|
|777|95|21|

#コード

ちょちょいと短時間で書いたので汚いです。

```cpp:Main.cpp

#include "Dxlib.h"

#define SORT_COUNT 20

int qcount = 0;

void QSort(int x[], int left, int right)
{
	int i, j, temp;
	int pivot;
	int move1, move2;
	int sa;

	i = left;
	j = right;

	pivot = x[(left + right) / 2];

	while (1) {

		while (x[i] < pivot)
			i++;

		while (pivot < x[j])
			j--;
		if (i >= j)
			break;

		qcount++;

		move1 = i;
		move2 = j;

		sa = i - j;
		if (sa < 0) sa *= -1;

		for (int move = 0; move < 20; move++) {

			//画面をクリアする処理
			if (ClearDrawScreen()) break;

			//×ボタンが押された時の処理
			if (ProcessMessage()) break;

			DrawFormatString(100, 20, GetColor(255, 255, 255), "[Quick Sort] Count:%d", qcount);

			for (int k = 0; k < SORT_COUNT; k++) {


				if (k == move1) {
					DrawBox(100 + k * 20 + move * sa, 300 - x[k], 100 + k * 20 + 15 + move * sa, 300, GetColor(200, 255, 255), TRUE);
				}
				else if (k == move2) {
					DrawBox(100 + k * 20 - move * sa, 300 - x[k], 100 + k * 20 + 15 - move * sa, 300, GetColor(200, 255, 255), TRUE);
				}
				else {
					if (i > k || j < k)DrawBox(100 + k * 20, 300 - x[k], 100 + k * 20 + 15, 300, GetColor(255, 200, 255), TRUE);
					else DrawBox(100 + k * 20, 300 - x[k], 100 + k * 20 + 15, 300, GetColor(255, 255, 255), TRUE);
				}
			}
			if (ScreenFlip()) break;
		}

		temp = x[i];
		x[i] = x[j];
		x[j] = temp;

		i++;
		j--;
	}

	if (left < i - 1)
		QSort(x, left, i - 1);
	if (j + 1 < right)
		QSort(x, j + 1, right);
}

int BubSort(int x[], int n)
{
	int i, j, temp;

	int count = 0;
	int move1, move2;
	bool moveFlag = false;

	for (i = 0; i < n - 1; i++) {
		for (j = n - 1; j > i; j--) {

			move2 = j;
			move1 = j - 1;

			if (x[j - 1] > x[j]) {
				moveFlag = true;
			}
			if (moveFlag == true) {
				count++;

				for (int move = 0; move < 20; move++) {

					//画面をクリアする処理
					if (ClearDrawScreen()) break;

					//×ボタンが押された時の処理
					if (ProcessMessage()) break;

					DrawFormatString(100, 20, GetColor(255, 255, 255), "[Bubble Sort] Count:%d", count);

					for (int k = 0; k < n; k++) {
						if (k == move1) {
							DrawBox(100 + k * 20 + move, 300 - x[k], 100 + k * 20 + 15 + move, 300, GetColor(200, 255, 255), TRUE);
						}
						else if (k == move2) {
							DrawBox(100 + k * 20 - move, 300 - x[k], 100 + k * 20 + 15 - move, 300, GetColor(200, 255, 255), TRUE);
						}
						else {
							if (i > k)DrawBox(100 + k * 20, 300 - x[k], 100 + k * 20 + 15, 300, GetColor(255, 200, 255), TRUE);
							else DrawBox(100 + k * 20, 300 - x[k], 100 + k * 20 + 15, 300, GetColor(255, 255, 255), TRUE);
						}
					}
					if (ScreenFlip()) break;
				}
			}
			moveFlag = false;

			if (x[j - 1] > x[j]) {
				temp = x[j];
				x[j] = x[j - 1];
				x[j - 1] = temp;
			}
		}

	}

	return 0;
}

//////////+//////////+//////////メイン関数//////////+//////////+//////////
#ifdef __ANDROID__
//Android版のコンパイルだったら android_main
int android_main(void) 
#else
//Windows版のコンパイルだったら WinMain
int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow)
#endif
{
	//背景を黒にする
	if (SetBackgroundColor(0, 0, 0)) return -1; 

	//logの出力を無しにする
	if (SetOutApplicationLogValidFlag(FALSE)) return -1; 
#ifndef __ANDROID__
	//Windows版のコンパイルだったら ChangeWindowMode を実行する										 
	if (ChangeWindowMode(TRUE)) return -1;
	//タイトル
	if (SetMainWindowText("Sort")) return -1;
#endif
	//ウィンドウサイズ
	if (SetGraphMode(600, 400, 32)) return -1;

	//初期化処理
	if (DxLib_Init()) return -1; 

	//裏画面処理
	if (SetDrawScreen(DX_SCREEN_BACK)) {
		DxLib_End();
		return -1;
	}

	//////////+//////////初期化処理//////////+//////////

	//SEED値を決定
	SRand(22);
	int sortCount[SORT_COUNT];
	for (int i = 0; i < SORT_COUNT; i++) {
		sortCount[i] = 1 + GetRand(255);
	}

	//どちらかを選ぶ
	BubSort(sortCount, SORT_COUNT);
	//QSort(sortCount, 0, SORT_COUNT - 1);

	WaitKey();

	//終了処理
	if (DxLib_End()) return -1; 
	return 0;
}

```

#さいごに
最後までお読みいただきありがとうございました。
「いいね！」していただけると、とても励みになります。

**"バブルソートとクイックソートを可視化して比較する"**いかがでしたでしょうか？

ソートアルゴリズム、奥が深いですね。
**"バブルソートとクイックソートを可視化して比較する"**でした。

##ソースコードのライセンス

These codes are licensed under CC0.
[![CC0](https://mirrors.creativecommons.org/presskit/buttons/88x31/svg/cc-zero.svg "CC0")](http://creativecommons.org/publicdomain/zero/1.0/deed.ja)

ソースコードは自由に使用してください。