# ============================================
# ソートアルゴリズムのサンプルコード
# ============================================

# ============================================
# 1. バブルソート（Bubble Sort）
# ============================================
# 最もシンプルで理解しやすいソートアルゴリズム
# 時間計算量: O(n²)

A ← [ 7, 3, 9, 4, 6 ]
N ← length(A)

for (i ← 1 to N - 1)
  for (j ← 1 to N - i)
    if (A[j] > A[j + 1])
      TEMP ← A[j]
      A[j] ← A[j + 1]
      A[j + 1] ← TEMP
    endif
  endfor
endfor

for (k ← 1 to N)
  print A[k]
endfor

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

A ← [ 7, 3, 9, 4, 6 ]
N ← length(A)

for (i ← 1 to N - 1)
  MIN_POS ← i
  for (j ← i + 1 to N)
    if (A[j] < A[MIN_POS])
      MIN_POS ← j
    endif
  endfor
  if (MIN_POS != i)
    TEMP ← A[i]
    A[i] ← A[MIN_POS]
    A[MIN_POS] ← TEMP
  endif
endfor

for (k ← 1 to N)
  print A[k]
endfor

# ============================================
# 3. 挿入ソート（Insertion Sort）
# ============================================
# カードを並べ替えるように、要素を適切な位置に挿入
# 時間計算量: O(n²) だが、実用的には高速

A ← [ 7, 3, 9, 4, 6 ]
N ← length(A)

for (i ← 2 to N)
  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 (k ← 1 to N)
  print A[k]
endfor

# ============================================
# 4. クイックソート（Quick Sort）- Lomuto方式
# ============================================
# 分割統治法を使った高速なソート
# 時間計算量: 平均 O(n log n)、最悪 O(n²)
# 注意: このアプリでは動作しますが、無限ループの可能性があるため注意が必要です

A ← [ 7, 3, 9, 4, 6 ]
N ← length(A)

call QuickSort(1, N)

for (k ← 1 to N)
  print A[k]
endfor

procedure QuickSort(left, right)
  if (left >= right)
    return
  endif

  # Lomuto partition scheme
  pivot ← A[right]
  i ← left

  for (j ← left to right - 1)
    if (A[j] <= pivot)
      SWAP_TEMP ← A[i]
      A[i] ← A[j]
      A[j] ← SWAP_TEMP
      i ← i + 1
    endif
  endfor

  SWAP_TEMP ← A[i]
  A[i] ← A[right]
  A[right] ← SWAP_TEMP

  # 再帰呼び出し（境界チェック付き）
  if (i - 1 > left)
    call QuickSort(left, i - 1)
  endif
  if (i + 1 < right)
    call QuickSort(i + 1, right)
  endif
endprocedure

# ============================================
# 5. マージソート（Merge Sort）
# ============================================
# 分割統治法を使った安定ソート
# 時間計算量: O(n log n)
# 注意: このアプリでは動作しますが、作業用配列が必要です

A ← [ 7, 3, 9, 4, 6 ]
N ← length(A)

# 作業用配列を初期化（配列は動的に作成される）
TEMP ← [ 0, 0, 0, 0, 0, 0 ]

call MergeSort(1, N)

for (k ← 1 to N)
  print A[k]
endfor

procedure MergeSort(left, right)
  # ベースケース: 要素が1つ以下の場合は終了
  if (left >= right)
    return
  endif

  # mid の計算（整数除算で中央値を求める）
  # 例: left=1, right=5 → mid=3
  #     left=1, right=4 → mid=2
  mid ← (left + right) // 2
  
  # 左半分をソート（left < mid が保証されている）
  call MergeSort(left, mid)
  
  # 右半分をソート（mid + 1 <= right が保証されている）
  call MergeSort(mid + 1, right)
  
  # マージ処理
  call Merge(left, mid, right)
endprocedure

procedure Merge(left, mid, right)
  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 to right)
    A[m] ← TEMP[m]
  endfor
endprocedure

# ============================================
# 6. 降順ソート（Selection Sort使用）
# ============================================
# 大きい順に並べ替える

A ← [ 7, 3, 9, 4, 6 ]
N ← length(A)

for (i ← 1 to N - 1)
  MAX_POS ← i
  for (j ← i + 1 to N)
    if (A[j] > A[MAX_POS])
      MAX_POS ← j
    endif
  endfor
  if (MAX_POS != i)
    TEMP ← A[i]
    A[i] ← A[MAX_POS]
    A[MAX_POS] ← TEMP
  endif
endfor

for (k ← 1 to N)
  print A[k]
endfor