def linear_search(L, e):
found = False
for i in range(len(L)):
if e == L[i]:
found = True
return found
def search(L, e):
for i in range(len(L)):
if L[i] == e:
return True
if L[i] > e:
return False
return False
def bisect_search1(L, e):
if L == []:
return False
elif len(L) == 1:
return L[0] == e
else:
half = len(L) // 2
if L[half] > e:
return bisect_search1(L[:half], e)
else:
return bisect_search1(L[half:], e)
def bisect_search2(L, e):
def bisect_search_helper(L, e, low, high):
if high == low:
return L[low] == e
mid = (low + high) // 2
if L[mid] == e:
return True
elif L[mid] > e:
if low == mid:
return False
else:
return bisect_search_helper(L, e, low, mid - 1)
else:
return bisect_search_helper(L, e, mid + 1, high)
if len(L) == 0:
return False
else:
return bisect_search_helper(L, e, 0, len(L) - 1)
testList = [1, 2, 3, 5, 7, 9, 18, 27]
bisect_search1(testList, 9)
True
bisect_search1(testList, 15)
False
bisect_search2(testList, 9)
True
bisect_search2(testList, 15)
False
def bubble_sort(L):
swap = False
while not swap:
print(L)
swap = True
for j in range(1, len(L)):
if L[j - 1] > L[j]:
swap = False
temp = L[j]
L[j] = L[j-1]
L[j-1] = temp
test = [1, 5, 3, 8, 4, 9, 6, 2]
bubble_sort(test)
[1, 5, 3, 8, 4, 9, 6, 2] [1, 3, 5, 4, 8, 6, 2, 9] [1, 3, 4, 5, 6, 2, 8, 9] [1, 3, 4, 5, 2, 6, 8, 9] [1, 3, 4, 2, 5, 6, 8, 9] [1, 3, 2, 4, 5, 6, 8, 9] [1, 2, 3, 4, 5, 6, 8, 9]
def selection_sort(L):
suffixSt = 0
while suffixSt != len(L):
print(L)
for i in range(suffixSt, len(L)):
if L[i] < L[suffixSt]:
L[suffixSt], L[i] = L[i], L[suffixSt]
suffixSt += 1
test = [1, 5, 3, 8, 4, 9, 6, 2]
selection_sort(test)
[1, 5, 3, 8, 4, 9, 6, 2] [1, 5, 3, 8, 4, 9, 6, 2] [1, 2, 5, 8, 4, 9, 6, 3] [1, 2, 3, 8, 5, 9, 6, 4] [1, 2, 3, 4, 8, 9, 6, 5] [1, 2, 3, 4, 5, 9, 8, 6] [1, 2, 3, 4, 5, 6, 9, 8] [1, 2, 3, 4, 5, 6, 8, 9]
def merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
while (i < len(left)):
result.append(left[i])
i += 1
while (j < len(right)):
result.append(right[j])
j += 1
print('merge ', result)
return result
def merge_sort(L):
print(L)
if len(L) < 2:
return L[:]
else:
middle = len(L) // 2
left = merge_sort(L[:middle])
right = merge_sort(L[middle:])
return merge(left, right)
test = [1, 5, 3, 8, 4, 9, 6, 2]
merge_sort(test)
[1, 5, 3, 8, 4, 9, 6, 2] [1, 5, 3, 8] [1, 5] [1] [5] merge [1, 5] [3, 8] [3] [8] merge [3, 8] merge [1, 3, 5, 8] [4, 9, 6, 2] [4, 9] [4] [9] merge [4, 9] [6, 2] [6] [2] merge [2, 6] merge [2, 4, 6, 9] merge [1, 2, 3, 4, 5, 6, 8, 9]
[1, 2, 3, 4, 5, 6, 8, 9]