# Tìm kiếm và sắp xếp¶

## Tìm kiếm¶

### Tìm kiếm tuần tự cho danh sách chưa được sắp xếp¶

In :
def linear_search(L, e):
found = False
for i in range(len(L)):
if e == L[i]:
found = True
return found


### Tìm kiếm tuần tự cho danh sách đã được sắp xếp¶

In [ ]:
def search(L, e):
for i in range(len(L)):
if L[i] == e:
return True
if L[i] > e:
return False
return False


### Tìm kiếm nhị phân 1¶

In :
def bisect_search1(L, e):
if L == []:
return False
elif len(L) == 1:
return L == e
else:
half = len(L) // 2
if L[half] > e:
return bisect_search1(L[:half], e)
else:
return bisect_search1(L[half:], e)


### Tìm kiếm nhị phân 2¶

In :
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)

In :
testList = [1, 2, 3, 5, 7, 9, 18, 27]

In :
bisect_search1(testList, 9)

Out:
True
In :
bisect_search1(testList, 15)

Out:
False
In :
bisect_search2(testList, 9)

Out:
True
In :
bisect_search2(testList, 15)

Out:
False

## Sắp xếp¶

### Sắp xếp nổi bọt - Bubble Sort¶

In :
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


In :
test = [1, 5, 3, 8, 4, 9, 6, 2]

In :
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]


### Selection Sort¶

In :
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

In :
test = [1, 5, 3, 8, 4, 9, 6, 2]

In :
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]


### Merge Sort¶

In :
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)

In :
test = [1, 5, 3, 8, 4, 9, 6, 2]

In :
merge_sort(test)

[1, 5, 3, 8, 4, 9, 6, 2]
[1, 5, 3, 8]
[1, 5]


merge  [1, 5]
[3, 8]


merge  [3, 8]
merge  [1, 3, 5, 8]
[4, 9, 6, 2]
[4, 9]


merge  [4, 9]
[6, 2]


merge  [2, 6]
merge  [2, 4, 6, 9]
merge  [1, 2, 3, 4, 5, 6, 8, 9]

Out:
[1, 2, 3, 4, 5, 6, 8, 9]