Help us understand the problem. What is going on with this article?

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

はじめに

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

可視化してみた

sort2.gif

クイックソートはやっ!

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

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

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

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.
CC0

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

gis
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away