第八章 排序 8-1 排序簡介 8-2 內部排序法 8-3 外部排序法.

Slides:



Advertisements
Similar presentations
不定積分 不定積分的概念 不定積分的定義 16 不定積分的概念 16.1 不定積分的概念 以下是一些常用的積分公式。
Advertisements

1 第八章 深入探討樹狀結構. 2 目次 8.1 m-way 搜尋樹 8.2 B-tree 8.3 動動腦時間 8.4 練習題解答.
Introduction to C Programming
使用C/C++語言 楊正宏 編著 全華科技圖書股份有限公司 印行.
1.1 利用平方差及完全平方的恆等式 分解因式 A 利用平方差的恆等式 B 利用完全平方的恆等式 目錄.
Sort(排序) 授課者:驕芸.
遞迴關係-爬樓梯.
課程名稱:程式設計 授課老師:________
TQC+ JAVA全國教師研習會 PLWeb 程式設計練習平台 簡介.
輔助記憶體.
Chapter 5 遞迴 資料結構導論 - C語言實作.
課程名稱:資料結構 授課老師:_____________
資料結構 第3章 鏈結串列.
資料結構設計與C++程式應用 Fundamentals of Data Structures and Their Applications Using C++ 第3章 佇列 資料結構設計與C++程式應用.
第11章 資料結構 – 使用C語言的模組 11-1 資料結構的基礎 11-2 C語言的模組化程式設計 11-3 基本鏈結串列
第十章 排序與搜尋.
Analysis of Sorting Algorithms
4B冊 認識公倍數和最小公倍數 公倍數和最小公倍數的關係.
(Circular Linked Lists)
Course 3 排序 Sort.
基數排序 (Radix Sort).
資料結構 第1章 導論.
Chapter 9 高度平衡二元搜尋樹 AVL Binary Search Tree
Java 程式設計 講師:FrankLin.
私立南山高中 信息組 電腦研習 電腦資料的備份 中華民國 99年4月20日 星期二.
排序的相關知識 排序(Sorting)是指將一群資料,按特定規則調換位置,使資料具有某種次序關係(遞增或遞減)。
基數排序法.
Chapter 8 排序 資料結構導論 - C語言實作.
Sorting 排序 Bubble Sort O(n2) Insert Sort Selection Sort Quick Sort
Chap3 Linked List 鏈結串列.
Chapter 11 B-tree 11.1 m-way 搜尋樹 11.2 B-tree.
第七章 資料排序 Sorting 版權屬作者所有,非經作者 同意不得用於教學以外用途.
北一女中 資訊選手培訓營.
資料結構 優點 缺點 1 陣列 (Array) 沒有額外變量 (例head, next,...) 運作/操作較簡單 更新資料時,若要保持順序,需要移動較大量資料 靜態結構Static (宣告時已決定了陣列元素多少,不能在程式執行期間增減元素) 2 隊列Queue (FIFO) 容易更新 加入enqueue:
Reference to FUNDAMENTALS OF DATA STRUCTURE IN C++
第8章 資料排序 資料結構設計與C++程式應用
Sorting in Linear Time.
第一次Labview就上手 參考書籍: LabVIEW for Everyone (Jeffrey Travis/Jim Kring)
CH05. 選擇敘述.
第 十 章 排序(Sorting) 課程名稱:資料結構 授課老師:________ 2019/4/20.
挑戰C++程式語言 ──第8章 進一步談字元與字串
蕭志明 老師 Algorithm(演算法) Ext:6779
蕭志明 老師 Algorithm(演算法) /FB:
99高中資訊科選修課程 夥伴學習教師 專業進修研習 進階程式設計--演算法 教學示例與研討
Teacher: 郭育倫 Mail: 演算法 Teacher: 郭育倫 Mail:
Ogive plot example 說明者:吳東陽 2003/10/10.
C qsort.
13.1 氣泡排序 13.2 選擇排序 13.3 插入排序 13.4 合併排序 13.5 快速排序
程式設計-- Binary Search 通訊一甲 B 楊穎穆.
講師:郭育倫 第3章 基本資料結構 講師:郭育倫
流程控制:Switch-Case 94學年度第一學期‧資訊教育 東海大學物理系.
MiRanda Java Interface v1.0的使用方法
陣列與結構.
10394: Twin Primes ★★★☆☆ 題組:Problem Set Archive with Online Judge
12797: Letters ★★★☆☆ 題組:Problem Set Archive with Online Judge
動畫演示 Node規範了一些基本的方法,像是增加節點、刪除節點、讓節點做一些事、取得第n個節點等等
Commando War ★★☆☆☆ 題組:Problem Set Archive with Online Judge
例題 1. 多項式的排列 1-2 多項式及其加減法 將多項式 按下列方式排列: (1) 降冪排列:______________________ (2) 升冪排列:______________________ 排列 降冪:次數由高至低 升冪;次數由低至高.
資料表示方法 資料儲存單位.
程式設計--Quick Sort 通訊一甲 B 楊穎穆.
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
堆積(Heap Tree) 授課老師:蕭志明.
資料結構 老師:李崇明 助教:楊斯竣.
All Sources Shortest Path The Floyd-Warshall Algorithm
JAVA 程式設計與資料結構 第十九章 Sorting.
String類別 在C語言中提供兩種支援字串的方式 可以使用傳統以null結尾的字元陣列 使用string類別
Array(陣列) Anny
10303: How Many Trees? ★★☆☆☆ 題組:Contest Archive with Online Judge
Chapter 4 Multi-Threads (多執行緒).
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
Presentation transcript:

