Lecture 6 Quicksort 本章的重點在介紹Quicksort的作法 然後給予時間複雜度的分析。

Slides:



Advertisements
Similar presentations
渡黑水溝 郁永河. 2 戎克船:是明末清初時期往返兩岸的主要交通工具 ∗ 1. 關於台灣的開發歷史,我們到底了解多少呢?不妨試著說出 就我們所知有關台灣開發史的故事、小說、電影、音樂與大 家分享。 ∗ 2. 什麼是黑水溝?黑水溝為什麼會成為大陸移民渡海來臺時最 大的威脅? ∗ 3. 有聽過「六死三留一回頭」、「有唐山公,無唐山嬤」這兩.
Advertisements

請按左鍵換頁 為人的藝術 ~善緣貴人多~ 廣結善緣 1. 有什麼觀念,就有什麼行為; 有什麼行為,就有什麼習慣; 有什麼習慣,就有什麼性格; 有什麼性格,就有什麼命運。 2. 對長輩謙虛是本分,對平輩謙虛是修養, 對 晚輩謙虛是高貴,對所有人謙虛是安全。 3. 廣結善緣,圓融的人際關係( EQ ):
中秋节 作者:杨露. “ 团圆节 ” “ 秋暮夕月 ” 的习俗 中秋拜月 热爱中秋佳节 每年农历八月十五日,是传统的中秋佳节。 这时是一年秋季的中期,所以被称为中秋。在中 国的农历里,一年分为四季,每季又分为孟、仲、 季三个部分,因而中秋也称仲秋。八月十五的月 亮比其他几个月的满月更圆,更明亮,所以又叫.
凱琪的包裹 這個故事是發生在第二次世界大戰後的歐洲。故事 藉由美國及荷蘭的兩位小女孩,因書信的往來而發
Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order
幼小課程統合與銜接 楊朝祥 中原大學講座教授.
第三节 人类的居住地——聚落.
大南海文化園區 (國立歷史博物館 -初期計畫) 簡介
举国上下抗击风雪灾害专刊 温暖行动 灾情告急年关近 万众一心齐抗灾 可歌可泣留千古 温暖行动遍人间 导读提示 阳关雨露出版社
11010: Tic-Tac-Tough ★★★★☆ 題組: Problem Set Archive with Online Judge
作文选刊 作文之窗
Introduction 基本概念 授課老師:蕭志明
主講者:林妙容 國立暨南國際大學 輔導與諮商研究所專任助理教授
第六课 师爱助我成长 我爱我师 导入 新课 进行 新课 练习 拓展.
快乐假期 2010年第6期 总第54期 贝尔芬 主编 暑期作文专刊 《快乐假期》杂志社 出版.
第1章第3节 量化研究与质化研究 案例1:关于中学思想政治教师专业发展现状和需求的调查研究
增值税转型 2008年12月.
分治演算法 與 刪尋演算法 各個擊破與化整為零.
团队介绍 (1)西湖区社区街道挂职社会实践基地 (2)武义、缙云、双浦乡镇挂职社会实践基地 (3)BOX企业实习社会实践基地
老师:如何撰写教研文章? 主讲:石修银 谨以此赠与孜孜追求的老师 谨以此赠与改变人生的老师.
依“标”据“本”,命制考题 发表于《数学教学》2006年第9期 (华东师大核心“CN”刊物)
第十一章 真理与价值 主讲人:阎华荣.
學生對弘爺早餐店的滿意度 ─以南台學生為例
12星座 对于星座,你又知道多少呢? 第一刊.
論文研討 2 學分 授課教師:吳俊概.
Recurrences 給定T(n)=T(n/2) + O(n) 我們該如何得到 T(n) = O(nlogn)?
分治演算法 各個擊破獲得最後勝利 國立中央大學 資工系 江振瑞 教授.
第十一章 理气剂.
第七章 固 定 资 产.
数学通报简介 ——如何写稿及投稿 数学通报 郑亚利 2014年8月.
第三节 固精缩尿止带药 1.特点:酸涩收敛,主归肾、膀胱经。 2.功效:固精、缩尿、止带。兼补肾。
推进《玻璃钢制品工》 国家职业资格证书制度的建设
本期导读: 1版 习 惯 2版 的 十个做人的好习惯 3版 力 4版 量 5版 6版 7版 8版
穩定是指偏離平衡時能夠回復平衡的特性,控制則是改變飛行狀態的機制。
好好國際物流股份有限公司 全球運籌物流服務建議 中 華 貨 物 通 關 自 動 化 協 會 理 事 長 劉 陽 柳 二○○二年五月十五日
「基本烹調法」 教學經驗分享 台南市安平國中 陳玫珺老師 許依玲老師.
行政院國軍退除役官兵輔導委員會 嘉義榮民醫院.
计算机问题求解 – 论题 算法的效率 2018年03月14日.
分治演算法 各個擊破獲得最後勝利 國立中央大學 資工系 江振瑞 教授.
主讲人: 吕敏 { } Spring 2012 ,USTC 算法基础 主讲人: 吕敏 { } Spring 2012 ,USTC.
Course 4 搜尋 Search.
数学 九年级上、下册合订 新课标(ZJ).
快速排序法 (Quick Sort).
Course 9 NP Theory序論 An Introduction to the Theory of NP
主讲人: 吕敏 } Spring 2012 ,USTC 算法基础 主讲人: 吕敏 } Spring 2012 ,USTC.
人(大人)(人口)(人手) 个(个人)(三个)(个子zi ) 手(小手)(双手)(手工) 大(大人)(大山)(大火)
东北林业大学 陈宇 ACM程序设计 东北林业大学 陈宇
公立學校教職員退休資遣撫卹條例重點說明 苗栗縣政府人事處編製 主講人:陳處長坤榮 107年5月2日.
计算机问题求解—论题4.9 随机算法的概念 陶先平 2017年5月15日.
Course 10 削減與搜尋 Prune and Search
講師:郭育倫 第2章 效能分析 講師:郭育倫
資料結構與C++程式設計進階 遞迴(Recursion) 講師:林業峻 CSIE, NTU 6/ 17, 2010.
資料結構簡介 綠園.
演算法分析 (Analyzing Algorithms)
红利、年金、满期金自动转入聚宝盆,收益有保底,升值空间更大
100學年度上學期 月亮班課程規劃.
香港大學教育應用資訊科技發展研究中心 資訊年代青年自學才能拓展計劃 (S計劃)
北一女中 資訊選手培訓營 遞迴、河內塔與merge sort Nan.
Divide and Conquer 3 Michael Tsai 2011/3/11.
Multi-threaded Algorithm 3
Open topic2: 大O( Θ ,Ω)和小o( θ ,ω)有什么区别? 3/19/18 黄秉焜
元 排 序 法.
1753: Need for Speed ★★☆☆☆ 題組:Problem Set Archive with Online Judge
The role of Algorithms in Computing
資料結構 老師:李崇明 助教:楊斯竣.
Quicksort 本章的重點在介紹Quicksort的作法 然後給予時間複雜度的分析。.
Advanced Competitive Programming
算法的基本思想: 第6章 内部排序 6.2 气泡排序 将待排序的记录看作是竖着排列的“气泡”,关键字较小 的记录比较轻,从而要往上浮。
12439: February 29 ★☆☆☆☆ 題組:Problem Set Archive with Online Judge
 等差數列 等差數列: a , a + d , a + 2d , a + 3d , 通項:
