منبع اصلی نوشتار زیر در این لینک قرار دارد

الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)

 bubble sort الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)

 

در پست قبل مفهومی از مرتب سازی را برای شما گفتیم و یک تابع برای مرتب سازی ارایه دادیم ، در این پست به سراغ مرتب سازی حبابی (bubble sort) می رویم که از معروف ترین الگوریتم های مرتب سازی است .قبل از این که به ادامه بحث بپردازیم یک مرور بکنیم از سایر الگوریتم ها که در روز های آینده آن ها را بررسی خواهیم کرد:

– مفهوم مرتب سازی

-bubble sort

-insertion sort

-merge sort

quick sort

-Distribution sorts

– Concurrent sorts

در این روش مرتب سازی هر عنصر آرایه فقط با عنصر کناری خود مقایسه می شود و اگر عنصر n ام کوچک تر از عنصر n+1 ام بود جای ای دو عنصر عوض می شود این کار تا زمانی که تمام آرایه مرتب شود ادامه می یابد .

اسم این الگوریتم را مرتب سازی حبابی (bubble sort) گذاشته اند  زیرا هر عنصر آرایه فقط با عنصر کناری خو بررسی می شود در تصویر متحرک زیر می توانید آرایه ای را ببینید که با بابل ، سورت می شود :

Bubble sort example 300px1 الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)

تابع مرتب سازی حبابی (bubble sort) را در زیر می بینید :

 

void bubble_sort( int A[],int n)
{
	int i;
	int temp ;
	int flag = 1;

	while( flag == 1)
	{
		flag = 0;

		for( i = 0; i < n-1 ; i++)
		{
			if( A[i] > A[i+1])
			{
				temp = A[i];
				A[i] = A[i+1];
				A[i+1] = temp;
				flag = 1;
			}
		}

	}
}

فرض کنید آرایه ی  ۵ عنصری   ۴ ۱ ۶ ۵ ۸ را دارید و می خواهید آن را با الگوریتم بابل مرتب کنید :

 

8 5 6 1 4

5 8 6 1 4

5 6 8 1 4

5 6 1 8 4

5 6 1 4 8

5 1 6 4 8

1 5 6 4 8

1 5 4 6 8

1 4 5 6 8

 

مرتبه این الگوریتم در بدترین حالت  ( O(n^2  است و  در  بهترین حالت  ( O(n است  به همین خاطر برای سورت کردن تعداد زیادی عنصر مناسب نیست .

در زیر برنامه ای آمده است که در آن تابع مرتب سازی حبابی آمده است که در تابع main  برنامه  آرایه ای به  تابع داده شده تا آن را سورت کند و آرایه را قبل و بعد از مرتب سازی چاپ کند

 

 

// bubble sort.cpp : تابع مرتب سازی حبابی 
//

#include "stdafx.h"
#include <iostream>

using namespace std;

void bubble_sort( int A[],int n)
{
	int i;
	int temp ;
	int flag = 1;

	while( flag == 1)
	{
		flag = 0;

		for( i = 0; i < n-1 ; i++)
		{
			if( A[i] > A[i+1])
			{
				temp = A[i];
				A[i] = A[i+1];
				A[i+1] = temp;
				flag = 1;
			}
		}

	}
}

int main()
{
	int i = 0;
	int A[5]={8,5,6,1,4};
	//show array before sort
	for( i = 0; i < 5; i++)
	{
		cout<< A[i]<<" ";
	}
	cout<<endl;
	//sort function
	bubble_sort(A,5);
	//show array after sort
	for( i = 0; i < 5; i++)
	{
		cout<< A[i]<<" ";
	}
	cout<<endl;

	return 0;
}

 

البته  الگوریتم bubble  رو می شه  جور دیگری پیاده سازی کرد ولی این بهتره.اگر برنامه را طور دیگری نوشته اید یا با زبان  دیگری حتما آن را در نظرات بیان کنید.

 

 

digg الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   reddit الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   stumbleupon الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   yahoo buzz الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   dzone الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   facebook الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   delicious الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   dotnetkicks الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   dotnetshoutout الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   linkedin الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   technorati الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   twitter الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   google buzz الگوریتم های مرتب سازی:مرتب سازی حبابی (bubble sort)   



برچسب ها : , , , ,

به سیاره لینوکس امتیاز دهید

به اين صفحه امتياز دهيد