# 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 [1]:
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 [8]:
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)


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

In [5]:
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 [6]:
testList = [1, 2, 3, 5, 7, 9, 18, 27]

In [9]:
bisect_search1(testList, 9)

Out[9]:
True
In [10]:
bisect_search1(testList, 15)

Out[10]:
False
In [11]:
bisect_search2(testList, 9)

Out[11]:
True
In [12]:
bisect_search2(testList, 15)

Out[12]:
False

## Sắp xếp¶

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

In [23]:
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 [24]:
test = [1, 5, 3, 8, 4, 9, 6, 2]

In [25]:
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 [29]:
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 [31]:
test = [1, 5, 3, 8, 4, 9, 6, 2]

In [32]:
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 [45]:
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 [46]:
test = [1, 5, 3, 8, 4, 9, 6, 2]

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

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