انواع مختلف مرتب سازی

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 

http://en.wikipedia.org/wiki/Bubble_sort   

  مرتب سازی درجی ( 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

            http://en.wikipedia.org/wiki/Insertion_sort

مرتب سازی انتخابی (selection sort) :

#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

http://en.wikipedia.org/wiki/Selection_sort

مرتب سازی ادغامی ( 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]
        

ادامه دارد .....