VBScriptで学ぶ高度なアルゴリズムとデータ構造：ソート、検索、データ構造の基礎と応用

VBScriptは、Windows環境での自動化やシステム操作に使われるスクリプト言語ですが、アルゴリズムやデータ構造の実装にも十分活用できます。

本記事では、VBScriptを用いて高度なアルゴリズムとデータ構造を学ぶために、ソート、検索、基本的なデータ構造について解説します。

アルゴリズムとは
ソートアルゴリズム
検索アルゴリズム
1. 線形探索（Linear Search）
2. 二分探索（Binary Search）
データ構造
総まとめ
演習問題

アルゴリズムとは

アルゴリズムは、コンピュータで問題を解決するための手順や方法を指します。

適切なアルゴリズムを使うことで、効率的にデータを処理し、結果を得ることが可能です。

ソートアルゴリズム

バブルソート（Bubble Sort）

バブルソートは、最も基本的なソートアルゴリズムの1つです。

このアルゴリズムは、隣接する要素を比較して、大小関係に応じて交換を行うことにより、リストを昇順または降順に並べ替えます。

実装例: VBScriptでのバブルソート

Sub BubbleSort(arr)
    Dim i, j, temp
    For i = UBound(arr) To 1 Step -1
        For j = 0 To i - 1
            If arr(j) > arr(j + 1) Then
                ' 要素の交換
                temp = arr(j)
                arr(j) = arr(j + 1)
                arr(j + 1) = temp
            End If
        Next
    Next
End Sub

' 使用例
Dim myArray
myArray = Array(34, 7, 23, 32, 5, 62)
Call BubbleSort(myArray)

' 結果を表示
For i = 0 To UBound(myArray)
    WScript.Echo myArray(i)
Next

上記のコードでは、バブルソートアルゴリズムが実装されています。

配列myArrayの各要素を、隣接する要素と比較しながら、小さいものから順に並べ替えます。

このアルゴリズムは単純で理解しやすい反面、計算量がO(n^2)と非効率で大きなデータセットには不向きです。

クイックソート（Quick Sort）

クイックソートは、バブルソートよりも効率的なソートアルゴリズムで、平均計算時間がO(n log n)です。

このアルゴリズムは「分割統治法」に基づき、リストを小さな部分に分割してソートするという手法を取ります。

実装例: VBScriptでのクイックソート

Function QuickSort(arr)
    If UBound(arr) <= 0 Then
        QuickSort = arr
        Exit Function
    End If

    Dim pivot, leftArray, rightArray, resultArray
    pivot = arr(UBound(arr)) ' 最後の要素をピボットとする
    ReDim leftArray(-1)
    ReDim rightArray(-1)

    For i = 0 To UBound(arr) - 1
        If arr(i) < pivot Then
            ReDim Preserve leftArray(UBound(leftArray) + 1)
            leftArray(UBound(leftArray)) = arr(i)
        Else
            ReDim Preserve rightArray(UBound(rightArray) + 1)
            rightArray(UBound(rightArray)) = arr(i)
        End If
    Next

    leftArray = QuickSort(leftArray)
    rightArray = QuickSort(rightArray)

    resultArray = ConcatenateArrays(leftArray, Array(pivot), rightArray)
    QuickSort = resultArray
End Function

Function ConcatenateArrays(arr1, arr2, arr3)
    Dim i, resultArray
    ReDim resultArray(UBound(arr1) + UBound(arr2) + UBound(arr3) + 2)

    ' 配列の結合
    For i = 0 To UBound(arr1)
        resultArray(i) = arr1(i)
    Next
    For i = 0 To UBound(arr2)
        resultArray(UBound(arr1) + 1 + i) = arr2(i)
    Next
    For i = 0 To UBound(arr3)
        resultArray(UBound(arr1) + UBound(arr2) + 2 + i) = arr3(i)
    Next

    ConcatenateArrays = resultArray
End Function

' 使用例
Dim myArray
myArray = Array(34, 7, 23, 32, 5, 62)
myArray = QuickSort(myArray)

' 結果を表示
For i = 0 To UBound(myArray)
    WScript.Echo myArray(i)
Next

このクイックソートアルゴリズムでは、ピボット（基準となる値）を使い、リストを2つに分け、再帰的にソートを行います。

