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]