第八章 排序 8-1 排序簡介 8-2 內部排序法 8-3 外部排序法

排序簡介 在排序的過程中,資料的移動方式可分為「直接移動」及「邏輯移動」兩種。 「直接移動」是直接交換儲存資料的位置,而「邏輯移動」並不會移動資料儲存位置,僅改變指向這些資料的輔助指標的值。 資料在經過排序後,會有下列幾點好處: 1.資料較容易閱讀。 2.資料較利於統計及整理。 3.可大幅減少資料搜尋的時間。

排序的分類 1、內部排序:排序的資料量小,可以完全在記憶體內進 行排序。 2、外部排序:排序的資料量無法直接在記憶體內進行排 序,而必須使用到輔助記憶體(如硬碟)。 內部排序法有:氣泡排序法、選擇排序法、插入排序法、合併排序法、快速排序法、堆積排序法、謝耳排序法、基數排序法等。 外部排序法有:直接合併排序法、k路合併法、多相合併法等。

排序演算法分析 演算法是否穩定 穩定的排序是指資料在經過排序後,兩個相同鍵值的記錄仍然保持原來的次序,如下例中7左的原始位置在7右的左邊(所謂7左及7右是指相同鍵值一個在左一個在右),穩定的排序(Stable Sort)後7左仍應在7右的左邊,不穩定排序則有可能7左會跑到7右的右邊去。例如: 原始資料順序: 7左 2 9 7右 6 穩定的排序: 2 6 7左 7右 9 不穩定的排序: 2 6 7右 7左 9

時間複雜度(Time complexity): 可分為最好情況(Best Case)、最壞情況(Worst Case)及平均情況(Average Case)。 最好情況就是資料已完成排序,例如原本資料已經完成遞增排序了,如果再進行一次遞增排序所使用的時間複雜度就是最好情況。 最壞情況是指每一鍵值均須重新排列,簡單的例子如原本為遞增排序重新排序成為遞減,就是最壞情況。 排序前:2 3 4 6 8 9 排序後:9 8 6 4 3 2 【這種排序的時間複雜度就是最壞情況】

空間複雜度(Space complexity): 指演算法在執行過程所需付出的額外記憶體空間。 挑選的排序法必須藉助遞迴的方式來進行,那麼遞迴過程中會使用到的堆疊就是這個排序法必須付出的額外空間。 排序法所使用到的額外空間愈少,它的空間複雜度就愈佳。 氣泡法在排序過程中僅會用到一個額的空間,在所有的排序演算法中,這樣的空間複雜度就算是最好的。

內部排序法 排序名稱 排序特性 簡單排序法 1.氣泡排序法(Bubble Sort) (1)穩定排序法 2.選擇排序法(Selection Sort) (1)不穩定排序法 3.插入排序法(Insertion Sort) 4.謝耳排序法(Shell Sort)

高等排序法 1.快速排序法 (Quick Sort) (1)不穩定排序法 (2)空間複雜度最差O(n)最佳O(log2n) 2.堆積排序法 (Heap Sort) (2)空間複雜度為最佳,只需一個額外空間O(1) 3.基數排序法 (Radix Sort) (1)穩定排序法 (2)空間複雜度為O(np),n為原始資料的個數,p為基底

氣泡排序法 氣泡排序法又稱為交換排序法,是由觀察水中氣泡變化構思而成,氣泡隨著水深壓力而改變。 氣泡排序法的比較方式是由第一個元素開始,比較相鄰元素大小,若大小順序有誤,則對調後再進行下一個元素的比較。 如此掃描過一次之後就可確保最後一個元素是位於正確的順序。 接著再逐步進行第二次掃描,直到完成所有元素的排序關係為止。

