はじめに
こんにちは。Yuinaです!
今日は配列の並べ替え問題を作ってみました。
ぜひぜひ、挑戦してみてください✨
問題
バブルソート
def bubble_sort_ascending(queue_urgency):
n = len(queue_urgency)
for i in range(n - 1):
swapped = False
for j in range(n - 1, i, -1):
if queue_urgency[j - 1] > queue_urgency[j]:
temp = queue_urgency[j - 1] ーー A
queue_urgency[j - 1] = queue_urgency[j]
queue_urgency[j] = temp
swapped = True ーー B
if not swapped:
break
return queue_urgency
initial_queue = [3, 1, 5, 2]
initial_queue_2 = [1, 3, 2, 4, 2, 2, 2]
result1 = bubble_sort_ascending(initial_queue)
result2 = bubble_sort_ascending(initial_queue_2)
print(result1)
print(result2)
隣り合う要素同士を比較し、全体の並べ替えを行います。
設問1.initial_queue = [3, 1, 5, 2]とinitial_queue_2 = [1, 3, 2, 4, 2, 2, 2]の時、Bの1回目終了時点での実行結果をそれぞれ教えてください。
回答.initial_queue : [1,3,2,5] initial_queue_2 :[1,2,3,2,4,2,2]
設問2.initial_queue = [3, 1, 5, 2]の時、”–A”は何回実行されますか?
回答.3回
挿入ソート
def insert_sort(items_list):
n = len(items_list)
for i in range(1,n):
current_item = items_list[i]
current_price = current_item[0]
j = i
while j > 0 and items_list[j - 1][0] > (a):
items_list[j] = items_list[j - 1]
(b) -= 1
items_list[j] = current_item
return items_list
def input_new_items(existing_items):
new_items_list = existing_items[:]
while True:
item_name = input("商品名：").strip()
if item_name.lower() == 'end':
break
while True:
try:
price_str = input(f"{item_name}の価格を入力して")
price = int(price_str)
if price <= 0:
print("正の整数を入力してね")
continue
break
except ValueError:
print("無効な入力です。")
new_items_list.append((price,(c)))
print(f"[{item_name}: ¥{price}]をリストに追加しました。\n")
return new_items_list
if __name__ == '__main__':
items = [(550,"マグカップ"),(1200,"ワイヤレスマウス"),(300,"鉛筆"),(800,"ノート"),(250,"消しゴム")]
items_to_sort = input_new_items(items)
sorted_items = insert_sort(items_to_sort)
print("===================================")
for rank, (price,name) in enumerate(sorted_items,1):
print(f"順位{rank}:商品名{name},価格:¥{price}")
このプログラムでは既存の商品リストに新商品を挿入します。
設問1.(a),(b),(c)に当てはまる値を教えてください。
回答.(a)current_price,(b) j,(c)item_name
設問2.(300,”ものさし”)を追加すると、どのように表示されますか?
回答.
順位1:商品名消しゴム,価格:¥250
順位2:商品名鉛筆,価格:¥300
順位3:商品名ものさし,価格:¥300
順位4:商品名マグカップ,価格:¥550
順位5:商品名ノート,価格:¥800
順位6:商品名ワイヤレスマウス,価格:¥1200
マージソート
def merge(left_list, right_list):
merged_list = []
i = 0 # left_list のインデックス
j = 0 # right_list のインデックス
while i < len(left_list) and j < len(right_list):
if left_list[i] <= right_list[j]:
merged_list.append(left_list[i])
i += 1
else:
merged_list.append(right_list[j])
j += 1
while i < len(left_list): -- A
merged_list.append(left_list[i])
i += 1
while j < len(right_list): -- B
merged_list.append(right_list[j])
j += 1
return merged_list
def merge_sort(data_list):
if len(data_list) <= 1:
return data_list
mid = len(data_list) // 2
left_half = data_list[:mid]
right_half = data_list[mid:]
# 2. 再帰的なソート
left_sorted = merge_sort(left_half)
right_sorted = merge_sort(right_half)
return merge(left_sorted, right_sorted)
if __name__ == '__main__':
random_data = [80, 20, 60, 10, 50, 40, 70, 30]
sorted_data = merge_sort(random_data)
設問1.merge_sort関数が完了した時点で、right_halfとleft_halfに含まれるものを教えてください。
回答.left_halfに含まれるもの[80,60,50,70],right_halfに含まれるもの[20,10,40,30]
設問2.AとBの実行回数を教えてください。
回答.A:4回,B:0回
クイックソート
def partitoin(A,low,high):
pivot_value = A[high][0]
i = low - 1
for j in range(low,high):
if A[j][0] <= pivot_value: -- A
i += 1
A[(a)], A[(b)] = A[j], A[i]
A[i + 1], A[high] = A[high], A[i + 1] -- B
return i + 1
def QuickSort(A,low,high):
if low < high:
pivot_pos = partitoin(A,low,high)
QuickSort(A,low,pivot_pos - 1) -- C
QuickSort(A,pivot_pos + 1,high) -- D
if __name__ == '__main__':
initial_numbers = [(5,"A"),(1,"B"),(8,"C"),(6,"E"),(2,"F")]
N = len(initial_numbers)
QuickSort(initial_numbers,0,N - 1)
print("--- 最終的な座席配置（経験年数昇順） ---")
for exp,name in initial_numbers:
print(f"経験年数:{exp}年,社員:{name}")
設問1. (a),(b)に当てはまる値を教えてください。
回答. (a)i(b)j
設問2. 最初にAがTrueになるときの経験年数(j)の値はなんですか。また、B実行後の配列の状態はどうなりますか。
回答. 経験年数(j) : 1, B実行後のの配列の状態:[(1,”B”),(5,”A”),(8,”C”),(6,”E”),(2,”F”)]
設問3.1回目のCとDのlow,highには何が入りますか。
回答.C:(low=0,high=0) D:(low=2,high=4)
設問4.2回目のDには何が入りますか。
回答.D:(low=3,high=4)
ヒープソート
def heapify(arr, n, i):
largest = i # 最大の要素のインデックスを初期化
left = 2 * (a) # 左の子のインデックス
right = 2 * (b) # 右の子のインデックス
if left < n and arr[i] < arr[left]:
largest = left # 最大の要素にする
if right < n and arr[i] < arr[right]:
largest = right # 最大の要素にする
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # 要素交換
heapify(arr,n,largest)
def heap_sort(arr):
n = len(arr)
for i in range((c),-1,-1):
heapify(arr,n,i)
for i in range((d),0,-1): --A
arr[i],arr[0] = arr[0],arr[i]
heapify(arr,i,0)
return arr
my_list = [12, 11, 13, 5, 6, 7]
sorted_list = heap_sort(my_list)
print(f"ソート前の配列: {my_list}")
print(f"ソート後の配列: {sorted_list}")
設問1.(a),(b),(c),(d)に当てはまる値を教えてください。
回答. (a)i + 1 (b)i + 2 (c)n // 2 – 1 (d)n – 1
設問2.Aの部分はどのような役割がありますか?
回答.ヒープの再構築。最大値が取り出された後のヒープを修復し、次の最大値を準備している。
まとめ
答え合わせはいかがでしたか??👀✨
もし時間がかかっても、それはあなたがアルゴリズムの内部構造を深く考えていた証拠です。
ソートアルゴリズムの真価は、ただ暗記することではなく、「なぜその手順で正しく並び替えられるのか」を理解することにあります。
ぜひ他のアルゴリズム問題にも挑戦し、知識を血肉に変えていきましょう。
