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

はじめに

こちらはC/C++ (DXライブラリ)を使って、バブルソートとクイックソートを可視化して比較する記事です。
ソートアルゴリズムとして有名な"バブルソート"と"クイックソート"のソート回数を数えていきます。

可視化してみた

クイックソートはやっ！

個数を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

コード

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

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.

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