氣泡排序法演算流程 由小到大排序:

第一次掃描會先拿第一個元素6和第二個元素4作比較,如果第二個元素小於第一個元素,則作交換的動作。 接著拿6和9作比較,就這樣一直比較並交換,到第4次比較完後即可確定最大值在陣列的最後面。

第二次掃描亦從頭比較起,但因最後一個元素在第一次掃描就已確定是陣列最大值,故只需比較3次即可把剩餘陣列元素的最大值排到剩餘陣列的最後面。

第三次掃描完,完成三個值的排序 第四次掃描完,即可完成所有排序 由此可知5個元素的氣泡排序法必須執行5-1次掃描,第一次掃描需比較5-1次,共比較4+3+2+1=10次

氣泡法分析 1. 最壞清況及平均情況均需比較:(n-1)+(n-2)+(n-3) + …+3+2+1= 次;時間複雜度為O(n2),最好情 況只需完成一次掃描,發現沒有做交換的動作則表 示已經排序完成,所以只做了n-1次比較,時間複雜 度為O(n)。 2. 由於氣泡排序為相鄰兩者相互比較交換,並不會更 改其原本排列的順序,所以是穩定排序法。 3.只需一個額外的空間,所以空間複雜度為最佳。 4.此排序法適用於資料量小或有部份資料已經過排序。

範例程式:ch08_01.c 執行結果:

範例程式:ch08_02.c 執行結果:

選擇排序法 選擇排序法可使用兩種方式排序,一為在所有的資料中,當由大至小排序,則將最大值放入第一位置;若由小至大排序時,則將最大值放入位置末端。 例如當N筆資料需要由大至小排序時,首先以第一個位置的資料,依次向2、3、4 …N個位置的資料作比較。 如果資料大於或等於其中一個位置,則兩個位置的資料不變;若小於其中一個位置,則兩個位置的資料互換。

排序法的演算流程 首先找到此數列中最小值後與第一個元素交換。

接著從第二個值找起,找到此數列中(不包含第一個)的最小值,再和第二個值交換。 接著從第三個值找起,找到此數列中(不包含第一、二個)的最小值,再和第三個值交換。 最後從第四個值找起,找到此數列中(不包含第一、二、三個)的最小值,再和第四個值交換,則此排序完成。

選擇法分析 1. 無論是最壞清況、最佳情況及平均情況都需要找到 最大值(或最小值),因此其比較次數為:(n-1)+(n-2) +(n-3)+…+3+2+1= 次;時間複雜度為O(n2) 2. 由於選擇排序是以最大或最小值直接與最前方未排序 的鍵值交換,資料排列順序很有可能被改變,故不是 穩定排序法。 3. 只需一個額外的空間,所以空間複雜度為最佳。 4. 此排序法適用於資料量小或有部份資料已經過排序。

範例程式:ch08_03.c 執行結果:

插入排序法 插入排序法(Insert Sort)是將陣列中的元素,逐一與已排序好的資料作比較,再將該陣列元素插入適當的位置。如以下說明: 由小到大排序: 原始值:6 4 9 8 3

插入法分析 1. 最壞及平均清況需比較(n-1)+(n-2)+(n-3)+…+3+2+1 = 次;時間複雜度為O(n2),最好情況時間複雜 2. 插入排序是穩定排序法。 3. 只需一個額外的空間,所以空間複雜度為最佳。 4. 此排序法適用於大部份資料已經過排序或已排序資 料庫新增資料後進行排序。 5.插入排序法會造成資料的大量搬移,所以建議在鏈結 串列上使用。

範例程式:ch08_04.c 執行結果:

謝耳排序法 「謝耳排序法」是D. L. Shell 在1959年7月所發明的一種排序法,而該排序法直接以發明者命名。 其排序法的原理有點像是插入排序法,但它可以減少資料搬移的次數。 排序的原則是將資料區分成特定間隔的幾個小區塊,以插入排序法排完區塊內的資料後再漸漸減少間隔的距離。

謝耳法分析 1.任何情況的時間複雜度均為O(n3/2)。 2.謝耳排序法和插入排序法一樣,都是穩定排序。 3.只需一個額外空間,所以空間複雜度是最佳。 4.此排序法適用於資料大部份都已排序完成的情況。

範例程式:ch08_05.c 執行結果:

合併排序法 合併排序法(Merge Sort)的工作原理乃是針對已排序好的二個或二個以上的檔案,經由合併的方式,將其組合成一個大的且已排序好的檔案。 底下是數列3,1,4,7,5,9,6,2合併排序法的的排序過程:

條列方式的步驟 將N個長度為1的檔案合併成N/2個已排序妥當且 長度為2的檔案。 2. 將N/2個長度為2的檔案合併成N/4個已排序妥當 且長度為4的檔案。 3. 將N/4個長度為4的檔案合併成N/8個已排序妥當 且長度為8的檔案。 4. 將N/2i-1個長度為2i-1的檔案合併成N/2i個已排序 妥當且長度為2i的檔案。

合併排序法: 1. 合併排序法n筆資料一般需要約log2n次處理, 每次處理的時間複雜度為O(n),所以合併排序 法的最佳情況、最差情況及平均情況複雜度為 O(nlogn)。 2. 由於在排序過程中需要一個與檔案大小同樣的 額外空間,故其空間複雜度O(n)。 3. 是一個穩定(stable)的排序方式。

快速排序法 快速排序法(Quick Sort)又稱分割交換排序法,是目前公認最佳的排序法。 假設有n筆記錄R1,R2,R3…Rn,其鍵值為k1,k2,k3…kn。快速排序法的步驟如下: 1. 取K為第一筆鍵值。 2. 由左向向找出一個鍵值Ki使得Ki>K。 3. 由右向左找出一個鍵值Kj使得Kj<K。 4. 若i<j則Ki與Kj交換,並繼續步驟的執行。 5. 若ij則將K與Kj交換,並以j為基準點將資料分為左右兩 部份。並以遞迴方式分別為左右兩半進行排序,直至 完成排序。

快速法分析 在最快及平均情況下,時間複雜度為O(nlog2n)。 最壞情況就是每次挑中的中間值不是最大就是最 小,其時間複雜度為O(n2)。 2. 快速排序法不是穩定排序法。 3. 在最差的情況下,空間複雜度為O(n),而最佳情況 為O(log2n)。 4. 快速排序法是平均執行時間最快的排序法。

範例程式:ch08_06.c 執行結果:

堆積排序法 堆積(Heap Sort)是一種特殊的二元樹,可分為最大堆積樹及最小堆積樹兩種。 最大堆積樹滿足以下3個條件: 最小堆積樹則具備以下3個條件: 1.它是一個完整二元樹。 2.所有節點的值都大於或等於它左右子節點的值。 3.樹根是堆積樹中最大的。 1.它是一個完整二元樹。 2.所有節點的值都小於或等於它左右子節點的值。 3.樹根是堆積樹中最小的。

堆積的基礎-最大堆積 在堆積的節點中,最大值是根節點9,所有子節點的資料都等於或比父節點小,這種堆積稱為「最大堆積」(Max Heap),如下圖所示:

堆積的基礎-最小堆積 反過來,如果根節點的資料是最小,所有子節點的資料都等於或比父節點大,稱為「最小堆積」(Min Heap),如下圖所示:

建立最大堆積-實作 最大堆積是一棵完整二元樹,除了最高階層外,它是一棵完滿二元樹(Full Binary Tree),在實作上可以使用陣列來儲存最大堆積,如下圖所示:

建立最大堆積-索引計算 heap[]陣列儲存堆積資料,heap_len是目前堆積的元素數,索引值是從1開始,索引值0並沒有使用,此時堆積節點的索引值計算,如下所示: 右子節點索引 = 父節點索引 * 2 + 1 左子節點索引 = 父節點索引 * 2 父節點索引 = 子節點索引 / 2

建立最大堆積-插入節點(說明) 在最大堆積插入節點,首先將節點插入heap[]陣列的最後,也就是插入成為二元樹的葉節點。 然後與父節點進行比較,往上一一和其父節點比較,就可以將二元樹調整成為堆積。

建立最大堆積-插入節點(圖例1) 左邊的二元樹插入節點9,首先插入在陣列heap_len+1的索引位置,然後與其父節點5比較,因為比較大,所以對調,如下圖所示:

建立最大堆積-插入節點(圖例2) 因為節點9比較大,所以交換,最後和根節點8進行比較,比較大所以交換,最後就可以重建成堆積。函數shiftUp()就可以向上調整節點來重建堆積。

建立最大堆積-取出最大節點(說明) 從堆積取出最大節點,以最大堆積來說,就是根節點,同樣的,當刪除根節點後,就需要重新調整來建立堆積。

建立最大堆積-取出最大節點(圖例) 首先刪除根節點9,並且將它取代成最後一個節點5,然後從上至下,比較其子節點,因為比左子節點小,所以交換,然後再與子節點比較,比左子節6小,所以交換即可完成堆積的重建。

