Sort(排序) 授課者:驕芸.

Slides:



Advertisements
Similar presentations
第一單元 建立java 程式.
Advertisements

計算機程式語言實習課.
Tree (2): heap, deap, 2-3 tree, 2-3-4tree
File Access 井民全製作.
专题研讨课二: 数组在解决复杂问题中的作用
Chapter 5 迴圈.
課程名稱:資料結構 授課老師:_____________
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)
第4章 串 串的基本概念和C语言的串函数 串的存储结构 动态数组实现的顺序串 串的模式匹配算法——BF算法 主要知识点.
第一章 程序设计入门.
選擇排序法 通訊一甲 B 楊穎穆.
排序 Sorting.
快速排序法 (Quick Sort).
第9章 排序.
Introduction to the C Programming Language
使用VHDL設計—4位元位移器 通訊一甲 B 楊穎穆.
C語言簡介 日期 : 2018/12/2.
程式撰寫流程.
(Circular Linked Lists)
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
第二章 SPSS的使用 2.1 啟動SPSS系統 2.2 結束SPSS系統 2.3 資料分析之相關檔案 2.4 如何使用SPSS軟體.
Chapter 9 高度平衡二元搜尋樹 AVL Binary Search Tree
排序的相關知識 排序(Sorting)是指將一群資料,按特定規則調換位置,使資料具有某種次序關係(遞增或遞減)。
Sorting 排序 Bubble Sort O(n2) Insert Sort Selection Sort Quick Sort
Chap3 Linked List 鏈結串列.
第9章 文件操作 文件 使用文件的目的 操作系统管理数据的基本单位 存储在外存储器上的数据的集合
計數式重複敘述 for 迴圈 P
程式設計實習課(四) ----C 函數運用----
第5讲 结构化程序设计(Part II) 周水庚 2018年10月11日.
第一單元 建立java 程式.
Chap4 Tree.
選擇性結構 if-else… switch-case 重複性結構 while… do-while… for…
北一女中 資訊選手培訓營.
資料結構使用Java 樹(Tree).
資料結構與C++程式設計進階 排序與搜尋 講師:林業峻 CSIE, NTU 6/ 14, 2010.
Reference to FUNDAMENTALS OF DATA STRUCTURE IN C++
第8章 資料排序 資料結構設計與C++程式應用
第一次Labview就上手 參考書籍: LabVIEW for Everyone (Jeffrey Travis/Jim Kring)
第九章 排序 概述 插入排序 快速排序 交换排序(起泡排序) 选择排序 归并排序.
挑戰C++程式語言 ──第8章 進一步談字元與字串
資料結構與C++程式設計進階 樹狀結構(Tree) 講師:林業峻 CSIE, NTU 11/ 12, 2009.
C qsort.
程式設計-- Binary Search 通訊一甲 B 楊穎穆.
累堆排序法 (Heap Sort).
挑戰C++程式語言 ──第7章 輸入與輸出.
流程控制:Switch-Case 94學年度第一學期‧資訊教育 東海大學物理系.
MiRanda Java Interface v1.0的使用方法
陣列與結構.
選擇性結構 if-else… switch-case 重複性結構 while… do-while… for…
第七章  数 组.
程式設計--linear search 通訊一甲 B 楊穎穆.
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)
資料表示方法 資料儲存單位.
程式設計--Quick Sort 通訊一甲 B 楊穎穆.
適用於多選一 可減少if 與 else配對混淆的錯誤.
資料結構 老師:李崇明 助教:楊斯竣.
資料結構 老師:李崇明 助教:楊斯竣.
All Sources Shortest Path The Floyd-Warshall Algorithm
JAVA 程式設計與資料結構 第十九章 Sorting.
String類別 在C語言中提供兩種支援字串的方式 可以使用傳統以null結尾的字元陣列 使用string類別
Trees 授課者:驕芸.
Array(陣列) Anny
10303: How Many Trees? ★★☆☆☆ 題組:Contest Archive with Online Judge
第三章 流程控制 程序的运行流程 选择结构语句 循环结构语句 主讲:李祥 时间:2015年10月.
C語言程式設計 老師:謝孟諺 助教:楊斯竣.
Introduction to the C Programming Language
Q6. 某學校將學生的電話號碼存貯在一個文字檔'telist.txt'。 在這交字檔中,每行有14個字符,代表學生班別、班號和電話號碼,
Unix指令4-文字編輯與程式撰寫.
函式庫補充資料 1.
Presentation transcript:

Sort(排序) 授課者:驕芸

