程式扎記: [ 資料結構 小學堂 ] 排序 : 堆積排序法

標籤

2010年11月25日 星期四

[ 資料結構 小學堂 ] 排序 : 堆積排序法

前言 :
堆積排序法 可以算是 選擇排序法 的改進版, 它可以減少在選擇排序中的比較次數, 進而減少排序時間. 堆積排序法使用到 二元樹 的技巧, 它是利用堆積樹來完成排序. 堆積是一種特殊的二元樹, 可以分為最大堆積樹及最小堆積樹兩種. 而最大堆積數滿足以下3 個條件 :
1. 它是一個完整二元樹.
2. 所有節點的值都大於或等於它右子點的值.
3. 樹根是堆積樹中最大的.

而最小堆積數則具備以下3個條件 :
1. 它是一個完整二元樹.
2. 所有節點的值都小於或等於它右子點的值.
3. 樹根是堆積樹中最小的.

在開始討論堆積排序法前, 先介紹如何將二元樹轉換成堆積數 (Heap Tree). 將以下面實例進行說明 :

Step1 : A[0] = 32 為樹根, A[1] = 17 < A[0] = 32, 不用交換.
Step2 : A[2] = 16 < A[0], 不用交換
Step3 : A[3] = 24 > A[1] = 17 故交換. A[3] = 24 < A[0] = 32, 不用交換

Step4 : A[4] = 35 > A[1] = 24 故交換, A[1] = 35 > A[0] 故交換

Step5 : A[5] = 87 > A[2] = 16 故交換, A[2] = 87 > A[0] = 35 故交換

Step6 : A[6] = 65 > A[2] = 35 故交換, A[2] = 65 < A[0] = 87 故不必交換. 最後 A[7] 與 A[8] 都不必交換, 所以下面為最後的堆積數.

藉由上面示範由二元樹轉換成堆積數, 可以知道堆積樹並非唯一. 至於堆積排序法的演算法就是從樹根取出最大值後, 再從原來的堆積數重新建立堆積數, 然後再依序從樹根取出值來得到排序的結果, 直到原來的堆積數元素為零為止.

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

範例代碼 :
  1. #include   
  2. #include
  3.   
  4. using namespace std;  
  5.   
  6. struct BenchMark {  
  7.     int swapTime;  // Swap Time  
  8.     int verifyTime;  // Verify Time  
  9.     double cTime;  // Consumed Time  
  10. };  
  11. void _swapValue(int *a, int *b) {  
  12.     int tmp = *a;  
  13.     *a = *b;  
  14.     *b = tmp;  
  15. }  
  16.   
  17. int _gp(int v) {  
  18.     if(v>0) {  
  19.         int tmp = v/2;  
  20.         if(v%2==0)  
  21.             return tmp-1;  
  22.         else  
  23.             return tmp;  
  24.     }     
  25.     return 0;  
  26. }  
  27.   
  28. BenchMark _ad_heap(int data[], int i, int size) {  
  29.     BenchMark bm;  
  30.     int vt=0, st=0;  
  31.     for(int j=i; j>0; j--) {  
  32.         int tmp = j;  
  33.         int k = _gp(j);  
  34.         while(k>=0) {  
  35.             vt++;  
  36.             if(data[tmp] > data[k]) {  
  37.                 st++;  
  38.                 _swapValue(&data[tmp], &data[k]);  
  39.                 tmp = k;  
  40.             } else {  
  41.                 break;  
  42.             }  
  43.             if(k==0)  
  44.                 break;  
  45.             k = _gp(k);  
  46.         }  
  47.     }  
  48.     bm.swapTime = st;  
  49.     bm.verifyTime = vt;  
  50.     return bm;  
  51. }  
  52.   
  53. BenchMark heapSort(int data[], int size) {  
  54.     BenchMark bm;  
  55.     BenchMark tmpBM;  
  56.     bm.swapTime = 0;  
  57.     bm.verifyTime = 0;  
  58.     /*建立堆積樹*/  
  59.     tmpBM = _ad_heap(data, size, size);  
  60.     bm.swapTime+= tmpBM.swapTime;  
  61.     bm.verifyTime+=tmpBM.verifyTime;  
  62.     printf("堆積樹內容: \n");  
  63.     for(int i=0; i
  64.         printf("%2d ", data[i]);  
  65.     }  
  66.     printf("\n");  
  67.     for(int i=(size-1); i>=0; i--) {  
  68.         _swapValue(&data[i], &data[0]);  
  69.         tmpBM = _ad_heap(data, i-1,size);  
  70.         bm.swapTime+= tmpBM.swapTime;  
  71.         bm.verifyTime+=tmpBM.verifyTime;  
  72.     }  
  73.     return bm;  
  74. }  
  75.   
  76. void _showData(int data[], int size) {  
  77.     for(int i=0; i
  78.         printf("%2d ", data[i]);  
  79.     }  
  80.     printf("\n");  
  81. }  
  82.   
  83. #define HEAP_DATA_SIZE 9  
  84. void main(bool b) {  
  85.     int data[HEAP_DATA_SIZE] = {32171624358765412};  
  86.     printf("原始資料為: ");  
  87.     _showData(data, HEAP_DATA_SIZE);  
  88.     BenchMark bm = heapSort(data, HEAP_DATA_SIZE);  
  89.     cout << "堆積排序: " << endl;  
  90.     _showData(data, HEAP_DATA_SIZE);  
  91.     printf("Swap time: %d\n", bm.swapTime);  
  92.     printf("Verify time: %d\n", bm.verifyTime);  
  93. }  