Presentation transcript:

Lecture 6 Quicksort 本章的重點在介紹Quicksort的作法 然後給予時間複雜度的分析。

6.1 Quicksort Quicksort(A[p..r]) Divide: 把 A[p..r] 分成 A[p..q-1] 和 A[q+1..r] A Conquer: 遞迴將 A[p..q-1] 和 A[q+1..r] 排序 Combine: 不需要作任何事 p r x pivot A[p..q-1] q A[q+1..r] x Quicksort也是典型的Divide-and-Conquer: 在分段的時候,我們先選定一個數字x 然後將所有比 x 小的數字都放到左邊,比 x 大的數字都放到右邊 然後左邊右邊分開來處理 Quicksort

2 q  Partition(A, p, r) /* divide */ Quicksort(A, p, r) 1 If p < r then 2 q  Partition(A, p, r) /* divide */ 3 Quicksort(A, p, q-1) /* conquer */ 4 Quicksort(A, q+1, r) /* conquer */ Quicksort

Partition(A, p, r) 1 x  A[r] 2 i  p-1 3 for j p to r-1 4 do if A[j]  x 5 then i  i+1 6 exchange A[i]A[j] 7 exchange A[i+1]A[r] 8 return i+1 Partition就是先前提到的,x 是我們選定的 pivot 比 x 小的數字就放到左邊去 Quicksort

i 和 j 的意義: p i j r x ≤ x > x unrestricted Quicksort i 和 j 都會越來越大 i 的左邊都是小於等於 x 的數字 介於 i, j 中間的數字都是大於 x 在 j 右邊的那些數字則是還沒處理到的 Quicksort

i 和 j 如何改變: p i j r >x x ≤ x > x p i j r x ≤ x > x Quicksort 當 j 那一格的數字比 x 還要大的時候, 我們直接將 j 移到下一格去,這樣仍舊符合我們前一頁定義的 i, j 特性 x ≤ x > x Quicksort