結果的に、ソートの効率が向上します。ConcatenateArrays関数を用いて、分割したリストを結合し、最終的なソート結果を得ます。

フィボナッチ数列（Fibonacci Sequence）

フィボナッチ数列は、初項から始まり、次の数が前の2つの数の和である数列です。

この数列は数学的に重要なアルゴリズムの1つで、多くの分野で応用されています。

実装例: VBScriptでのフィボナッチ数列

Function Fibonacci(n)
    If n = 0 Then
        Fibonacci = 0
    ElseIf n = 1 Then
        Fibonacci = 1
    Else
        Fibonacci = Fibonacci(n - 1) + Fibonacci(n - 2)
    End If
End Function

' 使用例
Dim i
For i = 0 To 10
    WScript.Echo "Fibonacci(" & i & ") = " & Fibonacci(i)
Next

このフィボナッチ数列は、再帰関数を使って実装されています。

Fibonacci関数は、引数nに対して0と1の場合を特別に処理し、それ以外は再帰的に前の2つのフィボナッチ数を足し合わせて計算します。

検索アルゴリズム

検索アルゴリズムは、データから特定の値を見つけるための方法です。

ここでは、基本的な線形探索と効率的な二分探索を紹介します。

線形探索（Linear Search）

線形探索は、リストの先頭から順に要素をチェックしていく方法です。

シンプルですが、データ量が多くなると非効率です。

線形探索の実装例

Function LinearSearch(arr, target)
    Dim i
    For i = 0 To UBound(arr)
        If arr(i) = target Then
            LinearSearch = i ' 見つかった場合、そのインデックスを返す
            Exit Function
        End If
    Next
    LinearSearch = -1 ' 見つからなかった場合は -1 を返す
End Function

線形探索の計算量はO(n)です。データ量が多い場合、他のアルゴリズムの方が効率的です。

二分探索（Binary Search）

二分探索は、ソートされたリストに対して行う効率的な検索方法です。

リストを半分に分割し、中央の値と目的の値を比較することで、探索範囲を絞ります。

二分探索の実装例

Function BinarySearch(arr, target)
    Dim low, high, mid
    low = 0
    high = UBound(arr)

    While low <= high
        mid = Int((low + high) / 2)
        If arr(mid) = target Then
            BinarySearch = mid ' 見つかった場合、そのインデックスを返す
            Exit Function
        ElseIf arr(mid) < target Then
            low = mid + 1
        Else
            high = mid - 1
        End If
    Wend

    BinarySearch = -1 ' 見つからなかった場合は -1 を返す
End Function

二分探索の計算量はO(log n)で、大きなデータセットでも高速です。

ただし、リストがソートされている必要があります。

データ構造

データ構造は、データを効率的に扱うための方法です。

ここでは、VBScriptで実装可能なスタック、キュー、リンクリストについて解説します。

スタック（Stack）

スタックは、LIFO（Last In, First Out）方式のデータ構造です。最後に追加されたデータが最初に取り出されます。

スタックの実装例

Class Stack
    Private arr

    Private Sub Class_Initialize()
        ReDim arr(-1)
    End Sub

    Public Sub Push(value)
        ReDim Preserve arr(UBound(arr) + 1)
        arr(UBound(arr)) = value
    End Sub

    Public Function Pop()
        If UBound(arr) >= 0 Then
            Pop = arr(UBound(arr))
            ReDim Preserve arr(UBound(arr) - 1)
        Else
            Pop = Null
        End If
    End Function

    Public Function Peek()
        If UBound(arr) >= 0 Then
            Peek = arr(UBound(arr))
        Else
            Peek = Null
        End If
    End Function
End Class

' 使用例
Dim myStack
Set myStack = New Stack
myStack.Push 10
myStack.Push 20
WScript.Echo myStack.Pop ' 20
WScript.Echo myStack.Peek ' 10

キュー（Queue）

キューは、FIFO（First In, First Out）方式のデータ構造で、先に追加されたデータが最初に取り出されます。

キューの実装例

