خبرگزاری آیصد (جدیدترین و جذاب ترین اخبار ایران و جهان)

نشر توسط:admin Views 45 تاریخ : 2 خرداد 1395

مرتب سازی حبابی(Bubble Sort) :

یکی از ساده ترین مرتب سازی هایی که ترم اول به بچه های کامپیوتر یاد می دن مرتب سازی حبابی است.در این الگوریتم از ابتدای آرایه شروع کرده و هر دو جفت عدد کنار هم, با هم مقایسه شده و در صورت نیاز جابه جا می شوند.و این کار  تا آخر ادامه می یابد. در واقع هر بار بزرگترین مقدار را از بین داده ها پیدا کرده و در انتها قرار می دهیم.این مرتب سازی از دوتا حلقه ی for تشکیل شده. حلقه ی بیرونی شمارنده ای است که هر بار یک عدد را برای مقایسه با بقیه ی اعداد انتخاب کرده و بزرگترین را به جای درست خود می برد.حلقه ی for درونی نیز شمارنده ایست که عمل مقایسه عدد با سایر اعداد را انجام می دهد.

	{

		
if(array[y]>array[y+1]);
{	int temp = array[y+1];
	array[y+1] = array[y];

}    }}

در بدترین حالت،یعنی زمانی که اعداد به صورت معکوس در آرایه قرار گرفته اند حداکثر

n مقایسه صورت می گیرد.

مرتبه زمانی این الگوریتم در بهترین حالت و بدترین حالت:O(n^2)

مرتب سازی حبابی با کمی تغییر(modified bubble sort):

بهترین نسخه ی الگوریتم مرتب سازی حبابی یک flag دارد.این flag  در صورتی که عمل swap بین جفت عدد انجام شود true  شده و در صورتی که swap انجام نشود flag  false می شود.false  بودن flag به این معناست که عمل  sort  پایان یافته و دیگر نیاز نیست تا انتهای آرایه داده ها را پیمایش کنیم.

در این صورت در بهترین حالت مرتبه ی زمانی الگوریتم O(n) می شود.