執行結果 :
原始資料為: 32 17 16 24 35 87 65 4 12
堆積樹內容:
87 35 65 24 17 32 16 4 12
堆積排序:
4 12 16 17 24 32 35 65 87
Swap time: 21
Verify time: 44

Ruby Sample Code
- alg/sort/SortMod.rb 
  1. module SortMod    
  2.   @@des_cmp = lambda{ |a,b| return a <=> b}  
  3.   @@asc_cmp = lambda{ |a,b| return b <=> a}  
  4.     
  5.   # Open API: Sorting given array.  
  6.   def sort(ary, desc=true)  
  7.     nary = []  
  8.     ary.each{ |item|; nary << item; }  
  9.     csort(nary, desc ? @@des_cmp : @@asc_cmp)  
  10.     nary  
  11.   end  
  12.     
  13.   # Customized sorting algorithm.  
  14.   def csort(ary, cmp)  
  15.     raise RuntimeError, "Muse implement method!"  
  16.   end  
  17.     
  18.   # Swap ary[i] with ary[j]  
  19.   def swap(ary, i, j)  
  20.     ary[i], ary[j] = ary[j], ary[i]  
  21.   end  
  22.     
  23.   # Open API: In place sorting on given array  
  24.   def sort?(ary, cmp, desc=true)      
  25.     csort(ary, cmp, desc ? @@des_cmp : @@asc_cmp)  
  26.     cmp  
  27.   end  
  28.     
  29.   public :sort, :sort?  
  30.   protected :csort, :swap    
  31. end  
- alg/sort/HeapSort.rb 
  1. require "alg/sort/SortMod"  
  2.   
  3. class HeapSort  
  4.   # http://localhost/jforum/posts/list/963.page  
  5.   include SortMod  
  6.     
  7.   # Get Parent  
  8.   #             0  
  9.   #           1   2  
  10.   #          3 4 5 6  
  11.   #  p = (c-1)/2  
  12.   #  c=1 -> (1-1)/2 = 0  
  13.   #  c=2 -> (2-1)/2 = 0  
  14.   #  c=3 -> (3-1)/2 = 1  
  15.   #  c=4 -> (4-1)/2 = 1  
  16.   #  c=5 -> (5-1)/2 = 2  
  17.   #  c=6 -> (6-1)/2 = 2    
  18.   @@GP=lambda{|c| (c-1)/2}  
  19.     
  20.   # Get Child  
  21.   #             0  
  22.   #           1   2  
  23.   #          3 4 5 6  
  24.   # c = (p*2+1, p*2+2)  
  25.   # p=0 -> 0*2+1=10*2+2=2  
  26.   # p=1 -> 1*2+1=31*2+2=4  
  27.   # p=2 -> 2*2+1=52*2+2=6  
  28.   @@GC=lambda{|p| [p*2+1,p*2+2]}       
  29.       
  30.   # Build heap-tree  
  31.   def _ad_heap(ary, cmp, size)  
  32.     (size-1).downto(1do |i|  
  33.       p=@@GP.call(i)  
  34.       while p>=0  
  35.         if cmp.call(ary[i], ary[p])==1  
  36.           swap(ary, i, p)  
  37.           i=p  
  38.           p=@@GP.call(p)  
  39.         else  
  40.           break  
  41.         end  
  42.       end  
  43.     end  
  44.   end  
  45.     
  46.   def csort(ary, cmp)  
  47.     if ary.size > 1  
  48.       ary.size.downto(2do |i|  
  49.         _ad_heap(ary, cmp, i)  
  50.         #printf("HeapTree(%d)=%s\n", i, ary)  
  51.         swap(ary, 0, i-1)  
  52.       end        
  53.     end  
  54.     ary   
  55.   end  
  56. end  
- Demo Code 
  1. require "alg/sort/HeapSort"  
  2.   
  3. printf("Heap Sorting Demo:\n")  
  4. heapSort = HeapSort.new  
  5. printf("Original ary: %s\n", a)  
  6. printf("After sort(desc): %s\n", heapSort.sort(a, false))  
  7. printf("After sort(asc) : %s\n", heapSort.sort(a, true))  
  8. printf("Original ary: %s\n\n", a)  
Execution result: 
Heap Sorting Demo:
Original ary: [2, 5, 9, 7, 6, 4, 8, 1, 3]
After sort(desc): [9, 8, 7, 6, 5, 4, 3, 2, 1]
After sort(asc) : [1, 2, 3, 4, 5, 6, 7, 8, 9]
Original ary: [2, 5, 9, 7, 6, 4, 8, 1, 3]

補充說明 :
Wiki : Heapsort
Heapsort is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantage of a more favorable worst-case Θ(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.


沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!