Outline Sort Internal Sorting External Sorting Bubble Sort Selection Sort Insertion Sort Quick Sort Heap Sort External Sorting Merge Sort

Sort 將一群資料按照某一種排列的規則,重新安排此群資料的次序,使其形成一個遞增(或遞減)的線性次序關係。 排序的方法可分為兩種: Internal Sorting(內部排序) 將資料先儲存在記憶體內,然後執行排序。 External Sorting(外部排序) 資料太大無法全部儲存在記憶體,在排序的過程使用外部儲 存裝置。

Internal Sorting---Bubble Sort 讓數值大的數字慢慢往右移,就像在水裡的氣泡向上浮一樣。 作法: 由左至右,數字兩兩比對,若前面的數字比後面大,則前後交換,否則不換。 例子:我們要將以下的數字從小到大排序, 26, 5, 81, 7, 63 Step1: 5, 26, 7, 63, 81 Step2: 5, 7, 26, 63, 81 Step3: 5, 7, 26, 63, 81 Step4: 5, 7, 26, 63, 81 第一次排序完,最大值一定被挪到最右邊,why? 在第二次排序時只須比較前4個值。

Internal Sorting---Bubble Sort Example 將數字由小到大排序(泡沫排序法). void main( ) { int i,j,tmp; int a[5] = {26, 5, 81, 7, 63 }; for ( i = 0; i < 4; i++ ) for ( j = 0; j < 4; j++ ) if (a[j] > a[j+1]) tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } printf(“Loop %d : ”,i); for ( j = 0; j < 5; j++ ) printf(“%4d”,a[j]); printf(“\n”); system(“pause”); } 執行效率為O(n2), why? 最差的情況:元素用相反的順序排列,若有n個元素,總共需要n-1次的外層迴圈。 內層迴圈依照外層迴圈遞減,次數為(n-1) 、(n-2)、…、2、1,總合為n(n-1)/2次的比較與交換. 檔名 : 1darray6.c 執行結果: Loop 0 : 6 15 13 27 33 Loop 1 : 6 13 15 27 33 Loop 2 : 6 13 15 27 33 Loop 3 : 6 13 15 27 33 缺點 : 兩個迴圈就可完成工作, 此程式仍然執行四次迴圈. 註一 : 泡沫排序法是相鄰的兩數加以比較後加以互換. 參考來源 : Borland C++入門與應用徹底剖析(P.204)

Internal Sorting---Bubble Sort Example a[0] a[1] a[2] a[3] a[4] a[0] a[1] a[2] a[3] a[4] i=0 j=0 j=1 j=2 j=3 i=1 j=0 j=1 j=2 j=3 5 26 81 7 63 5 26 7 63 81 5 26 81 7 63 5 7 26 63 81 5 26 7 81 63 5 7 26 63 81 5 26 7 63 81 5 7 26 63 81 a[0] a[1] a[2] a[3] a[4] a[0] a[1] a[2] a[3] a[4] i=3 j=0 j=1 j=2 j=3 i=2 j=0 j=1 j=2 j=3 5 7 26 63 81 5 7 26 63 81 5 7 26 63 81 5 7 26 63 81 5 7 26 63 81 5 7 26 63 81 5 7 26 63 81 5 7 26 63 81

Internal Sorting---Selection Sort 從排序的元素中選出最小的一個元素與第一個元素交換。然後從剩下的元素中再選出最小的元素和第二個元素交換,如此重覆下去,直到最後一個元素為止。

Internal Sorting---Selection Sort 例子:我們要將以下的字元依字典順序排序 l, k, j, o, a, b 需要兩層迴圈,外層迴圈執行交換過程,內層迴圈每次找出最小的元素. 執行效率為O(n2),迴圈執行次數與Bubble Sort相同. l k j o a b a k j o l b 第一次交換 第二次交換 第三次交換 第四次交換 第五次交換 a b j o l k a b j o l k a b j k l o a b j k l o

Selection Sort Example void select(char *string,int count) { int pos; /*目前最小的字元*/ int i,j; char temp; for ( i = 0; i < count - 1; i++ ) /*第一層迴圈,執行交換*/ pos = i; temp = string[pos]; for ( j = i + 1; j < count; j++ ) /*第二層迴圈,找尋最小的字元*/ if ( string[j] < temp ) /*是否更小*/ pos = j; /*新的最小字元*/ temp = string[j]; } string[pos] = string[i]; /*交換兩字元*/ string[i] = temp; printf("輸出結果: [%s]\n",string); /*列印交換後字串 */