i 和 j 如何改變: p i j r ≤x x ≤ x > x p i j r x ≤ x > x Quicksort 當 j 那格數字小於等於 x 的時候,我們將那個數字跟 i+1 那格的數字交換 然後 i 與 j 各往後移動一格 x ≤ x > x Quicksort

範例: (Partition, x=A[r]=4) p,j p i j r r (a) (f) 2 8 7 1 3 5 6 4 2 1 3 8 7 5 6 4 p,i j p i j r r (b) (g) 2 8 7 1 3 5 6 4 2 1 3 8 7 5 6 4 p,i j p i (c) r r (h) 2 8 7 1 3 5 6 4 2 1 3 8 7 5 6 4 (d) 黃色是pivot x, 灰色的部分是處理過的數字中大於 x 的數字 綠色的部分是處理過的數字中小於等於 x 的數字,白色的則是還沒處理到的數字。 p,i j p i r (i) r 2 8 7 1 3 5 6 4 2 1 3 4 7 5 6 8 p i j r (e) 2 1 7 8 3 5 6 4 Quicksort

6.2 分析 Worst-case: (n2) (對於已排序好的輸入) T(n) = = 猜測: T(n)  c n2 = O(n2) Substituting: T(n)   c  c(n-1)2+(n)  cn2-c(2n-1)+(n)  cn2 (挑選夠大的 c 即可) 因為輸入已經是排序好的 因此我們找到的 x 不能很平均地把數字分段 Quicksort

T(n)=(n2) n n 1 n-1 n n 1 n-2 n-1 1 n-3 n-2 2 3 1 1 2 (n2) Quicksort 由於數字已經排序好,所以每次partition都只會把pivot切開 造成每次partition都很不平均的情況發生 2 3 1 1 2 (n2) Quicksort

Average-case: (n lg n) (假設所有的元素都不相同) T(n)=O(n+X),X 是 Partition 中第四行的執行次數。 每次呼叫 Partition 的時候,如果 A[i]<x<A[j] 或 A[j]<x<A[i],A[i] 和 A[j] 將來就不會再互相比較。 Quicksort

範例: 令 A={3,9,2,7,5}。 第一個回合後,A={3,2,5,9,7}。 之後 {3,2} 再也不會和 {9,7} 比較了。 將 A 的元素重新命名為 z1,z2,...,zn,其中 zi 是第 i 小的元素。且定義 Zij={zi,zi+1,...,zj}。 定義zi : zj :若且唯若第一個從 Zij 選出來的 pivot 是 zi 或 zj。 Quicksort

對於任意的 i 和 j,發生 zi : zj 的機率為 2/(j-i+1), 因此, X = = < (套用 Harmonic Series) = O(nlg n) Quicksort

n n n lg n n … 1 1 1 1 1 1 1 1 n Total:Θ(n lg n) Quicksort 由於recursion tree的高度為log(n), 每一層所花的時間為Θ(n) 因此最後的時間是Θ(n log n) … 1 1 1 1 1 1 1 1 n Total:Θ(n lg n) Quicksort

n n n 1 n … ≤n ≤n 1 Total:Θ(n lg n) Quicksort 就算partition的時候沒有像上一頁切得很平均 只要能將一個長度為 n 的數列切成兩份長度比例為 1:9 (甚至 1:1000, 1:10000都可) 的話,時間仍舊是Θ(n log n) ≤n 1 ≤n Total:Θ(n lg n) Quicksort

其他分析 E(n) = = 為了簡單起見,假設 nE(n) = ------(1) (n-1)E(n-1) = ------(2) E(n)為Average Case下的執行時間 q 是 partition 成兩部分的其中一部份長度 (1/n) * { E(q-1) + E(n-q) } for all q = 1 to n 則表示Partition之後平均情況下的執行時間 (用 n-1 替換掉 (1) 裡面的 n) Quicksort

E(n) = (套用 iteration method) = = = = = = (n)+(n) (1)-(2), 可得 nE(n) = E(n) = (套用 iteration method) = = = = = = (n)+(n) = (n)+(n)(lg n)+2 (套用 Harmonic Series) = (nlg n) Quicksort

6.3 Randomized version of quicksort Randomized Algorithm: 使用亂數產生器的演算法。 Pseudorandom-number generator: 一個傳回在統計上看似隨機數字的 deterministic algorithm 。 Randomized-Partition(A, p, r) i  Random(p, r); exchange(A[r], A[i]); return Partition(A, p, r) 之前是選數列中的最後一個數字當作 pivot, 現在是隨便選數列中的任何一個數字當作 pivot,可以有很高的機率可以避免worst case的發生 Quicksort

