喲吼吼吼: 排序法 in C/C++ ( Merge Sort & Heap Sort & Radix Sort )

開發環境: Microsoft C++ 2010 sp1
Merge Sort( 合併排序 ) :

主要演算法假設是，在n段以排序過的資料裡面，要把n段的資料合併並排序成一段，
所以只要每兩段做一次資料的比較並且合併成 n / 2 段，
然後再把n / 2段的資料進行比較與合併成 n / 4 段，
重複以上的過程直到最後剩下一段的資料，最後一段資料即為所求。

下圖為排序順序:

以下為實作的code:

有兩種版本，一為陣列(陣列位置數到快瘋了)，二為遞迴，

陣列:

#include 
#include 

const int BASE = 1000 ;
//快速排序法所需要的比較子
int comp( const void *p , const void *q ) {
 int *_p = (int *)p ;
 int *_q = (int *)q ;
 if ( *_p == *_q )
  return 0 ;
 else {
  if ( *_p < *_q ) return -1 ;
  else return 1 ;
 }
}

void printRange( int *x , int s , int n ) {
 int i ;
 for ( i = s ; i < n ; i++ ) {
  std::cout << x[i] << " ";
 }
 std::cout << std::endl ;
}
int main() {
 int m , n = 100000 - 3, i ;
 //輸入資料
 int *x = new int[1000000] ;
 //暫存資料
 int *y = new int[1000000] ;
 //存放第n個區段裡面有幾筆資料
 int table[ 1000000 / 2 / BASE + 1] ;


 while ( std::cin >> n ) {
  for ( i = 0 ; i < n ; i++ ) {
   std::cin >> x[i] ;
   
   if ( (i+1) % BASE == 0 ) {
    //排序每個區段的資料
    qsort( (void *)( x + ( (i / BASE) * BASE ) ) , BASE , sizeof(int) , comp ) ;
   }
  }

  if ( n % BASE != 0 && n > BASE ) {
   qsort( &x[ (n / BASE) * BASE ] , n % BASE , sizeof(int) , comp ) ;
  }
  //切割splits個BASE大小的區段
  int splits = (int)( (double)n / (double)BASE + 0.5 ) ;
  int runs = 1 , j ;
  int a , b , c ;
  //如果splits > 0才需要Merge
  if ( splits > 0 ) {
   //每個區段為BASE個
   for ( a = 0 ; a < splits ; a++ )
    table[a] = BASE ;
   //如果輸入的資料數不能整除BASE個
   if ( n % BASE != 0 )
    table[splits-1] = n % BASE ;
   //當切割數 > 1時才開始Merge
   while ( splits > 1 ) {
    c = ( splits % 2 == 0 ) ? splits : splits - 1 ;
    //合併 n 個區段至 n / 2個
    for ( m = 0 ; m < c  ; m += 2 ) {
     a = 0 ;
     b = 0 ;
     int cmp1 = x[m * BASE * runs + a] ;
     int cmp2 = x[ (m+1) * BASE * runs + b] ;
     //合併兩個區段
     for ( j = 0 ; a < table[m * runs] || b < table[(m + 1) * runs] ; j++ ) { 
      if ( a == table[m * runs] ) {
       y[j] = cmp2 ;
       cmp2 = x[ (m+1) * BASE * runs + (++b)] ;
      } else if ( b == table[(m + 1) * runs] ) {
       y[j] = cmp1 ;
       cmp1 = x[ m * BASE * runs + (++a)] ;
      } else {
       if ( cmp1 <= cmp2 ) {
        y[j] = cmp1 ;
        cmp1 = x[ m * BASE * runs + (++a)] ;
       } else {
        y[j] = cmp2 ;
        cmp2 = x[ (m+1) * BASE * runs + (++b)] ;
       }
      }
     }
     //放大這個區段的大小
     table[ m * runs ] = table[ m * runs ] + table[ (m + 1) * runs ] ;
     //寫回去原本的陣列裡面
     for ( a = m * BASE * runs , b = 0 ; a < m * BASE * runs + table[ m * runs ] ; a++ , b++)
      x[a] = y[b] ;
    }
    //切割數目 / 2
    splits = (int)((double)splits / 2. + 0.5) ;
    runs *= 2 ;
   }
  } else {
   qsort( x , n , sizeof(int) , comp ) ;
   table[0] = n ;
  }
  printRange( x , 0 , n ) ;
 }
 return 0;
}