Class Queue
    Private arr

    Private Sub Class_Initialize()
        ReDim arr(-1)
    End Sub

    Public Sub Enqueue(value)
        ReDim Preserve arr(UBound(arr) + 1)
        arr(UBound(arr)) = value
    End Sub

    Public Function Dequeue()
        If UBound(arr) >= 0 Then
            Dequeue = arr(0)
            Dim i
            For i = 1 To UBound(arr)
                arr(i - 1) = arr(i)
            Next
            ReDim Preserve arr(UBound(arr) - 1)
        Else
            Dequeue = Null
        End If
    End Function
End Class

' 使用例
Dim myQueue
Set myQueue = New Queue
myQueue.Enqueue 10
myQueue.Enqueue 20
WScript.Echo myQueue.Dequeue ' 10
WScript.Echo myQueue.Dequeue ' 20

リンクリスト（Linked List）

リンクリストは、各要素が次の要素への参照を持つデータ構造です。動的にサイズを変更でき、挿入や削除が容易です。

リンクリストの実装例

Class Node
    Public data
    Public nextNode
End Class

Class LinkedList
    Private head

    Public Sub Add(value)
        Dim newNode
        Set newNode = New Node
        newNode.data = value
        newNode.nextNode = head
        head = newNode
    End Sub

    Public Function Remove()
        If Not head Is Nothing Then
            Remove = head.data
            Set head = head.nextNode
        Else
            Remove = Null
        End If
    End Function

    Public Function Display()
        Dim current
        Set current = head
        While Not current Is Nothing
            WScript.Echo current.data
            Set current = current.nextNode
        Wend
    End Function
End Class

' 使用例
Dim myList
Set myList = New LinkedList
myList.Add 10
myList.Add 20
myList.Display ' 20, 10
WScript.Echo myList.Remove ' 20

総まとめ

VBScriptを使って、ソート、検索、そしてデータ構造の基礎を学びました。

これらのアルゴリズムやデータ構造は、プログラムの効率を大幅に向上させるため、習得しておくべき重要な技術です。

特に、ソートアルゴリズムや再帰的なアルゴリズムは多くの場面で活用されるため、これらの実装を通じてスキルアップを図りましょう。

演習問題

この記事の内容を基にした演習問題を通じて、実際に手を動かしながら学習を進めましょう。

問題1: バブルソートの実装を応用して、昇順ではなく降順に並べ替えるプログラムを作成してください。

演習1：解答例

バブルソート降順版

Sub BubbleSortDescending(arr)
    Dim i, j, temp
    For i = UBound(arr) To 1 Step -1
        For j = 0 To i - 1
            If arr(j) < arr(j + 1) Then
                ' 要素の交換（降順）
                temp = arr(j)
                arr(j) = arr(j + 1)
                arr(j + 1) = temp
            End If
        Next
    Next
End Sub

問題2: クイックソートのピボットを常に中央の要素に変更して、ソート結果が正しく得られることを確認してください。

演習2：解答例

クイックソート（中央ピボット版）

Function QuickSort(arr)
    If UBound(arr) <= 0 Then
        QuickSort = arr
        Exit Function
    End If

    Dim pivotIndex, pivot, leftArray, rightArray
    pivotIndex = Int(UBound(arr) / 2)
    pivot = arr(pivotIndex)
    ReDim leftArray(-1)
    ReDim rightArray(-1)

    For i = 0 To UBound(arr)
        If i <> pivotIndex Then
            If arr(i) < pivot Then
                ReDim Preserve leftArray(UBound(leftArray) + 1)
                leftArray(UBound(leftArray)) = arr(i)
            Else
                ReDim Preserve rightArray(UBound(rightArray) + 1)
                rightArray(UBound(rightArray)) = arr(i)
            End If
        End If
    Next

    leftArray = QuickSort(leftArray)
    rightArray = QuickSort(rightArray)

    QuickSort = ConcatenateArrays(leftArray, Array(pivot), rightArray)
End Function

問題3: フィボナッチ数列の計算において、再帰を使わずにループを使って計算する方法を考えて実装してください。

演習3：解答例

フィボナッチ数列（ループ版）

Function FibonacciLoop(n)
    Dim a, b, temp, i
    a = 0
    b = 1
    If n = 0 Then
        FibonacciLoop = 0
    ElseIf n = 1 Then
        FibonacciLoop = 1
    Else
        For i = 2 To n
            temp = a + b
            a = b
            b = temp
        Next
        FibonacciLoop = b
    End If
End Function