堆積法分析 在所有情況下,時間複雜度均為O (nlogn)。 堆積排序法不是穩定排序法。 只需要一額外的空間,空間複雜度為O (1)。

範例程式:ch08_07.c 執行結果:

基數排序法 基數排序法(Radix Sort)依比較的方向可分為最有效鍵優先(Most Significant Digit First:MSD)和最無效鍵優先(Least Significant Digit First:LSD)兩種。 MSD法是從最左邊的位數開始比較,而LSD則是從最右邊的位數開始比較。 底下的範例我們以LSD將三位數的整數資料來加以排序,它是依個位數、十位數、百位數來進行排序。

原始資料: 步驟一:把每個整數依其個位數字放到串列中: 26 95 7 34 60 168 171 259 372 45 88 133 1 2 3 4 5 6 7 8 9 資料 60 171 372 133 34 95 45 26 168 88 59 259

步驟二:再依其十位數字,依序放到串列中: 合併後成為: 步驟二:再依其十位數字,依序放到串列中: 60 171 372 133 34 95 45 7 168 88 59 259 十位數字 1 2 3 4 5 6 7 8 9 資料 133 34 45 59 259 60 168 171 372 88 95

步驟二:再依其百位數字,依序放到串列中: 合併後成為: 步驟二:再依其百位數字,依序放到串列中: 7 133 34 45 59 259 60 168 171 372 88 95 百位數字 1 2 3 4 5 6 7 8 9 資料 34 45 59 60 88 95 133 168 171 259 372

最後合併即完成排序: 基數法分析: 7 34 45 59 60 88 95 133 168 171 259 372 在所有情況下,時間複雜度均為O(nlogpk),k是原始 資料的最大值。 2. 基數排序法是穩定排序法。 3. 基數排序法會使用到很大的額外空間來存放串列資 料,其空間複雜度為O(n*p), n是原始資料的個數,p 是資料字元數;如上例中,資料的個數n=12,字元數 p=3。 4. 若n很大,p固定或很小,此排序法將很有效率。

範例程式:ch08_08.c 執行結果:

外部排序法 外部儲存裝置又可依照存取方式分為兩種方式,如循序存取(如磁帶)或隨機存取(如磁碟)。 要循序存取的檔案就像是串列一樣,我們必須事先走訪整個串列才有辦法進行排序。 而隨機存取的檔案就像是陣列,資料存取方便,所以相對的排序也會比循序存取快一些。 最常使用的就是合併排序法,它適用於循序存取的檔案。

直接合併排序法 直接合併排序法(Direct Merge Sort)是外部儲存裝置最常用的排序方法。它可以分為兩個步驟: 1.將欲排序的檔案分為幾個可以載入記憶體空間大 小的小檔案,再使用內部排序法將各檔案內的資 料排序。 2.將第一步驟所建立的小檔案每二個合併成一個檔 案。兩兩合併後,把所有檔案合併成一個檔案後 就可以完成排序了。

範例程式:ch08_09.c 以下的程式是直接把兩個已經排序好的檔案合併與排序成一個檔案。 執行結果:

範例程式:ch08_10.c 執行結果:

k路合併法(k-Way Merge) 它所需要的時間儘需logkn,也就是處理輸出入時間減少許多,排序的速度也因此可以加快。 首先我門來描述利用3路合併(3-way merge)來處理27個行程(Runs)的示意圖:

多相合併法(Polyphase Merge) 它可以使用少於2k個磁碟,卻能正確無誤地執行k-way合併。以下示範了如何進行多相合併。 下圖共有21個runs,使用2-way合併及3個磁帶T1、T2、T3來進行合併,假設這21個行程(已排序完畢,且令其長度為1)的表示方為Sn,其中S為行程大小,n為長度相同run的個數。 例如8個runs且長度為2,可表示成28。

2-way及3個磁碟的多項合併 Phase T1 T2 T3 合併狀況說明 1 113 18 empty 起始分佈情況 2 15 28 度變成2 3 35 23 將T15個長度為1的行程和T35個長度為2的行 程,合併到T2,其長度變成3 4 53 32 將T23個長度為3的行程和T33個長度為2的行 程,合併到T1,其長度變成5 5 51 82 將T12個長度為5的行程和T22個長度為3的行 程,合併到T3,其長度變成8 6 131 81 將T11個長度為5的行程和T31個長度為8的行 程,合併到T2,其長度變成13 7 211 將T21個長度為13的行程和T31個長度為8的 行程,合併到T1,其長度變成21