遞迴:

#include 
#include 

const int BASE = 1000 ;
//每個切割資料要用快速排序法的比較子
int comp( const void *p , const void *q ) {
 int *_p = (int *)p ;
 int *_q = (int *)q ;
 if ( *_p == *_q )
  return 0 ;
 else {
  if ( *_p < *_q ) return -1 ;
  else return 1 ;
 }
}

//Merge Sort的主函式
void MergeSort( int *x , int numberElement ) {
 if ( numberElement <= BASE ) { //如果切割大小 >= 目前傳入的陣列大小
  qsort( x , numberElement , sizeof(int) , comp ) ;  //使用快速排序法排序整個element( conqure )
 } else {
  int pad =  numberElement % 2 == 0 ? 0 : 1 , i , j = 0 ;
  int *z = x + numberElement / 2 ;
  //左排序(divide)
  MergeSort( x , numberElement / 2 ) ;
  //右排序(divide)
  MergeSort( z , numberElement / 2 + pad ) ;
  //組合在一起
  int a = 0 , b = 0 ;
  const int divide = (numberElement / 2) ;
  //
  const int a_range = divide ;
  const int b_range = divide + pad ;

  int *y = new int[numberElement] ;
  //把左右兩邊各自排序完成的資料使用Merge的規則進行排序
  for ( i = 0 ; i < divide * 2 ; i++ , j++ ) {
   if ( a == a_range ) {
    y[j] = z[b++] ;
   } else if ( b == b_range ) {
    y[j] = x[a++] ;
   } else {
    if ( x[a] < z[b] ) {
     y[j] = x[a++] ;
    } else {
     y[j] = z[b++] ;
    }
   }
  }
  //判斷最後一個
  if ( a != a_range )
   y[j] = x[a] ;
  else if ( b != b_range )
   y[j] = z[b] ;

  //排序後的資料設定回整個陣列
  for ( i = 0 ; i < numberElement ; i++ )
   x[i] = y[i] ;
  delete []y ;
 }
}
//印出陣列內容
void printRange( int *x , int s , int n ) {
 int i ;
 for ( i = s ; i < n ; i++ ) {
  std::cout << x[i] << " ";
 }
 std::cout << std::endl ;
}
int main() {
 int  n , i ;
 int *x = new int[1000000] ;
 

 while ( std::cin >> n ) {
  for ( i = 0 ; i < n ; i++ )
   std::cin >> x[i] ;
  MergeSort( x , n ) ;
  printRange( x , 0 , n ) ;
 }
 return 0;
}

Heap Sort( 堆積排序 ):

Heap為一個完整二元樹( Complete Binary Tree )，
而Min Heap的定義是，父節點會比子節點的值還要小，Max Heap反之，
建構Min Heap的步驟是，逐一把資料加在完整樹的最後一個節點，
再把最後一個節點的值往根接點的方向來比較，把值往上送到保持heap的地方，
以下為建構Min Heap的例子:

如果要用來做排序，直接把heap的根節點輸出，接下來把最後一個節點與根結點交換，
最後再把根結點往下沉到該擺放的地方，如下圖所示，

以下為實作的code:

#include 

void swap( int *a , int *b ) {
 int x = *a ;
 *a = *b ;
 *b = x ; 
}
int main() {
 int *x = new int [1000001] ;
 
 int n , i , m , j ;
 while ( std::cin >> n ) {
  int tmp , parent ;
  //一開始先按照heap的資料結構建立一個min heap
  std::cin >> x[1] ; //第0個位置不使用
  for ( i = 1 ; i < n ; i++ ) {
   std::cin >> m ;   
   //complete binary tree
   x[i + 1] = m ;
   //以輸入的值往完整二元樹的祖先，一直交換找，直到小孩比父節點還要小為止
   tmp = (i + 1) ;
   parent = (i + 1) / 2 ;

   while ( parent > 0 ) {
    //小孩節點與父節點比較小
    if ( x[parent] > x[tmp] ) {
     swap( &x[tmp] , &x[parent] ) ;  //交換兩個數值
    } else //如果小孩比父節點還要小了
     break ;  //不需要往下做下去
    parent /= 2 ; //繼續往下尋找
    tmp /= 2 ;
   }
  }

  for ( j = n - 1 ; j >= 2 ; --j ) {
   //輸出根節點
   std::cout << x[1] << " " ;
   //把根節點替換到這個heap的最後一個位置
   swap( &x[1] , &x[j+1] ) ;
   //把根節點的值往下沉，以保證這個heap結構沒有錯誤
   parent = 1 ;
   tmp = parent * 2 ;
   
   while ( tmp < j ) {
    //找兩個子節點最小的那個
    if ( x[tmp] > x[tmp+1] )
     tmp = tmp + 1 ;
    //如果父節點大於子節點的值
    if ( x[parent] > x[tmp] )
     swap( &x[parent] , &x[tmp] ) ;  //把數值往下替換
    else //如果沒有就節束動作，
     break ;
    //繼續往下沉
    parent = tmp ;
    tmp = parent * 2 ;
   }
  }

  if ( x[1] < x[2] )
   std::cout << x[1] << " " << x[2] ;
  else
   std::cout << x[2] << " " << x[1] ;
  std::cout << std::endl ;
 }
 delete []x ;
 return 0;
}

