{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# DS-Exercise Day3" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "- 交作業方式:\n", " - 於 GitHub 中，新增一個 Repo，命名為: X-Village-DS-Exercise\n", " - 並依照範例檔命名及完成作業，在上傳至 GitHub。\n", "\n", "- 歡迎用 [slido](https://app2.sli.do/event/bgcdkics/questions) (#4774) 匿名問問題和匿名交友，喔喔喔～～\n", "- 今日問卷: https://goo.gl/forms/OpxCqc6jnbzEXwMb2" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Sort" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Quickstart\n", "- Bubble Sort\n", "- Insertion Sort\n", "- Quick Sort\n", "- Merge Sort\n", "- Heap Sort" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## 用跳舞來視覺化排序吧（?!）\n", "- [Bubble-sort with Hungarian (\"Csángó\") folk dance](https://www.youtube.com/watch?v=lyZQPjUT5B4)\n", "- [Insert-sort with Romanian folk dance](https://www.youtube.com/watch?v=ROalU379l3U)\n", "- [Quick-sort with Hungarian (Küküllőmenti legényes) folk dance](https://www.youtube.com/watch?v=ywWBy6J5gz8)\n", "- [Merge-sort with Transylvanian-saxon (German) folk dance](https://www.youtube.com/watch?v=XaqR3G_NVoo)\n", "- [HEAP-sort with Hungarian (MEZŐSÉGI) folk dance](https://www.youtube.com/watch?v=Xw2D9aJRBY4)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "## 如果不想看跳舞，也可以看CS50\n", "- [Bubble Sort](https://www.youtube.com/watch?v=RT-hUXUWQ2I)\n", "- [Insert Sort](https://www.youtube.com/watch?v=kU9M51eKSX8)\n", "- [Quick Sort](https://www.youtube.com/watch?v=aQiWF4E8flQ)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Exercise4 用Python做排序 (ex4.py)" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "some_list = [\n", " 65, 81, 65, 19, 6, 28, 86, 40, 72, 27,\n", " 76, 46, 22, 98, 49, 57, 52, 46, 47, 14,\n", " 29, 15, 59, 74, 61, 47, 20, 33, 89, 99,\n", " 65, 82, 84, 63, 93, 1, 42, 13, 54, 58,\n", " 84, 17, 5, 18, 14, 14, 19, 42, 60, 77,\n", " 17, 29, 2, 42, 42, 31, 47, 67, 15, 16,\n", " 71, 56, 98, 46, 18, 20, 14, 36, 42, 23,\n", " 87, 7, 5, 5, 52, 78, 76, 91, 92, 88, 38,\n", " 66, 13, 18, 68, 96, 23, 51, 77, 93, 35,\n", " 18, 9, 64, 51, 76, 76, 96, 5, 18\n", "]" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Exercise5 深入淺出Python排序 (ex5.md)\n", "### Question 1 Python的`some_list.sort()`跟`sorted(some_list)`差別在哪?\n", "### Question 2 Python的`sorted()`是用哪種排序演算法?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Exercise6 用Python做排序 (ex6.py)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "- 現在有一筆ptt八卦版的資料，資料格式如下\n", " - 其中`h_推文總數`有可能會是空的字典(dict) \n", " i.e. `\"h_推文總數\": {}`" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "```json\n", "[\n", " {\n", " \"a_ID\": \"編號\",\n", " \"b_作者\": \"作者名\",\n", " \"c_標題\": \"標題\",\n", " \"d_日期\": \"發文時間\",\n", " \"e_ip\": \"發文ip\",\n", " \"f_內文\": \"內文\",\n", " \"g_推文\": {\n", " \"推文編號\": {\n", " \"狀態\": \"推 or 噓 or →\",\n", " \"留言內容\": \"留言內容\",\n", " \"留言時間\": \"留言時間\",\n", " \"留言者\": \"留言者\"\n", " },\n", " ...\n", " },\n", " \"h_推文總數\": {\n", " \"all\": \"推文數目\",\n", " \"噓\": \"噓數\",\n", " \"推\": \"推數\",\n", " \"none\": \"→數\"\n", " },\n", " \"i_連結\": \"原始連結\"\n", " },\n", " ......\n", "]\n", "```" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "- 讀入`external_data/ptt_0726_s.json`或`external_data/ptt_0726_m.json`\n", " - 差別在資料量的不同\n", "- 根據每篇文章推文的總數量來做排序，多的在前面" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Bouns3 實作各種sort作法 (bouns3.py)\n", "- insert sort\n", "- bubble sort\n", "- merge sort\n", "- quick sort\n", "- heap sort\n", "- etc.\n", "\n", "### Requriement\n", "不能用任何第三方函式庫" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Bouns4 分析各種sort適合的情境 (bouns4.md)\n", " \n", "1. 找幾筆實際的資料\n", " - [DATA.GOV.TW](https://data.gov.tw/datasets/search?qs=tid:6410+&order=pubdate)有很多資料！\n", "2. 測試各種排序的速度\n", " - [timeit](https://docs.python.org/3/library/timeit.html)\n", " - 可以使用[TheAlgorithms/Python](https://github.com/TheAlgorithms/Python)裡面的code\n", "3. 找出怎樣特性的資料適合怎樣的排序？並試著說明為什麼？" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# 記得要填問卷啊啊啊啊啊啊！！！！！！！ https://goo.gl/forms/OpxCqc6jnbzEXwMb2" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Reference\n", "- [AlgoRythmics](https://www.youtube.com/channel/UCIqiLefbVHsOAXDAxQJH7Xw)\n", "- [CS50](https://www.youtube.com/channel/UCcabW7890RKJzL968QWEykA)\n", "- [TheAlgorithms/Python](https://github.com/TheAlgorithms/Python)" ] } ], "metadata": { "celltoolbar": "Slideshow", "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.5" }, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false } }, "nbformat": 4, "nbformat_minor": 2 }