星期四, 12月 28, 2006

Mergesort

最近要交作業才會真正認真的開始思考合併排序的好用之處,在網路上所參考到的碼較少為template實作之,所以花了一點小功夫改寫和包裝,也還算方便,以下程式碼不算是我寫的,我只是就古狗大神找到的C code改成template型式,使用了vector,這樣子會使程式碼較為簡潔而較能夠專精於整個程式的運作程,對我而言是一個不錯的學習方式


template<class T>
void MergeSort(vector<T>& u){
merge_sort(u,0,u.size()-1);
}

template<class T>
void merge_sort(vector<T>& u,int low, int high){
if(high>low){
merge_sort(u,low,(low+high)/2);
merge_sort(u,(low+high)/2+1,high);
Merge(u,low,high);
}
}

template<class T>
void Merge(vector<T>& u, int low, int high){
vector<T> temp;

for(unsigned int i=low, j=(low+high)/2+1 ; i<=(low+high)/2 || j<=high;){
if(i>(low+high)/2) temp.push_back(u[j++]);
else if(j>high) temp.push_back(u[i++]);
else if(u[i]>u[j]) temp.push_back(u[j++]);
else if(u[i]<u[j]) temp.push_back(u[i++]);
else{
temp.push_back(u[i++]);
temp.push_back(u[j++]);
}
}
for(unsigned int i=low,j=0;i<=high;i++,j++) u[i]=temp[j];
}


補上在wiki找到的quick sort 轉成實際C++ code(也是使用vector實作之)

template<class T>
void QuickSort(vector<T>& u){
quicksort(u,0,u.size()-1);
}

template<class T>
void quicksort(vector<T>& u, int left, int right){
int l_hold=left, r_hold=right, p_pivot=0;
T pivot = u[left];
while(left<right){
while((u[right]>=pivot) && (left < right)) right--;
if(left!=right){
u[left] = u[right];
left++;
}

while((u[left]<=pivot) && (left<right)) left++;
if(left!=right){
u[right]=u[left];
right--;
}
}
u[left]=pivot;
p_pivot=left;

left = l_hold;
right = r_hold;

if(left<p_pivot) quicksort(u,left,p_pivot-1);
if(right>p_pivot) quicksort(u,p_pivot+1,right);
}

---
下一次可以自行試著寫寫看了,總覺得這個Merge的判斷會造成速度的問題

張貼留言