Internal Sorting---Insertion Sort 將一個記錄插入到一串排序好的記錄。 先將前兩個元素排序,然後將第三個元素插入排序好的兩個元素,使其三個元素仍是由小至大排序。 重覆操作直到所有元素都排好。 優點: 當字串幾乎排序好時,插入排序法的時間就比較短。 不會影響相同元素的資料順序。 缺點:執行效率慢,不適合資料量龐大時使用。

Internal Sorting---Insertion Sort 例子:我們要將以下的字元依字典順序排序 l, k, j, o, a, b 執行效率為O(n2),why? 第一層迴圈需插入n-1個元素,第二層回圈將執行1,2,3…n-2,n-1次,合計為n(n-1)/2. 最初陣列 第一次 第二次 第三次 第四次 第五次 l k j o a b k l j o a b j k l o a b j k l o a b a j k l o b a b j k l o

Insertion Sort Example #include <stdlib.h> #define MAX 20 /*最大字串長度*/ void insert(char *string,int count) { int i,j; char temp; for ( i = 1; i < count; i++ ) /* 第一層迴路,插入元素至字串中*/ temp = string[i]; /*建立初值*/ j = i - 1; /*開始位置*/ /*空出插入位置,將插入元素放在正確位置*/ while ( j >= 0 && temp < string[j] ) string[j+1] = string[j]; j--; } string[j+1] = temp; /*插入字元*/ printf("輸出結果: [%s]\n",string); /*列印交換後字串*/

Quick Sort(高等排序) 將資料分割 最好的情況就是找出中間值,但是並不容易,所以有兩種常用方式: 選擇一個元素為分割標準,將資料分成兩半。 其中一半是比標準值大的元素,另外一半是比較小或相等的元素。 接著每一半元素使用相同方法分割,直到無法再分割為止。 最好的情況就是找出中間值,但是並不容易,所以有兩種常用方式: 選取陣列元素的第一個. 選取陣列元素最中間的元素.

因為i的值已經大於j的值,所以將選擇值與j互換 Quick Sort d e a c f b h g 0 1 2 3 4 5 6 7 d e a c f b h g 交換[1],[5] i j d b a c f e h g 因為i的值已經大於j的值,所以將選擇值與j互換 j i c b a d f e h g 對這兩個部份再繼續分割 第一部份 都比d小 第二部份 都比d大

Quick Sort c b a a b c e f h g g h a b c d e f g h 第一部份分割後的結果 第二部份 第二部份分割的結果 e f h g 最後的結果 第一部份 第二部份 g h a b c d e f g h 第一部份 第二部份

Quick Sort void q_sort(char *string,int left,int right) { char partition; /*分割元素*/ char temp; int i,j,k; if ( left < right ) /*是否繼續分割*/ i = left; /*分割的最左*/ j = right + 1; /*分割的最右*/ partition = string[left]; /*取第一個元素*/ do { do { /*從左往右找,直到大於等於par才停止*/ i++; } while( string[i] < partition ); do { /*從右往左找,直到小於等於par才停止*/ j--; } while( string[j] > partition ); if ( i < j ) temp = string[i]; /*若有找到滿足前述兩項條件者,就交換資料*/ string[i] = string[j]; string[j] = temp; } } while( i < j ); temp= string[left]; /*若i>=j 則交換j與left的資料*/ string[left] = string[j]; string[j] = temp; printf("輸出結果: "); for ( k = left; k <= right; k++) /*列印處理字串 */ printf("%c",string[k]); printf("\n"); /*換行*/ q_sort(string,left,j-1); /*遞迴呼叫處理第一部份*/ q_sort(string,j+1,right);/*遞迴呼叫處理第二部份*/ }

Quick Sort void quick(char *string,int n) { q_sort(string,0,n-1); } void main() char string[MAX]; /*字串陣列*/ int count; /*字串長度*/ printf("輸入欲排序的字串 ==> "); gets(string); /*讀取字串*/ count = strlen(string); /*計算字串長度*/ quick(string,count); /*快速排序法*/ /*列印排序後字串*/ printf("\n輸出排序結果: [%s]\n",string);

Heap Sort Heap本身是一棵二元樹,且滿足下列的條件: Heap處理步驟: 每個父節點都比其左,右子節點的資料大或相等。 Step1:由二元樹建立heap. Step2:輸出heap的樹根,將剩下的二元樹節點重建為heap. Step3:重覆操作直到所有節點都已輸出.

索引值從1開始, 節點n的左子節點為2*n,右子節點為2*n+1. Heap Sort 有一棵二元樹如下圖所示: (1) 5 (2) (3) 6 4 (4) (5) (6) (7) 8 2 3 7 (8) (9) 1 9 索引值從1開始, 節點n的左子節點為2*n,右子節點為2*n+1. 儲存方式如下圖所示: 1 2 3 4 5 6 7 8 9 5 6 4 8 2 3 7 1 9

Heap Sort---調整 由中間往回調整. 如果陣列有n個元素,其中間的位置是n/2. 此位置的節點保證是葉節點的上一層,所以在調整的過程,可以處理所有的葉節點. 接著再作如下列的步驟: Step1:找出此節點的左,右節點中資料最大的節點與此節點相比較. (1)如果此節點較大,則不調整. (2)如果此節點比較小,則交換兩節點的資料,然後以交換後的父節點重覆Step1.

(1) (1)首先往回調整的索引值是4(9/2).此時的右子節點比它大,所以作交換. 5 (2) (3) 6 4 (4) (5) (6) (7) 8 2 3 7 (8) (9) 1 9 (1) (2)因為索引值9的節點無子節點,所以結束. 5 (2) (3) 6 4 (4) (5) (6) (7) 9 2 3 7 (8) (9) 1 8

(3)接著處理索引值3的節點.因為右節點較大,所以作交換. (1) (3)接著處理索引值3的節點.因為右節點較大,所以作交換. 5 (2) (3) 6 4 (4) (5) (6) (7) 9 2 3 7 (8) (9) 1 8 (1) (4)因為索引值7的節點無子節點,所以結束. 5 (2) (3) 6 7 (4) (5) (6) (7) 9 2 3 4 (8) (9) 1 8

(5)接著處理索引值2的節點.因為右節點較大,所以作交換. 5 (2) (3) (1) (5)接著處理索引值2的節點.因為右節點較大,所以作交換. 5 (2) (3) 6 7 (4) (5) (6) (7) 9 2 3 4 (8) (9) 1 8 (1) (6)因為索引值4的節點有子節點,所以繼續比較,結果左子節點8比較大,作交換. 5 (2) (3) 9 7 (4) (5) (6) (7) 6 2 3 4 (8) (9) 1 8

(7)接著處理索引值1的節點.因為左節點較大,所以作交換. 5 (2) (3) (1) (7)接著處理索引值1的節點.因為左節點較大,所以作交換. 5 (2) (3) 9 7 (4) (5) (6) (7) 8 2 3 4 (8) (9) 1 6 (1) (8)因為索引值2的節點有子節點,所以繼續比較子節點,結果左子節點較大,作交換. 9 (2) (3) 5 7 (4) (5) (6) (7) 8 2 3 4 (8) (9) 1 6

(9)接著處理索引值4的節點.因為右節點較大,所以作交換. 9 (2) (3) (1) (9)接著處理索引值4的節點.因為右節點較大,所以作交換. 9 (2) (3) 8 7 (4) (5) (6) (7) 5 2 3 4 (8) (9) 1 6 (1) (10)因為索引值9的節點沒有子節點,所以結束調整. 9 (2) (3) 8 7 (4) (5) (6) (7) 6 2 3 4 (8) (9) 1 5

Heap Sort #include <stdlib.h> /* 調整累堆 */ /* 調整累堆 */ void adjust_heap(int *heap,int root,int len) { int done; /* 是否可結束的變數 */ int j; int temp; j = 2 * root; /* 子節點指標 */ temp = heap[root]; /* 累堆的根值 */ done = 0; /* 建立變數 */ while ( j <= len && !done ) /* 主迴路 */ if ( j < len ) /* 從左,右子節點中找最大的子節點*/ if ( heap[j] < heap[j+1] ) j++; /* 下一節點 */ if ( temp >= heap[j] ) /* 比較樹根值 */ done = 1; /* 結束 */ else heap[j/2] = heap[j]; /* 父節點是目前節點 */ j = 2 * j; /* 其子節點 */ } heap[j/2] = temp; /*父節點為根值 */ /* 累堆排序 */ void heap(int *heap,int len) { int i,j,temp; for ( i = ( len / 2 ); i >= 1; i-- ) /*將二元樹轉成累堆*/ adjust_heap(heap,i,len); printf("\n累堆的內容: "); for ( j = 1; j < 10; j++ ) /*列出累堆的內容 */ printf("[%d]",heap[j]); printf("\n"); /*換行 */ for ( i = len - 1; i >= 1; i-- ) /*累堆排序主迴路*/ temp = heap[i+1]; /*交換最後元素:heap[1]與heap[i+1]*/ heap[i+1] = heap[1]; heap[1] = temp; adjust_heap(heap,1,i); /*重建累堆 */ printf("\n處理內容: "); for ( j = 1; j < 10; j++ ) /*列出處理內容*/ }

Heap Sort /* 主程式: 將陣列資料用累堆排序法來排序. */ int main() { /*二元樹節點資料*/ /* 主程式: 將陣列資料用累堆排序法來排序. */ int main() { /*二元樹節點資料*/ int data[10] = { 0, 5, 6, 4, 8, 2, 3, 7, 1, 9 }; int i; printf("二元樹的內容: "); for ( i = 1; i < 10; i++ ) /* 列出二元樹內容 */ printf("[%d]",data[i]); heap(data,9); /* 累堆排序法 */ printf("\n\n輸出排序結果: "); for ( i = 1; i < 10; i++ ) /* 列出最後內容 */ printf("\n"); system("pause"); return 0; }

Heap Sort Result

Merge Sort 外部儲存裝置最常用的排序方法. Step1:將資料分成數個檔案,其中大小是可以載入記憶體空間,然後使用適當的內部排序執行,最後將排序完的資料寫回檔案. Step2:將Step1建立的檔案,二個二個合併成為一個檔案,等到全部的檔案都合併成一個檔案,就完成排序.

Merge Sort 1 2 3 4 5 6 7

Merge Sort 1 4 5 6 2 3 7 8 檔案1 檔案2 1 2 3 4

Merge Sort void merge(FILE *merge,FILE *sort1,FILE *sort2,int len) { int s1=0,s2=0; /* 資料計數 */ char c,c1,c2; c1 = getc(sort1); /* 讀取第一個檔案 */ c2 = getc(sort2); /* 讀取第二個檔案 */ while ( 1 ) if ( c1 < c2 ) /* 比較兩個值*/ /* 第一個檔案小, 存入主檔 */ putc(c1,merge); s1++; if ( s1 < len ) /* 是否未讀完 */ c1 = getc(sort1); /* 繼續讀取第一個檔案*/ else break; /* 第一個檔案已讀完,跳出迴路 */ } /* 第二個檔案小, 存入主檔 */ putc(c2,merge); s2++; if ( s2 < len ) /* 是否未讀完 */ c2 = getc(sort2); /* 讀取第二個檔案 */ break; } } /*第二個檔案已讀完, 跳出迴路*/ /* 第一個檔案是否是已讀取的最後一筆 */ if ( s1 < len ) { putc(c1,merge); /* 存入主檔*/ s1++; /* 計數加一*/ } /* 第二個檔案是否是已讀取的最後一筆 */ if ( s2 < len ) putc(c2,merge); /* 存入主檔 */ s2++; /* 第一個檔案 */ while ( s1 < len ) /* 取出剩下的資料 */ c = getc(sort1); /* 讀取第一個檔案 */ putc(c,merge); /* 存入主檔 */ s1++; /* 第二個檔案 */ while ( s2 < len ) /* 取出剩下的資料 */ c = getc(sort2); /* 讀取第二個檔案*/ putc(c,merge); /* 存入主檔 */

Merge Sort 請先建立好三個檔:sort1.txt,sort2.txt,result.txt /*合併排序*/ #include <stdio.h> #define LEN 4 /* 最大元素個數*/ /* 主程式: 讀取兩個檔案內容, 接著用合併排序法來排序. */ int main() { FILE *fp; /* 主檔指標 */ FILE *fp1; /* 第一資料檔案指標*/ FILE *fp2; /* 第二資料檔案指標 */ fp = fopen("result.txt","r+"); /* 開啟主檔 */ if ( fp == NULL ) printf("主檔開啟錯誤! \n"); else fp1 = fopen("sort1.txt","r+"); /*開啟第一資料檔案*/ if ( fp1 == NULL ) printf("第一資料檔開啟錯誤! \n"); fp2 = fopen("sort2.txt","r+"); /*開啟第二資料檔案*/ if ( fp2 == NULL ) printf("第二資料檔開啟錯誤! \n"); printf("資料處理中, 請稍待. . . \n"); merge(fp,fp1,fp2,LEN); /*合併排序法*/ printf("資料處理完成! \n"); fclose(fp); /* 關檔 */ fclose(fp1); fclose(fp2); } } system("pause"); return 0; } 請先建立好三個檔:sort1.txt,sort2.txt,result.txt Sort1.txt中存入1456四筆資料 Sort2.txt中從入2378四筆資料