#!/usr/bin/env python
# coding: utf-8

# # 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)


# In[10]:


bisect_search1(testList, 15)


# In[11]:


bisect_search2(testList, 9)


# In[12]:


bisect_search2(testList, 15)


# ## 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)


# ### 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)


# ### 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)


# - - -
# [Trước: Lập trình Hướng đối tượng](http://nbviewer.jupyter.org/github/manleviet/introCSusingPython/blob/master/9%20-%20L%E1%BA%ADp%20tr%C3%ACnh%20H%C6%B0%E1%BB%9Bng%20%C4%91%E1%BB%91i%20t%C6%B0%E1%BB%A3ng.ipynb) | 
# [Mục lục](http://nbviewer.jupyter.org/github/manleviet/introCSusingPython/blob/master/index.ipynb) | 
# [Tiếp: Trực quan hoá dữ liệu](http://nbviewer.jupyter.org/github/manleviet/introCSusingPython/blob/master/11%20-%20Tr%E1%BB%B1c%20quan%20ho%C3%A1%20d%E1%BB%AF%20li%E1%BB%87u.ipynb)