LoginSignup
0
0
@shinonome8090

ソートアルゴリズムを視覚化した

Posted at

1.はじめに

　今回は、バブルソートやクイックソートなどのソートアルゴリズムを視覚的に理解するために役に立つウェブサイトを作成したいと思い開発を行いました。
完成予想図
sort.png
各ソートの解説についてはご自分で調べていただけたらなと思います。豊富にあります。

2.実行環境

環境やツール
windows 10
vscode
HTML
CSS
JavaScript

3.開発プロセス

まず、ソートアルゴリズムの種類を調べ、HTMLとCSSを使い大体のインターフェイスを決定します。
その後、一番簡単であるバブルソートから実装しテストを行い正しく動作するか確認します。
バブルソートの動作が確認できたら、他のソートについて調べて実装していく流れとなります。

4.プログラムの詳細

index.html
<!DOCTYPE html>
<html lang="ja">
<head>
    <meta charset="UTF-8">
    <title>ソートアルゴリズムの視覚化</title>
    <link rel="stylesheet" href="style.css">
</head>
<body>
    <div id="controls">
        <input type="number" id="dataCount" min="1" max="100" placeholder="データ数">
        <button id="generate">生成</button>
        <select id="sortMethod">
            <option value="bubbleSort">バブルソート</option>
            <option value="quickSort">クイックソート</option>
            <option value="mergeSort">マージソート</option>
            <option value="selectionSort">選択ソート</option>
            <option value="insertionSort">挿入ソート</option>
            <option value="heapSort">ヒープソート</option>
        </select>
        <button id="startSorting">ソート開始</button>
        <button id="nextStep">次へ</button>
        <button id="pauseResume">一時停止/再開</button>
        <button id="reset">リセット</button>
    </div>
    <div id="visualization-container"></div>
    <script src="sort.js"></script>
</body>
</html>
style.css
.bar {
    display: inline-block;
    width: 20px; /* 各バーの幅 */
    margin: 2px;
    background-color: teal;
    color: white;
    text-align: center;
    display: flex;
    justify-content: center;
    align-items: center;
    color: white; /* 数字の色 */
    font-size: 16px; /* 数字のサイズ */
}

.selected {
    background-color: red; /* 選択されたバーの色を赤にする */
}

#controls button {
    margin: 5px;
    padding: 10px;
}

#visualization-container {
    display: flex;
    align-items: flex-end;
    height: 300px; /* コンテナの高さ */
    background-color: #f1f1f1;
    margin: 15px;
    padding: 10px;
}
バブルソート
async function bubbleSort() {
    const bars = document.querySelectorAll('.bar');
    for (let i = 0; i < bars.length; i++) {
        for (let j = 0; j < bars.length - i - 1; j++) {
            bars[j].style.backgroundColor = 'red';
            bars[j + 1].style.backgroundColor = 'red';
            if (parseInt(bars[j].textContent) > parseInt(bars[j + 1].textContent)) {
                await swapBars(j, j + 1); // インデックスを渡す
                swapCount++;
            }
            bars[j].style.backgroundColor = 'teal';
            bars[j + 1].style.backgroundColor = 'teal';
        }
    }
    showResult(); // ソートの最後に一度だけ呼び出す
}
クイックソート
async function quickSort(bars = document.querySelectorAll('.bar'), start = 0, end = bars.length - 1) {
    if (start >= end) {
        return;
    }
    
    let index = await partition(bars, start, end);
    await quickSort(bars, start, index - 1);
    await quickSort(bars, index + 1, end);
    showResult(); // 最後にこの関数を呼び出す
}

async function partition(bars, start, end) {
    const pivotValue = parseInt(bars[end].textContent);
    let pivotIndex = start;
    bars[end].style.backgroundColor = 'red';

    for (let i = start; i < end; i++) {
        bars[i].style.backgroundColor = 'yellow';
        await new Promise(resolve => setTimeout(resolve, 300));

        if (parseInt(bars[i].textContent) < pivotValue) {
            await swapBars(i, pivotIndex); // 修正
            swapCount++;
            pivotIndex++;
        }

        bars[i].style.backgroundColor = 'teal';
    }

    await swapBars(pivotIndex, end); 
    swapCount++;
    bars[end].style.backgroundColor = 'teal';

    return pivotIndex;
}
選択ソート
async function selectionSort() {
    const bars = document.querySelectorAll('.bar');

    for (let i = 0; i < bars.length - 1; i++) {
        let minIndex = i;
        bars[i].style.backgroundColor = 'red'; // 現在選択されているバーを赤に
    
        for (let j = i + 1; j < bars.length; j++) {
            bars[j].style.backgroundColor = 'yellow'; // 比較中のバーを黄色に
            await new Promise(resolve => setTimeout(resolve, 300));
    
            if (parseInt(bars[j].textContent) < parseInt(bars[minIndex].textContent)) {
                if (minIndex !== i) {
                    bars[minIndex].style.backgroundColor = 'teal'; // 最小値でなくなったバーをリセット
                }
                minIndex = j;
                bars[minIndex].style.backgroundColor = 'orange'; // 新しい最小値のバーをオレンジに
            }
            if (j !== minIndex) {
                bars[j].style.backgroundColor = 'teal'; // 比較が終わったバーをリセット
            }
        }
        await swapBars(i, minIndex); // 最小値のバーと交換
        swapCount++;
        bars[i].style.backgroundColor = 'teal'; // 交換が終わったバーをリセット
    }
    showResult(); // 最後にこの関数を呼び出す
}
挿入ソート
async function insertionSort() {
    const bars = document.querySelectorAll('.bar');

    for (let i = 1; i < bars.length; i++) {
        let j = i;
        bars[i].style.backgroundColor = 'red'; // 現在操作中のバーを赤色に

        while (j > 0 && parseInt(bars[j - 1].textContent) > parseInt(bars[j].textContent)) {
            await swapBars(j, j - 1); // バーを交換
            bars[j].style.backgroundColor = 'teal'; // 元の位置のバーの色をリセット
            j--;
            swapCount++;
        }

        bars[j].style.backgroundColor = 'teal'; // 最終位置のバーの色をリセット
        await new Promise(resolve => setTimeout(resolve, 300));
    }
    showResult(); // 最後にこの関数を呼び出す
}
ヒープソート
async function heapSort() {
    const bars = document.querySelectorAll('.bar');
    const n = bars.length;

    // ヒープを構築
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        await heapify(bars, n, i);
    }

    // 一つずつ要素を取り出してソート
    for (let i = n - 1; i > 0; i--) {
        await swapBars(0, i); // 修正
        swapCount++;
        await heapify(bars, i, 0);
    }
    showResult(); // 最後にこの関数を呼び出す
}

