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四筆資料