def selection_sort(arr):
  for i in range(len(arr)):
       min_index = i
       for j in range(i + 1, len(arr)):
          if arr[j] < arr[min_index]:
               min_index = j
       arr[i], arr[min_index] = arr[min_index], arr[i]
     return arr
 
def insertion_sort(arr):
   for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
           arr[j + 1] = arr[j]
           j -= 1
        arr[j + 1] = key
     return arr
 
 def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
       for j in range(0, n - i - 1):
          if arr[j] > arr[j + 1]:
              arr[j], arr[j + 1] = arr[j + 1], arr[j]
     return arr
 
def merge_sort(arr):
  if len(arr) > 1:
      mid = len(arr) // 2
      L = arr[:mid]
      R = arr[mid:]

      merge_sort(L)
      merge_sort(R)

      i = j = k = 0

      while i < len(L) and j < len(R):
        if L[i] < R[j]:
            arr[k] = L[i]
            i += 1
        else:
           arr[k] = R[j]
           j += 1
         k += 1

      while i < len(L):
         arr[k] = L[i]
         i += 1
         k += 1

    while j < len(R):
       arr[k] = R[j]
       j += 1
       k += 1
  return arr

def print_menu():
   print("กรุณาเลือกวิธีการเรียงลำดับตัวเลข")
   print("1. Selection Sort")
   print("2. Insertion Sort")
   print("3. Bubble Sort")
   print("4. Merge Sort")
   print("0. Exit")

 arr = []
 print("กรุณาป้อนตัวเลข 8 ตัว:")
 for i in range(8):
     num = int(input(f"ป้อนตัวเลขที่ {i+1}: "))
     arr.append(num)
 choice = -1 # กำหนดค่าเริ่มต้นของ choice เพื่อให้เข้าไปในลูป while ได้

 while choice != 0:
   print_menu()
   choice = int(input("เลือกเมนู: "))

   if choice == 1:
       selection_sort(arr)
       print("ผลลัพธ์จากการใช้ Selection Sort:", arr)
   elif choice == 2:
       insertion_sort(arr)
       print("ผลลัพธ์จากการใช้ Insertion Sort:", arr)
   elif choice == 3:
       bubble_sort(arr)
       print("ผลลัพธ์จากการใช้ Bubble Sort:", arr)
   elif choice == 4:
       merge_sort(arr)
       print("ผลลัพธ์จากการใช้ Merge Sort:", arr)
   elif choice == 0:
       print("ออกจากโปรแกรม")
   else:
       print("เลือกเมนูไม่ถูกต้อง")