// Strategy Pattern Example

// ソートアルゴリズムのStrategyインターフェース
interface SortStrategy {
    fun sort(numbers: IntArray): IntArray
}

// バブルソートアルゴリズム
class BubbleSortStrategy : SortStrategy {
    override fun sort(numbers: IntArray): IntArray {
        val sortedArray = numbers.clone()
        val n = sortedArray.size
        for (i in 0 until n) {
            for (j in 0 until n - i - 1) {
                if (sortedArray[j] > sortedArray[j + 1]) {
                    val temp = sortedArray[j]
                    sortedArray[j] = sortedArray[j + 1]
                    sortedArray[j + 1] = temp
                }
            }
        }
        return sortedArray
    }
}

// クイックソートアルゴリズム
class QuickSortStrategy : SortStrategy {
    override fun sort(numbers: IntArray): IntArray {
        if (numbers.size <= 1) return numbers

        val pivot = numbers[numbers.size / 2]
        val equal = numbers.filter { it == pivot }.toIntArray()
        val less = numbers.filter { it < pivot }.toIntArray()
        val greater = numbers.filter { it > pivot }.toIntArray()

        return sort(less) + equal + sort(greater)
    }
}

// ソートを実行するコンテキストクラス
class SortContext(private val strategy: SortStrategy) {
    fun executeSort(numbers: IntArray): IntArray {
        return strategy.sort(numbers)
    }
}

fun main() {
    val numbers = intArrayOf(9, 3, 7, 1, 5)

    // バブルソートを用いたソート
    val bubbleSortStrategy = BubbleSortStrategy()
    val bubbleSortContext = SortContext(bubbleSortStrategy)
    val sortedWithBubbleSort = bubbleSortContext.executeSort(numbers)
    println("バブルソートの結果: ${sortedWithBubbleSort.joinToString()}")

    // クイックソートを用いたソート
    val quickSortStrategy = QuickSortStrategy()
    val quickSortContext = SortContext(quickSortStrategy)
    val sortedWithQuickSort = quickSortContext.executeSort(numbers)
    println("クイックソートの結果: ${sortedWithQuickSort.joinToString()}")
}