// ヒープを維持するための関数
async function heapify(bars, n, i) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < n && parseInt(bars[left].textContent) > parseInt(bars[largest].textContent)) {
        largest = left;
    }

    if (right < n && parseInt(bars[right].textContent) > parseInt(bars[largest].textContent)) {
        largest = right;
    }

    if (largest !== i) {
        await swapBars(i, largest); // 修正
        swapCount++;
        await heapify(bars, n, largest);
    }
}
マージソート
async function mergeSort(bars, start, end, depth = 0) {
    if (start < end) {
        const middle = Math.floor((start + end) / 2);
        await mergeSort(bars, start, middle, depth + 1);
        await mergeSort(bars, middle + 1, end, depth + 1);
        await merge(bars, start, middle, end);
    }
}



async function merge(bars, start, middle, end) {
    let i = start;
    let j = middle + 1;

    while (i < j && j <= end) {
        if (parseInt(bars[i].textContent) <= parseInt(bars[j].textContent)) {
            i++;
        } else {
            let temp = j;
            while (temp > i) {
                await swapBars(temp, temp - 1);
                temp--;
            }
            i++;
            j++;
        }
    }
}
グラフを入れ替える
function swapBars(index1, index2) {
    // スワップ操作を同期的に実行するための変更
    const bars = document.querySelectorAll('.bar');
    if (index1 < 0 || index1 >= bars.length || index2 < 0 || index2 >= bars.length) {
        return; // インデックスが無効な場合は処理を中断
    }
    const style1 = bars[index1].style.height;
    const style2 = bars[index2].style.height;

    bars[index1].style.height = style2;
    bars[index2].style.height = style1;
    bars[index1].classList.add('selected');
    bars[index2].classList.add('selected');
    // 数字の交換
    const temp = bars[index1].textContent;
    bars[index1].textContent = bars[index2].textContent;
    bars[index2].textContent = temp;
    // 選択を解除するためのタイムアウトをPromiseでラップ
    return new Promise(resolve => {
        setTimeout(() => {
            bars[index1].classList.remove('selected');
            bars[index2].classList.remove('selected');
            resolve();
        }, 300);
    });
}
sort.js
document.addEventListener('DOMContentLoaded', (event) => {
    const generateButton = document.getElementById('generate');
    const sortButton = document.getElementById('startSorting');

    // イベントリスナーの追加
    generateButton.addEventListener('click', generateData);
    sortButton.addEventListener('click', startSorting);
});

let swapCount = 0; // グローバル変数

function startSorting() {
    const selectedSortMethod = document.getElementById('sortMethod').value;
    swapCount = 0;

    switch(selectedSortMethod) {
        case 'bubbleSort':
            bubbleSort().then(showResult);
            break;
        case 'quickSort':
            quickSort().then(showResult);
            break;
        case 'mergeSort':
            mergeSort().then(showResult);
            break;
        case 'selectionSort':
            selectionSort().then(showResult);
            break;
        case 'insertionSort':
            insertionSort().then(showResult);
            break;
        case 'heapSort':
            heapSort().then(showResult);
            break;
    }
}

function showResult() {
    alert(`ソート完了！入れ替え回数: ${swapCount}回`);
}
function generateData() {
    const container = document.getElementById('visualization-container');
    container.innerHTML = ''; // コンテナをクリア
    const count = document.getElementById('dataCount').value;
    for (let i = 0; i < count; i++) {
        const value = Math.floor(Math.random() * 100) + 1;
        const bar = document.createElement('div');
        bar.style.height = `${value}%`; // 高さを値に応じて設定
        bar.style.width = '20px'; // 幅を固定値に設定
        bar.classList.add('bar');
        bar.textContent = value.toString(); // 数字をバーに追加
        container.appendChild(bar);
    }
}

5.完成したもの

6.結論、最後に

問題なく動作しました！って思ったけど、マージソートだけ全然動作しなかった。
なぜだろうか。。。
ソートに関して勉強したのがかなり昔なので1から勉強しようと思います。
他のソートについても何か間違いがあれば指摘お願いします。

0
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0