{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tìm kiếm và sắp xếp\n",
    "\n",
    "## Tìm kiếm\n",
    "\n",
    "### Tìm kiếm tuần tự cho danh sách chưa được sắp xếp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def linear_search(L, e):\n",
    "    found = False\n",
    "    for i in range(len(L)):\n",
    "        if e == L[i]:\n",
    "            found = True\n",
    "    return found"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tìm kiếm tuần tự cho danh sách đã được sắp xếp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(L, e):\n",
    "    for i in range(len(L)):\n",
    "        if L[i] == e:\n",
    "            return True\n",
    "        if L[i] > e:\n",
    "            return False\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tìm kiếm nhị phân 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bisect_search1(L, e):\n",
    "    if L == []:\n",
    "        return False\n",
    "    elif len(L) == 1:\n",
    "        return L[0] == e\n",
    "    else:\n",
    "        half = len(L) // 2\n",
    "        if L[half] > e:\n",
    "            return bisect_search1(L[:half], e)\n",
    "        else:\n",
    "            return bisect_search1(L[half:], e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tìm kiếm nhị phân 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bisect_search2(L, e):\n",
    "    def bisect_search_helper(L, e, low, high):\n",
    "        if high == low:\n",
    "            return L[low] == e\n",
    "        mid = (low + high) // 2\n",
    "        if L[mid] == e:\n",
    "            return True\n",
    "        elif L[mid] > e:\n",
    "            if low == mid:\n",
    "                return False\n",
    "            else:\n",
    "                return bisect_search_helper(L, e, low, mid - 1)\n",
    "        else:\n",
    "            return bisect_search_helper(L, e, mid + 1, high)\n",
    "\n",
    "    if len(L) == 0:\n",
    "        return False\n",
    "    else:\n",
    "        return bisect_search_helper(L, e, 0, len(L) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "testList = [1, 2, 3, 5, 7, 9, 18, 27]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bisect_search1(testList, 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bisect_search1(testList, 15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bisect_search2(testList, 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bisect_search2(testList, 15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sắp xếp\n",
    "\n",
    "### Sắp xếp nổi bọt - Bubble Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort(L):\n",
    "    swap = False\n",
    "    while not swap:\n",
    "        print(L)\n",
    "        swap = True\n",
    "        for j in range(1, len(L)):\n",
    "            if L[j - 1] > L[j]:\n",
    "                swap = False\n",
    "                temp = L[j]\n",
    "                L[j] = L[j-1]\n",
    "                L[j-1] = temp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "test = [1, 5, 3, 8, 4, 9, 6, 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 3, 8, 4, 9, 6, 2]\n",
      "[1, 3, 5, 4, 8, 6, 2, 9]\n",
      "[1, 3, 4, 5, 6, 2, 8, 9]\n",
      "[1, 3, 4, 5, 2, 6, 8, 9]\n",
      "[1, 3, 4, 2, 5, 6, 8, 9]\n",
      "[1, 3, 2, 4, 5, 6, 8, 9]\n",
      "[1, 2, 3, 4, 5, 6, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "bubble_sort(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Selection Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(L):\n",
    "    suffixSt = 0\n",
    "    while suffixSt != len(L):\n",
    "        print(L)\n",
    "        for i in range(suffixSt, len(L)):\n",
    "            if L[i] < L[suffixSt]:\n",
    "                L[suffixSt], L[i] = L[i], L[suffixSt]\n",
    "        suffixSt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "test = [1, 5, 3, 8, 4, 9, 6, 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 3, 8, 4, 9, 6, 2]\n",
      "[1, 5, 3, 8, 4, 9, 6, 2]\n",
      "[1, 2, 5, 8, 4, 9, 6, 3]\n",
      "[1, 2, 3, 8, 5, 9, 6, 4]\n",
      "[1, 2, 3, 4, 8, 9, 6, 5]\n",
      "[1, 2, 3, 4, 5, 9, 8, 6]\n",
      "[1, 2, 3, 4, 5, 6, 9, 8]\n",
      "[1, 2, 3, 4, 5, 6, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "selection_sort(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Merge Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(left, right):\n",
    "    result = []\n",
    "    i, j = 0, 0\n",
    "    while i < len(left) and j < len(right):\n",
    "        if left[i] < right[j]:\n",
    "            result.append(left[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            result.append(right[j])\n",
    "            j += 1\n",
    "    while (i < len(left)):\n",
    "        result.append(left[i])\n",
    "        i += 1\n",
    "    while (j < len(right)):\n",
    "        result.append(right[j])\n",
    "        j += 1\n",
    "    print('merge ', result)\n",
    "    return result\n",
    "\n",
    "def merge_sort(L):\n",
    "    print(L)\n",
    "    if len(L) < 2:\n",
    "        return L[:]\n",
    "    else:\n",
    "        middle = len(L) // 2\n",
    "        left = merge_sort(L[:middle])\n",
    "        right = merge_sort(L[middle:])\n",
    "        return merge(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "test = [1, 5, 3, 8, 4, 9, 6, 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 3, 8, 4, 9, 6, 2]\n",
      "[1, 5, 3, 8]\n",
      "[1, 5]\n",
      "[1]\n",
      "[5]\n",
      "merge  [1, 5]\n",
      "[3, 8]\n",
      "[3]\n",
      "[8]\n",
      "merge  [3, 8]\n",
      "merge  [1, 3, 5, 8]\n",
      "[4, 9, 6, 2]\n",
      "[4, 9]\n",
      "[4]\n",
      "[9]\n",
      "merge  [4, 9]\n",
      "[6, 2]\n",
      "[6]\n",
      "[2]\n",
      "merge  [2, 6]\n",
      "merge  [2, 4, 6, 9]\n",
      "merge  [1, 2, 3, 4, 5, 6, 8, 9]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 8, 9]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "merge_sort(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- - -\n",
    "[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) | \n",
    "[Mục lục](http://nbviewer.jupyter.org/github/manleviet/introCSusingPython/blob/master/index.ipynb) | \n",
    "[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)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}