Exercises Problem 1: 企業喜歡有個好記的電話號碼。用一個好記的詞或片語來拼電話號碼是一個方法。例如,您撥打 TUT-GLOP 就能打到滑鐵盧大學。有的時候號碼中只有一部分的數字被拿來拼字。當您回到您的旅館時,您能撥打 310-GINO 到 Gino’s 點一個披薩。另一個讓電話號碼好記的方法是把數字編組。例如您能撥打”三個十”3-10-10-10 到 Pizza Hut 點您的披薩。 電話號碼的標準格式由七個十進位的數字所構成,其中有一個連字號在三和第四個數字之間(例如:888-1200)。電話的按鍵提供了字母與數字的對應, 如下所示: Quicksort

Exercises A、 B 和 C 對應到 2; D、 E 和 F 對應到 3 G、 H 和 I 對應到 4; J、 K 和 L 對應到 5 M、 N 和 O 對應到 6; P、 R 和 S 對應到 7 T、 U 和 V 對應到 8; W、 X 和 Y 對應到 9 Q 和 Z 沒有對應的數字。連字號不用撥,而且可以視情況增加或刪除。TUT-GLOP 的標準格式是 888-4567,310-GINO 的標準格式是 310-4466,而 3-10-10-10 的是 310-1010。 二個電話號碼如果有同樣標準格式表示他們是相同的。(他們撥同樣的數字。)您的公司正要整理地方企業的電話號碼。為了控制品質,您想要檢查有沒有兩家(或更多)的企業有同樣電話號碼。 Quicksort

Exercises 輸入:第一行包含了一個整數,代表總共有幾筆資料。隨後會接著一個空行。之後的第一行是一個正整數(最大到 100000),代表要處理的電話號碼的數目。接下來的每一行都有一組電話號碼,由十進位的數字、大寫字母(Q 和 Z 除外)以及連字號所構成。其中剛好有七個字元是字母或數字。每筆資料中間都有一個空行。 輸出:列出所有出現兩次以上的電話號碼。每一行必須是電話號碼的標準格式,接著是該電話號碼出現的次數(兩者用一個空白隔開)。這些電話號碼必須要由小到大排好。如果沒有電話號碼是重複的,那就輸出一行: No duplicate. 在兩筆資料之間要印一個空行。 Quicksort

以下是一個輸出入的實例: Sample Input Sample Output 1 12 4873279 ITS-EASY 888-4567 3-10-10-10 888-GLOP TUT-GLOP 967-11-11 310-GINO F101010 888-1200 -4-8-7-3-2-7-9- 487-3279 310-1010 2 487-3279 4 888-4567 3 Quicksort

Exercises Problem 2: 某家公司正在尋求一個簡單的方法來編寫員工的資訊。目前的做法是各個部門分別列出自己的員工,然後再統一把資料集中送到公司負責人那邊,負責人再將蒐集好的名單根據姓氏排序。但是人力太花時間了,所以負責人希望能有一個程式幫忙做這件事情:輸入所有員工的資料,合併整理之後再輸出。 Quicksort

Exercises 輸入:輸入的第一行包含了公司部門的數目(介於 2 和 12 之間),接下來會有各個部門的員工資料。每一個部門提供的資料中,第一行是部門的名稱,之後的每一行都有一個員工的資料(直到空行或是檔案結尾為止)。資料格式如下: 稱謂,名字,姓氏,地址,家中電話,辦公電話,校園信箱號碼 (用逗號隔開) 最多只有 20000 個員工。 輸出:以下是輸出的格式:(請參閱輸出實例) -------------------- <稱謂> <名字> <姓氏> <地址> Department: <部門名稱> Home Phone: <家中電話> Work Phone: <辦公電話> Campus Box: <校園信箱號碼> Quicksort

以下是一個輸出入的實例: Sample Input Sample Output Quicksort 2 English Department Dr.,Tom,Davis,Anystreet USA,555-2832,555-2423,823 Mrs.,Jessica,Lembeck,Center Street,555-2543,555-8584,928 Computer Science Mr.,John,Euler,East Pleasure,555-1432,555-2343,126 ---------------------------------------- Dr. Tom Davis Anystreet USA Department: English Department Home Phone: 555-2832 Work Phone: 555-2423 Campus Box: 823 Mr. John Euler East Pleasure Department: Computer Science Home Phone: 555-1432 Work Phone: 555-2343 Campus Box: 126 Mrs. Jessica Lembeck Center Street Home Phone: 555-2543 Work Phone: 555-8584 Campus Box: 928 Quicksort