Radix Sort( 基底排序法 )
其演算法主要的概念為，將整數位元切割成不同的數字，接著按每個位數進行比較，
假設基底為10，要排序的資料分別為 5 3 2 1 30 20 52 11 (x[i], 0 <= i < 8 )，
run1 ( 個位數字 ) :

radix | 0 1 2 3 4 5 6 7 8 9
---------------------------------
5
3
2
1
30
20
52
11
----------------------------------
個數 2 2 2 1 0 1 0 0 0 0
累加個數 y[i] = { 2 , 4 , 6 , 7 , 7 , 8 , 8 , 8 , 8 , 8 } ，這個即為填回去的陣列的最高陣列位置，
用上面的y[i]來進行陣列的重新分配，最原本x最後面開始，

x[7] = 11 ， 11 / 1 % 10 = 1 推論 radix = 1，所以對回去y[i]之後，
11這個值的位置要從7變成 --y[1] = 3，也就是新排列的陣列x' = { X , X , X , 11 , X , X , X , X }，

x[6] = 52 ， 52 / 1 % 10 = 2 推論 radix = 2，所以對回去y[i]之後，
52這個值的位置要從6變成 --y[2] = 5，也就是新排列的陣列x' = { X , X , X , 11 , X , 52 , X , X }，

x[5] = 20 ， 20 / 1 % 10 = 0 推論 radix = 0，所以對回去y[i]之後，
20這個值的位置要從5變成 --y[0] = 1，也就是新排列的陣列x' = { X , 20 , X , 11 , X , 52 , X , X }，

x[4] = 30 ， 30 / 1 % 10 = 0 推論 radix = 0，所以對回去y[i]之後，
30這個值的位置要從4變成 --y[0] = 0，也就是新排列的陣列x' = { 30 , 20 , X , 11 , X , 52 , X , X }，

x[3] = 1 ， 1 / 1 % 10 = 1 推論 radix = 1，所以對回去y[i]之後，
1這個值的位置要從3變成 --y[1] = 2，也就是新排列的陣列x' = { 30 , 20 , 1 , 11 , X , 52 , X , X }，

x[2] = 2 ， 2 / 1 % 10 = 2 推論 radix = 2，所以對回去y[i]之後，
2這個值的位置要從2變成 --y[2] = 4，也就是新排列的陣列x' = { 30 , 20 , 1 , 11 , 2 , 52 , X , X }，

x[1] = 3 ， 3 / 1 % 10 = 3 推論 radix = 3，所以對回去y[i]之後，
3這個值的位置要從1變成 --y[3] = 6，也就是新排列的陣列x' = { 30 , 20 , 1 , 11 , 2 , 52 , 3 , X }，

x[0] = 5 ， 5 / 1 % 10 = 5 推論 radix = 5，所以對回去y[i]之後，
5這個值的位置要從0變成 --y[5] = 7，也就是新排列的陣列x' = { 30 , 20 , 1 , 11 , 2 , 52 , 3 , 5 }，

