// ============================================
// ソートアルゴリズムのサンプル（科目B記法）
// 各節をコピーしてコード欄へ貼って実行してください
// ============================================

// ============================================
// 1. バブルソート（Bubble Sort）
// ============================================
// 隣り合う要素を比較して入れ替える
// 時間計算量: O(n²)

整数型の配列: A ← { 7, 3, 9, 4, 6 }
整数型: N, i, j, temp
N ← Aの要素数

for (i を 1 から N − 1 まで 1 ずつ増やす)
    for (j を 1 から N − i まで 1 ずつ増やす)
        if (A[j] ＞ A[j ＋ 1])
            temp ← A[j]
            A[j] ← A[j ＋ 1]
            A[j ＋ 1] ← temp
        endif
    endfor
endfor

for (i を 1 から N まで 1 ずつ増やす)
    A[i] を出力
endfor

// ============================================
// 2. 選択ソート（Selection Sort）
// ============================================
// 最小値を見つけて先頭へ移す
// 時間計算量: O(n²)

整数型の配列: A ← { 7, 3, 9, 4, 6 }
整数型: N, i, j, minPos, temp
N ← Aの要素数

for (i を 1 から N − 1 まで 1 ずつ増やす)
    minPos ← i
    for (j を i ＋ 1 から N まで 1 ずつ増やす)
        if (A[j] ＜ A[minPos])
            minPos ← j
        endif
    endfor
    if (minPos ≠ i)
        temp ← A[i]
        A[i] ← A[minPos]
        A[minPos] ← temp
    endif
endfor

for (i を 1 から N まで 1 ずつ増やす)
    A[i] を出力
endfor

// ============================================
// 3. 挿入ソート（Insertion Sort）
// ============================================
// 未整列の先頭を、整列済みの適切な位置へ挿入する
// 時間計算量: O(n²)

整数型の配列: A ← { 7, 3, 9, 4, 6 }
整数型: N, i, j, key
N ← Aの要素数

for (i を 2 から N まで 1 ずつ増やす)
    key ← A[i]
    j ← i − 1
    while ((j ≧ 1) and (A[j] ＞ key))
        A[j ＋ 1] ← A[j]
        j ← j − 1
    endwhile
    A[j ＋ 1] ← key
endfor

for (i を 1 から N まで 1 ずつ増やす)
    A[i] を出力
endfor

// ============================================
// 4. クイックソート（Quick Sort）
// ============================================
// 分割統治。平均 O(n log n)、最悪 O(n²)

整数型の配列: A ← { 7, 3, 9, 4, 6 }
整数型: N
N ← Aの要素数
QuickSort(1, N)
for (i を 1 から N まで 1 ずつ増やす)
    A[i] を出力
endfor

○QuickSort(整数型: left, 整数型: right)
    整数型: pivot, i, j, swapTemp
    if (left ≧ right)
        return
    endif
    pivot ← A[right]
    i ← left
    for (j を left から right − 1 まで 1 ずつ増やす)
        if (A[j] ≦ pivot)
            swapTemp ← A[i]
            A[i] ← A[j]
            A[j] ← swapTemp
            i ← i ＋ 1
        endif
    endfor
    swapTemp ← A[i]
    A[i] ← A[right]
    A[right] ← swapTemp
    if (i − 1 ＞ left)
        QuickSort(left, i − 1)
    endif
    if (i ＋ 1 ＜ right)
        QuickSort(i ＋ 1, right)
    endif

// ============================================
// 5. マージソート（Merge Sort）
// ============================================
// 分割統治の安定ソート。時間計算量 O(n log n)

整数型の配列: A ← { 7, 3, 9, 4, 6 }
整数型の配列: temp ← { 0, 0, 0, 0, 0 }
整数型: N
N ← Aの要素数
MergeSort(1, N)
for (i を 1 から N まで 1 ずつ増やす)
    A[i] を出力
endfor

○MergeSort(整数型: left, 整数型: right)
    整数型: mid
    if (left ≧ right)
        return
    endif
    mid ← (left ＋ right) ÷ 2
    MergeSort(left, mid)
    MergeSort(mid ＋ 1, right)
    Merge(left, mid, right)

○Merge(整数型: left, 整数型: mid, 整数型: right)
    整数型: i, j, k, m
    i ← left
    j ← mid ＋ 1
    k ← left
    while ((i ≦ mid) and (j ≦ right))
        if (A[i] ≦ A[j])
            temp[k] ← A[i]
            i ← i ＋ 1
        else
            temp[k] ← A[j]
            j ← j ＋ 1
        endif
        k ← k ＋ 1
    endwhile
    while (i ≦ mid)
        temp[k] ← A[i]
        i ← i ＋ 1
        k ← k ＋ 1
    endwhile
    while (j ≦ right)
        temp[k] ← A[j]
        j ← j ＋ 1
        k ← k ＋ 1
    endwhile
    for (m を left から right まで 1 ずつ増やす)
        A[m] ← temp[m]
    endfor

// ============================================
// 6. 降順ソート（選択ソート）
// ============================================
// 大きい順に並べ替える

整数型の配列: A ← { 7, 3, 9, 4, 6 }
整数型: N, i, j, maxPos, temp
N ← Aの要素数

for (i を 1 から N − 1 まで 1 ずつ増やす)
    maxPos ← i
    for (j を i ＋ 1 から N まで 1 ずつ増やす)
        if (A[j] ＞ A[maxPos])
            maxPos ← j
        endif
    endfor
    if (maxPos ≠ i)
        temp ← A[i]
        A[i] ← A[maxPos]
        A[maxPos] ← temp
    endif
endfor

for (i を 1 から N まで 1 ずつ増やす)
    A[i] を出力
endfor