HW1/HW1-QuickSort_new.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我在每一次要開始打程式之前，\n",
    "\n",
    "都會先在一張紙上\n",
    "把我想的跟我理解的先寫下來或畫出來把我想得跟我理解的先寫下來或畫出來(如附件一)\n",
    "\n",
    "雖然整張紙很亂，看起來好像沒什麼重點，\n",
    "\n",
    "但我都會盡量把我的想法先寫出來，因為我打程式的能力還不夠，\n",
    "\n",
    "所以用紙筆的方式我會比較知道我自己在做甚麼，\n",
    "\n",
    "都用好後我才打程式。\n",
    "\n",
    "一開始在紙上自己畫了很多次QuickSort跑的流程，\n",
    "但我都設定要抓最後一個數去跟其他比較。\n",
    "\n",
    "還有我有想到一些條件:\n",
    "1. 我發現這段程式會需要三個List去裝比基準點大的數、比基準點小的數、以及基準點(也就是我要拿來跟其他數做比較的那個數)\n",
    "2. 要可以做排序比較的條件是長度一定要大於1，因為這樣他才有元素可以去做比較跟排序\n",
    "\n",
    "我的想法很簡單，就是最基本的分來分去，然後左右左右放。\n",
    "\n",
    "大於比較的數的話，放右邊；\n",
    "\n",
    "小於比較的數的話，放左邊；\n",
    "\n",
    "等於比較的數的話，放中間。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1 :\n",
    "\n",
    "我先設立了三個空的List，\n",
    "\n",
    "他們的功能用來裝我比較後的數(大的放右邊，小的放左邊)\n",
    "\n",
    "然後還有用來放我的基準點。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "LeftSide = []\n",
    "RightSide = []\n",
    "Compare = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 2:\n",
    "\n",
    "接著我用我的生日創了一個List，準備拿來做排序\n",
    "\n",
    "我取了最後一個數當作基準去做比較。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list = [1,9,9,9,0,5,1,8]\n",
    "Last = list[-1]\n",
    "Last"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 3:\n",
    "\n",
    "我知道假如這個List長度大於1的話，\n",
    "\n",
    "就要用for迴圈去做一個一個數的比大小，\n",
    "\n",
    "所以我先用if、else寫了假如他長度小於或等於1的話，他會直接印回來，\n",
    "\n",
    "如果長度大於1的話，才取最後一個數並進到for迴圈裡做排序比較那些。\n",
    "\n",
    "我用if、elif、else分成三個，\n",
    "\n",
    "並按照我一開始在紙上寫的想法一樣，\n",
    "\n",
    "大於比較的數的話，加到右邊的List；\n",
    "\n",
    "小於比較的數的話，加到左邊的List；\n",
    "\n",
    "等於比較的數的話，加到中間的List。\n",
    "\n",
    "最後把這次排完的結果印出來。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 0, 5, 1, 9, 9, 9, 8]\n"
     ]
    }
   ],
   "source": [
    "if len(list) <= 1:\n",
    "    print (list)\n",
    "else:\n",
    "    Last = list[-1]\n",
    "    for i in list:\n",
    "        if i < Last:\n",
    "            LeftSide.append(i)\n",
    "        elif i > Last:\n",
    "            RightSide.append(i)\n",
    "        else:\n",
    "            Compare.append(i)\n",
    "        \n",
    "print (LeftSide+RightSide+Compare)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 4:\n",
    "\n",
    "然後我就在想阿，如果這樣跑一次只能排一輪的話，\n",
    "\n",
    "這樣每次一分完就要再重新輸入一次左邊的List跟右邊的List甚麼的，\n",
    "\n",
    "就根本不是QuickSort了阿...\n",
    "\n",
    "所以，我就上網找QuickSort的資料，看他到底要怎麼樣才可以一直跑跑到最後成功分完，\n",
    "\n",
    "然後我就看到了一個QuickSort的範例:\n",
    "http://jialin128.pixnet.net/blog/post/142927691-%5b-%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%5d-%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%B3%95%EF%BC%88quick-sort%EF%BC%89in-python\n",
    "\n",
    "我發現他外面用def寫成了一個function，所以他的程式可以一直跑一直跑，\n",
    "\n",
    "當跑完第一次，只需要呼叫這個function，就可以一直跑到最後成功排序完所有的數字。\n",
    "\n",
    "所以我就學他用了一個def創一個function，叫做QuickSort，\n",
    "\n",
    "然後我還發現一個不一樣，就是這個人在def裡面要印東西出來他是用return而不是print，\n",
    "\n",
    "後來我問同學return跟print到底是差在哪，\n",
    "\n",
    "他跟我說只要是return都用在def，\n",
    "\n",
    "並且把上面的程式都一起丟進去變成一個完整的QuickSort。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def QuickSort (list):\n",
    "    LeftSide = []\n",
    "    RightSide = []\n",
    "    Compare = []\n",
    "    \n",
    "    if len(list) <= 1:\n",
    "        return list\n",
    "    \n",
    "    else:\n",
    "        Last = list[-1]\n",
    "        for i in list:\n",
    "            if i < Last:\n",
    "                LeftSide.append(i)\n",
    "            elif i > Last:\n",
    "                RightSide.append(i)\n",
    "            else:\n",
    "                Compare.append(i)\n",
    "\n",
    "    LeftSide = QuickSort(LeftSide)\n",
    "    RightSide = QuickSort(RightSide)\n",
    "\n",
    "    return LeftSide + Compare + RightSide\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 5:\n",
    "\n",
    "然後我又用我的生日做一次測試。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 5, 8, 9, 9, 9]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list = [1,9,9,9,0,5,1,8]\n",
    "QuickSort(list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 然後然後然後 就 成 功 了 啦  ! ! !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最後附上QuickSort的時間複雜度\n",
    "\n",
    "QuickSort時間複雜度:(n為資料筆數)\n",
    "                \n",
    "    Best Time          O(nlogn)\n",
    "    Average Time       O(nlogn)\n",
    "    Worst Time         O(n^2)"
   ]
  }
 ],
 "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
}