run2 ( 10位數字x' = x ) :

radix | 0 1 2 3 4 5 6 7 8 9
---------------------------------
30
20
1
11
2
52
3
5
----------------------------------
個數 4 1 1 1 0 1 0 0 0 0
累加個數 y[i] = { 4 , 5 , 6 , 7 , 7 , 8 , 8 , 8 , 8 , 8 } ，這個即為填回去的陣列的最高陣列位置，
用上面的y[i]來進行陣列的重新分配，最原本x最後面開始，

x[7] = 5 ， 5 / 10 % 10 = 0 推論 radix = 0，所以對回去y[i]之後，
5這個值的位置要從7變成 --y[0] = 3，也就是新排列的陣列x' = { X , X , X , 5 , X , X , X , X }，

x[6] = 3 ， 3 / 10 % 10 = 0 推論 radix = 0，所以對回去y[i]之後，
3這個值的位置要從6變成 --y[0] = 2，也就是新排列的陣列x' = { X , X , 3 , 5 , X , X , X , X }，

x[5] = 52 ， 52 / 10 % 10 = 5 推論 radix = 5，所以對回去y[i]之後，
52這個值的位置要從5變成 --y[5] = 7，也就是新排列的陣列x' = { X , X , 3 , 5 , X , X , X , 52 }，

x[4] = 2 ， 2 / 10 % 10 = 0 推論 radix = 0，所以對回去y[i]之後，
2這個值的位置要從4變成 --y[0] = 1，也就是新排列的陣列x' = { X , 2 , 3 , 5 , X , X , X , 52 }，

x[3] = 11， 11 / 10 % 10 = 1 推論 radix = 1，所以對回去y[i]之後，
11這個值的位置要從3變成 --y[1] = 4，也就是新排列的陣列x' = { X , 2 , 3 , 5 , 11 , X , X , 52 }，

x[2] = 1 ， 1 / 10 % 10 = 0 推論 radix = 0，所以對回去y[i]之後，
1這個值的位置要從2變成 --y[0] = 0，也就是新排列的陣列x' = { 1 , 2 , 3 , 5 , 11 , X , X , 52 }，

x[1] = 20 ， 20 / 10 % 10 = 2 推論 radix = 2，所以對回去y[i]之後，
20這個值的位置要從1變成 --y[2] = 5，也就是新排列的陣列x' = { 1 , 2 , 3 , 5 , 11 , 20 , X , 52}，

x[0] = 30 ， 30 / 10 % 10 = 3 推論 radix = 3，所以對回去y[i]之後，
30這個值的位置要從0變成 --y[3] = 6，也就是新排列的陣列x' = { 1 , 2 , 3 , 5 , 11 , 20 , 30 , 52 }，

最後沒有百位數字，所以停止排序 x' 即為所求。

以下為實作的code:

#include 

int main() {
 int *x = NULL , *y = NULL ;
 
 int n , i ;
 while ( std::cin >> n ) {
  x = new int[n] ;
  y = new int[n] ;

  int max = 0 ;
  for ( i = 0 ; i < n ; i++ ) {
   std::cin >> x[i] ;
   //尋找最大值
   max = x[i] > max ? x[i] : max ;
  }

  //從個位數字開始
  int exp = 1 ;
  //籃子，來放每個數值的索引位置
  int bucket[10] ;

  //排列到最大數字的位元數
  while ( max / exp > 0 ) {
   //初始化每個籃子
   for ( i = 0 ; i < 10 ; i++ )
    bucket[i] = 0 ;
   //找到每個數字要擺放的陣列位置，並記錄每個籃子的大小
   for ( i = 0 ; i < n ; i++ ) 
    bucket[x[i] / exp % 10]++ ;
   //根據每個籃子的大小，計算出籃子中的元素的最大陣列位置
   for ( i = 0 ; i < 9 ; i++ )
    bucket[i+1] += bucket[i] ;
   //根據上面計算出來的籃子陣列位置，把數值填到對應的位置
   for ( i = n - 1 ; i >= 0 ; --i ) 
    y[ --bucket[ x[i] / exp % 10 ] ] = x[i] ;
   //最後拷貝一份到原始陣列中
   for ( i = 0 ; i < n ; i++ )
    x[i] = y[i] ;
   exp *= 10 ;
  }
  
  for ( i = 0 ; i < n ; i++ )
   std::cout << x[i] << " " ;
  std::cout << std::endl ;
  delete []x ;
  delete []y ;
 }
 
 return 0;
}

參考網站 : http://zerojudge.tw/ShowProblem?problemid=a233

喲吼吼吼

2013年7月28日星期日

排序法 in C/C++ ( Merge Sort & Heap Sort & Radix Sort )

沒有留言:

2013年7月28日 星期日

排序法 in C/C++ ( Merge Sort & Heap Sort & Radix Sort )

沒有留言:

2013年7月28日星期日