2012年5月12日 星期六

【資料結構】二路合併排序(2-way merge sort)/(collating sort)


二路合併排序(2-way merge sort)/(collating sort)

重點為二:
1.      n個,長度1keys,合併程n/2個,長度2keys…直到1個,長度nkey
2.      合併時順便做排序(每次均為二路相互比較成一組)

程式碼運作如下:
========================================================================
void merge (int a[], int m, int p,int n,int b[])

{
int i,j,k;
i=m;
j=p+1;
k=m;
while (i<=p && j<=n)
if(a[i]<=a[j])
b[k++]=a[i++];
else
b[k++]=a[j++];
while(i<=p)
b[k++]=a[i++];
while(j<=n)
b[k++]=a[j++];
}
int * MergeSort(int *x, int *y, int n)
{
int len, *t;
for(len=1; len<n; len*=2)
{
for(int s=1 s+len<=n; s+=2*len)
if(s+2*len-1>n)
merge(x,s,s+len-1,n,y);
else
merge(x,s,s+len-1,s+len*2-1,y);
t=x;
x=y;
y=t;
}
return x;
}
========================================================================

題目:
外部排序(external sorting)最常使用的是2-way合併排序法(merge sorting)。假設檔案裡面包含18000筆資料,而記憶體最多只能容許3000筆資料。假設每次I/O block大小為1000筆資料,則需讀多少次I/O block才能完成排序?
解法:
A.     在分段排序階段:
18000/3000=6段資料,而每段3000/1000=3I/O block,共需6*3=18I/O block

B.     在分段合併階段:
a.       回合一:
 


b.      回合二:
c.       回合三:


得到解答:
共需18+18+12+18=66I/O block


沒有留言:

張貼留言

如果久久沒有反應,請直接寄信
應該是我不太會用google blogger 導致有留言過久未處理><
實在深感抱歉..