الگوريتم مرتب سازي حبابي

صفحه اصلی

آموزش الگوريتم نويسي

آموزش مقدماتي

آموزش الگوريتم نويسي - آموزش مقدماتي

نوشته شده توسط محمد حسين سعادت فر

اين الگوريتم ساده ترين و معروف ترين الگوريتم براي مرتب سازي داده است.

فرض کنید می‌خواهیم n داده به صورت صعودی مرتب شوند. عنصر اول را با با عنصر دوم مقایسه کرده، و در صورتی که عنصر اول بزرگتر باشد باشد جای عنصر اول و دوم را عوض می‌کنیم. همین کار را با عناصر دوم و سوم انجام می‌دهیم و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تمام شد بزرگ‌ترین عنصر بین داده‌ها به آخر لیست می‌رسد . حالا یک بار دیگر از اول این کار را انجام می‌دهیم اما این بار تا عنصر (n -۱)ام ادامه می‌دهیم (عنصر nام در مرحله اول در جای خودش قرار گرفته). باز هم این کار را تا عنصر (n - ۲)ام تکرار می‌کنیم ، و بازهم .... تا اینکه بالاخره داده‌ها مرتب می‌شوند.

مثلا:

۰ - ۰)    ۵ ۶ ۴ ۲

۱ - ۱)    ۵ ۶ ۴ ۲

۱ - ۲)    ۵ ۴ ۶ ۲

۱ - ۳)    ۵ ۴ ۲ ۶

۲ - ۱)    ۴ ۵ ۲ ۶

۲ - ۲)    ۴ ۲ ۵ ۶

۳ - ۱)    ۲ ۴ ۵ ۶

مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم می‌شوند شش مقایسه. در کل این روش n (n - ۱) / ۲ مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید:

۰ - ۰)    ۰ ۷ ۱ ۳ ۵ ۴

۱ - ۱)    ۰ ۱ ۷ ۳ ۵ ۴

۱ - ۲)    ۰ ۱ ۷ ۳ ۵ ۴

۱ - ۳)    ۰ ۱ ۳ ۷ ۵ ۴

۱ - ۴)    ۰ ۱ ۳ ۵ ۷ ۴ 

۱ - ۵)    ۰ ۱ ۳ ۵ ۴ ۷ 

۲ - ۱)    ۰ ۱ ۳ ۵ ۴ ۷

۲ - ۲)    ۰ ۱ ۳ ۵ ۴ ۷

۲ - ۳)    ۰ ۱ ۳ ۵ ۴ ۷

۲ - ۴)    ۰ ۱ ۳ ۴ ۵ ۷ 

۳ - ۱)    ۰ ۱ ۳ ۴ ۵ ۷

۳ - ۲)    ۰ ۱ ۳ ۴ ۵ ۷

۳ - ۳)    ۰ ۱ ۳ ۴ ۵ ۷

۴ - ۱)    ۰ ۱ ۳ ۴ ۵ ۷

۴ - ۲)    ۰ ۱ ۳ ۴ ۵ ۷

۵ - ۱)    ۰ ۱ ۳ ۴ ۵ ۷

همونطور که می‌بینید انتهای مرحله ۲ داده‌ها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحله‌ای رسیدیم که هیچ جابجایی در اون رخ نداد نتیجه می‌شه که داده‌ها مرتب هستن (مرحله سوم). پس بعد از مرحله ۳ مطمئن می‌شیم که داده هامون مرتب شدن و نیازی به مراحل ۴ و ۵ نیست.

برگرفته از: ويكيپديا

نظر ها