2.2-1 Θ(n3) 2.2-2 def selection_sort(A): n = len(A) for i in range(n-1): minimum = i for j in range(i+1, n): if A[minimum] > A[j]: minimum = j A[i], A[minimum] = A[minimum], A[i] ループ不変式は、「第3-8行のforループが開始されるとき、部分配…

2.1-1 2つの41の順序関係が維持されている(安定である)ことに注目するぐらい。 2.1-2 def insertion_sort(A): for j in range(1, len(A)): key = A[j] i = j-1 while i >= 0 and A[i] < key: A[i+1] = A[i] i -= 1 A[i+1] = key 2.1-3 def linear_search(A, …