آشنایی با مرتب سازی حبابی (Bubble Sort )

روش های مختلفی برای مرتب سازی وجود دارد و این که بیان شود کدام روش بهینه ترین است بستگی به شرایط مسئله دارد و مطلقا نمی توان گفت که کدام روش همواره بهترین است . در الگوریتم های مرتب سازی مقایسه و انتساب دو عمل اصلی می باشند. مبحث دیگری که در روش های مرتب سازی مهم می باشد بحث پایدار بودن است یعنی اگر اعداد ۱,۲,۲۰,۳۰,۳را داشته باشیم و بعد از مرتب شدن  به صورت ۱,۲,۳,۲۰,۳۰ شده باشد آن وقت می گوییم پایدار شده است.

در این بخش می خواهیم مرتب سازی حبابی را توضیح دهیم . در این روش آرایه چندین بار پیمایش می شود و هر بار عنصری را با عنصر بعد از خودش مقایسه شده و در صورتی بزرگتر بودن عنصر اول از عنصر دوم جای آن ها تعویض می شود.( در صورتی که شرط مسئله صعودی بودن عناصر باشد)

برای درک بهتر این روش به مثال زیر توجه نمائید : اعداد ورودی : ۵,۹,۴,۱ می باشد.

گذر اول :

ابتدا عدد ۵و۹ با هم مقایسه می شوند و چون عدد ۵ کوچکتر می باشد تعویض صورت نمی گیرد ( ۱ مقایسه و صفر تعویض )

سپس عدد ۹ و ۴ باهم مقایسه می شوند. چون عدد ۹ از ۴ بزرگتر است جای این دو عوض می شود(۱ مقایسه و ۱ تعویض)

سپس عدد ۹ و عدد ۱ با هم مقایسه و سپس تعویض می شوند ( ۱ مقایسه و ۱ تعویض )

پایان گذر اول : ۳ مقایسه و ۲ تعویض صورت گرفت . و بزرگترین عدد سرجای خودش قرار گرفت.

آرایه به صورت ۵,۴,۱,۹ در امده است .

گذر دوم :

حال در گذردوم دوباره از اول آرایه شروع به پیمایش و مقایسه می کنیم :

عدد ۵ و۴ مقایسه و تعویض ( ۱ مقایسه و ۱ تعویض )

سپس عدد ۵ و عدد ۱ مقایسه و سپس تعویض ( ۱ مقایسه و ۱ تعویض )

پایان گذر دوم : ۲ مقایسه و ۲ تعویض

در پایان گذر دوم آرایه به صورت ۴,۱,۵,۹ می باشد.

گذر سوم :

دوباره از اول شروع به پیمایش و عدد ۴و۱ مقایسه و سپس تعویض می شوند ( ۱ مقایسه و ۱ تعویض )

۱,۴,۵,۹

 

کل مقایسه ها : ۶ مقایسه

کل تعویض ها : ۵ مقایسه

 

پس به طور کلی در این روش n(n-1)/2 مقایسه صورت می گیرد : یعنی ۴*۳ /۲ مقایسه صورت گرفت .

مقایسه :

بهترین حالت : O(n^2)

حالت متوسط :‌ O(n^2)

بدترین حالت : O(n^2)

 

تعویض :

بهترین حالت : O(1)

حالت متوسط : O(n^2)

بدترین حالت : O(n^2)

 

برای درک بهتر این روش مرتب سازی به گیف زیر توجه نمائید :

 

 

 

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *