Quick Sort
2009/09/22 16:45
瀏覽4,300
迴響0
推薦0
引用0
Quick Sort
qucik sort 的基本想法為：挑選中間的 element 來做為比較與分割的基準點，據此將原集合分割成左集合與右集合，我們的目標是要先確保左集合的每個 element 都不大於基準點的 element、以及右集合的每個 element 皆大於基準點的 element 之後，再根據基準點將原集合分割成兩個子集，每個子集再分別去執行基準點的挑選、比較以及分割的運作，如此反覆地循環運作，直到子集小到不需要再做分割即可迎刃而解時停止。
程式解說：quick_sort_on_int.c
本程式的主要目的為：透過 quick sort 的實作，引領讀者去體會 divide andconqure 的思惟以及 array 與 pointer 的用法。
由於分割點的選擇會影響 quick sort 的執行效率，且其最差的情況是發生在分割點恰好是該輪集合的最大值或最小值時，所以我們要想辦法避開這種情況。據此，我們使用 median of three 的挑選法來做為分割點的選擇機制，它的挑選方式為：以 array 的第一個、中間的以及最後一個 element 為候選者，並依三者的大小做排序，最後選出其順序位於中間的 element。
當集合只有兩個或三個 element 時，就直接對它們做排序，排完就解掉一個 sub-problem，因此不需要再做分割與呼叫自己，直接做 return 即可 (line 29 至 33、line 56 至 57)。
由於傳統的 quick sort 之實作程式都是將分割點的 element (稱之為 pivot) 留在原地，但如此為之則該 element 還會在後續的排序過程中被當成排序的對象，因此我們採用「將 pivot 調到第一個位置」的做法 (line 62)，讓它做為兩個集合的比較基準，但是不要去干擾兩個集合的對調作業，待兩個集合中的 element 都各就定位之後 (即 scan_up 與 scan_down 碰面之後)，再將 pivot 調到它最終的位置 (line 87；雖然此時整個 quick sort 尚未結束，但我們已能確定 scan_down 就是它的最終位置，因為在 scan_up 與 scan_down 碰完面之後，scan_down 一定是停在第一個集合中的最後一個 element 上，又已知此時的第一個集合之所有 element 一定是小於或等於 pivot，故 scan_down 就是 pivot 的 final position；這也是接下來的兩個 recursive funciton call 為何將 pivot 排除在外的原因，即 line 90 與 93 的函式呼叫)。
請留意 line 68 的等號是一定要寫的，因為當 scan_up 與 scan_down 指向同一個 element 之際，該 element 尚未與 pivot 做過比較，所以一定要讓 control flow 進入 while loop、讓該 element 與 pivot 進行比較的運作。
由於我們是採用中位數選擇法 (median of three) 來挑選 pivot，所以 pivot 不會是集合中的最大值或最小值，因此 scan_up 與 scan_down 不會在 line 68 至 83 的 while loop 中跑到 array bound 之外；但如果選擇到的 pivot 有可能是集合中的最大值或最小值，則 line 69 與 72 就必須加上 array bound 的測試，以避免 scan_up 與 scan_down 跑到 array bound 之外。
筆者在此將 quick sort 的某次執行過程繪製成兩幅圖，以呈現其 activation flow 的流轉過程、以及 scan_up 與 scan_down 在每輪中的交會過程，讀者若能將之與實作程式做番對照，則對 quick sort 必能有所體悟 (請參考圖 5.2-5 與圖 5.2-6)。
程式列表：quick_sort_on_int.c
001: #include
002: #include
003: #include
004:
005: void
006: PerformQSort(int data[], int first, int last);
007:
008: static void
009: Swap(int *a, int *b);
010:
011: void PerformQSort(int data[], int first, int last)
012: {
013: int pivot, scan_up, scan_down;
014: int middle = (first + last) >> 1L;
015:
016: if (first == last) /* only one element */
017: return;
018:
019: /*
020: ** Just in case if caller gives the parameters in
021: ** reverse order.
022: */
023: if (first > last) {
024: scan_up = first;
025: first = last;
026: last = scan_up;
027: }
028:
029: if (first + 1 == last) { /* only two elements */
030: if (data[first] > data[last])
031: Swap(data + first, data + last);
032: return;
033: }
034:
035: /*
036: ** We are sure now that there are at least three elements.
037: **
038: ** We plan to select the pivot by median-of-three scheme,
039: ** so we choose the first, middle and last elements as the
040: ** candidates and sort them.
041: */
042:
043: if (data[middle] < data[first])
044: Swap(&data[first], &data[middle]);
045:
046: if (data[last] < data[first])
047: Swap(data + first, data + last);
048:
049: if (data[last] < data[middle])
050: Swap(data + middle, data + last);
051:
052: /*
053: ** If there are exactly three elements, then we have finished
054: ** the sorting job.
055: */
056: if (first + 2 == last)
057: return;
058:
059: /*
060: ** Place the pivot at the front.
061: */
062: Swap(data + first, data + middle);
063: pivot = data[first];
064:
065: scan_up = first + 1;
066: scan_down = last;
067:
068: while (scan_up <= scan_down) {
069: while (data[scan_up] < pivot)
070: scan_up++;
071:
072: while (data[scan_down] > pivot)
073: scan_down--;
074:
075: if (scan_up < scan_down) {
076: Swap(data + scan_up, data + scan_down);
077:
078: scan_up++;
079: scan_down--;
080: }
081: else
082: break;
083: }
084: /*
085: ** Place pivot in its final position.
086: */
087: Swap(data + first, data + scan_down);
088:
089: if (first < scan_down - 1)
090: PerformQSort(data, first, scan_down - 1);
091:
092: if (scan_down + 1 < last)
093: PerformQSort(data, scan_down + 1, last);
094: }
095:
096: static void
097: Swap(int *a, int *b)
098: {
099: int temp;
100:
101: temp = *a;
102: *a = *b;
103: *b = temp;
104: }
程式列表：exercise_quick_sort_on_int.c
01: #include
02: #include
03: #include
04:
05: #define DATA_COUNT 16
06:
07: extern void
08: PerformQSort(int data[], int first, int last);
09:
10: int
11: main(int argc, char *argv[])
12: {
13: int data[DATA_COUNT], i, val;
14:
15: srand((unsigned int)time(NULL));
16: printf("randomly generated integers:\n\n");
17: for (i = 0; i < DATA_COUNT; ) {
18: data[i] = rand() % 200;
19: printf("%3d\t", data[i]);
20: i++;
21:
22: if (0 == i % 4)
23: printf("\n");
24: }
25: printf("\n\n");
26:
27: PerformQSort(data, 0, DATA_COUNT - 1);
28:
29: printf("after the quick sort:\n\n");
30: for (i = 0; i < DATA_COUNT; ) {
31: printf("%3d\t", data[i]);
32: i++;
33:
34: if (0 == i % 4)
35: printf("\n");
36: }
37:
38: return 0;
39: }
執行結果：exercise_quick_sort_on_int
randomly generated integers:
143 67 145 54
123 80 93 60
161 183 113 11
60 36 138 180
after the quick sort:
11 36 54 60
60 67 80 93
113 123 138 143
145 161 180 183
qucik sort 的基本想法為：挑選中間的 element 來做為比較與分割的基準點，據此將原集合分割成左集合與右集合，我們的目標是要先確保左集合的每個 element 都不大於基準點的 element、以及右集合的每個 element 皆大於基準點的 element 之後，再根據基準點將原集合分割成兩個子集，每個子集再分別去執行基準點的挑選、比較以及分割的運作，如此反覆地循環運作，直到子集小到不需要再做分割即可迎刃而解時停止。
程式解說：quick_sort_on_int.c
本程式的主要目的為：透過 quick sort 的實作，引領讀者去體會 divide andconqure 的思惟以及 array 與 pointer 的用法。
由於分割點的選擇會影響 quick sort 的執行效率，且其最差的情況是發生在分割點恰好是該輪集合的最大值或最小值時，所以我們要想辦法避開這種情況。據此，我們使用 median of three 的挑選法來做為分割點的選擇機制，它的挑選方式為：以 array 的第一個、中間的以及最後一個 element 為候選者，並依三者的大小做排序，最後選出其順序位於中間的 element。
當集合只有兩個或三個 element 時，就直接對它們做排序，排完就解掉一個 sub-problem，因此不需要再做分割與呼叫自己，直接做 return 即可 (line 29 至 33、line 56 至 57)。
由於傳統的 quick sort 之實作程式都是將分割點的 element (稱之為 pivot) 留在原地，但如此為之則該 element 還會在後續的排序過程中被當成排序的對象，因此我們採用「將 pivot 調到第一個位置」的做法 (line 62)，讓它做為兩個集合的比較基準，但是不要去干擾兩個集合的對調作業，待兩個集合中的 element 都各就定位之後 (即 scan_up 與 scan_down 碰面之後)，再將 pivot 調到它最終的位置 (line 87；雖然此時整個 quick sort 尚未結束，但我們已能確定 scan_down 就是它的最終位置，因為在 scan_up 與 scan_down 碰完面之後，scan_down 一定是停在第一個集合中的最後一個 element 上，又已知此時的第一個集合之所有 element 一定是小於或等於 pivot，故 scan_down 就是 pivot 的 final position；這也是接下來的兩個 recursive funciton call 為何將 pivot 排除在外的原因，即 line 90 與 93 的函式呼叫)。
請留意 line 68 的等號是一定要寫的，因為當 scan_up 與 scan_down 指向同一個 element 之際，該 element 尚未與 pivot 做過比較，所以一定要讓 control flow 進入 while loop、讓該 element 與 pivot 進行比較的運作。
由於我們是採用中位數選擇法 (median of three) 來挑選 pivot，所以 pivot 不會是集合中的最大值或最小值，因此 scan_up 與 scan_down 不會在 line 68 至 83 的 while loop 中跑到 array bound 之外；但如果選擇到的 pivot 有可能是集合中的最大值或最小值，則 line 69 與 72 就必須加上 array bound 的測試，以避免 scan_up 與 scan_down 跑到 array bound 之外。
筆者在此將 quick sort 的某次執行過程繪製成兩幅圖，以呈現其 activation flow 的流轉過程、以及 scan_up 與 scan_down 在每輪中的交會過程，讀者若能將之與實作程式做番對照，則對 quick sort 必能有所體悟 (請參考圖 5.2-5 與圖 5.2-6)。
程式列表：quick_sort_on_int.c
001: #include
002: #include
003: #include
004:
005: void
006: PerformQSort(int data[], int first, int last);
007:
008: static void
009: Swap(int *a, int *b);
010:
011: void PerformQSort(int data[], int first, int last)
012: {
013: int pivot, scan_up, scan_down;
014: int middle = (first + last) >> 1L;
015:
016: if (first == last) /* only one element */
017: return;
018:
019: /*
020: ** Just in case if caller gives the parameters in
021: ** reverse order.
022: */
023: if (first > last) {
024: scan_up = first;
025: first = last;
026: last = scan_up;
027: }
028:
029: if (first + 1 == last) { /* only two elements */
030: if (data[first] > data[last])
031: Swap(data + first, data + last);
032: return;
033: }
034:
035: /*
036: ** We are sure now that there are at least three elements.
037: **
038: ** We plan to select the pivot by median-of-three scheme,
039: ** so we choose the first, middle and last elements as the
040: ** candidates and sort them.
041: */
042:
043: if (data[middle] < data[first])
044: Swap(&data[first], &data[middle]);
045:
046: if (data[last] < data[first])
047: Swap(data + first, data + last);
048:
049: if (data[last] < data[middle])
050: Swap(data + middle, data + last);
051:
052: /*
053: ** If there are exactly three elements, then we have finished
054: ** the sorting job.
055: */
056: if (first + 2 == last)
057: return;
058:
059: /*
060: ** Place the pivot at the front.
061: */
062: Swap(data + first, data + middle);
063: pivot = data[first];
064:
065: scan_up = first + 1;
066: scan_down = last;
067:
068: while (scan_up <= scan_down) {
069: while (data[scan_up] < pivot)
070: scan_up++;
071:
072: while (data[scan_down] > pivot)
073: scan_down--;
074:
075: if (scan_up < scan_down) {
076: Swap(data + scan_up, data + scan_down);
077:
078: scan_up++;
079: scan_down--;
080: }
081: else
082: break;
083: }
084: /*
085: ** Place pivot in its final position.
086: */
087: Swap(data + first, data + scan_down);
088:
089: if (first < scan_down - 1)
090: PerformQSort(data, first, scan_down - 1);
091:
092: if (scan_down + 1 < last)
093: PerformQSort(data, scan_down + 1, last);
094: }
095:
096: static void
097: Swap(int *a, int *b)
098: {
099: int temp;
100:
101: temp = *a;
102: *a = *b;
103: *b = temp;
104: }
程式列表：exercise_quick_sort_on_int.c
01: #include
02: #include
03: #include
04:
05: #define DATA_COUNT 16
06:
07: extern void
08: PerformQSort(int data[], int first, int last);
09:
10: int
11: main(int argc, char *argv[])
12: {
13: int data[DATA_COUNT], i, val;
14:
15: srand((unsigned int)time(NULL));
16: printf("randomly generated integers:\n\n");
17: for (i = 0; i < DATA_COUNT; ) {
18: data[i] = rand() % 200;
19: printf("%3d\t", data[i]);
20: i++;
21:
22: if (0 == i % 4)
23: printf("\n");
24: }
25: printf("\n\n");
26:
27: PerformQSort(data, 0, DATA_COUNT - 1);
28:
29: printf("after the quick sort:\n\n");
30: for (i = 0; i < DATA_COUNT; ) {
31: printf("%3d\t", data[i]);
32: i++;
33:
34: if (0 == i % 4)
35: printf("\n");
36: }
37:
38: return 0;
39: }
執行結果：exercise_quick_sort_on_int
randomly generated integers:
143 67 145 54
123 80 93 60
161 183 113 11
60 36 138 180
after the quick sort:
11 36 54 60
60 67 80 93
113 123 138 143
145 161 180 183
你可能會有興趣的文章：
