بابک

بابک

بابک

بابک

بابک

این جا برای این است که هر از چندی دلنوشته و یا خواسته ای را بنویسم. البته خالی از مطالب علمی هم نخواهد بود.

طبقه بندی موضوعی

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

شنبه, ۱۳ اسفند ۱۳۹۰، ۰۶:۱۳ ب.ظ

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


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



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



ادامه دارد .....
موافقین ۱ مخالفین ۰ ۹۰/۱۲/۱۳
بابک احمدی

نظرات  (۱)

خیلی خوبه. ادامه بده!
پاسخ:
خیلی ممنون :)

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی