انواع مختلف مرتب سازی
شنبه, ۱۳ اسفند ۱۳۹۰، ۰۶:۱۳ ب.ظ
1 - مرتب سازی مقایسه ای :
مرتب سازی حبابی ( bubble sort ) :
// cpp code #include <iostream> #include <algorithm> using namespace std; const int maxn=1024; void bubble_sort(int n,vector<int> & a){ int i,j; for(j=0;j<n-1;j++) for(i=0;i<n-1;i++) if(a[i]>a[i+1]) a[i]^=a[i+1]^=a[i]^=a[i+1]; }
# python def bubble_sort(a): n = len(a) for j in range(n-1): for i in range(n-1): if a[i] > a[i+1]: tmp=a[i] a[i]=a[i+1] a[i+1]=tmp
مرتب سازی درجی ( insertion sort ) :
#include <algorithm> #include <vector> using namespace std; void insertion_sort(vector<int>& v){ int tmp,i,j,n = v.size(); for(i=1;i<n;i++){ tmp=v[i]; for(j=i;j>0 && v[j-1]>v[j];j--) swap(v[j],v[j-1]); v[j]=tmp; } }
# python def insertion_sort(v): n = len(v) for i in range(1,n): tmp=v[i] j=i while j>0 and v[j-1]>v[j]: r=v[j] v[j]=v[j-1] v[j-1]=r j-=1 v[j]=tmp
#include <vector> #include <algorithm> using namespace std; void selection_sort(vector<int>& v){ int ind,j,i,n = v.size(); for(i=0;i<n;i++){ ind=i; for(j=i+1;j<n;j++) if(v[j]<v[ind]) ind=j; swap(v[i],v[ind]); } }
def selection_sort(v): n = len(v) for i in range(n): ind = i for j in range(i+1,n): if v[j]<v[ind]: ind=j tmp=v[i] v[i]=v[ind] v[ind]=tmp
مرتب سازی ادغامی ( merge sort ) :
بر خلاف الگوریتم های قبلی این الگوریتم بر اساس روش تقسیم و حل کار می کند و پیچیدگی زمان آن نیز از (O(nlgn می باشد.
//cpp code #include<algorithm> #include<vector> using namespace std; const int maxn = 100*1000; void merge_sort(vector<int>& v,int low , int up){ // [low,up) int mid,i,j; if(up<=(low+1)) return ; mid=(up+low)/2; merge_sort(v,low,mid); merge_sort(v,mid,up); //now merge [low,mid) and [mid,up) vector<int>::iterator it=v.begin(); inplace_merge(it+low,it+mid,it+up); }
#python code l=[] def merge_sort(low,up): global l if (low+1) >= up: return mid = (low+up)/2 merge_sort(low,mid) merge_sort(mid,up) # merge [low,mid) and [mid,up) c=[] i = low j = mid while i<mid and j<up: if l[i]>l[j]: c.append(l[j]) j+=1 else: c.append(l[i]); i+=1 while i<mid: c.append(l[i]) i+=1 while j<up: c.append(l[j]) j+=1 for i in xrange(low,up): l[i]=c[i-low]
ادامه دارد .....
۹۰/۱۲/۱۳