الگوریتم مرتب‌سازی حبابی ( Bubble Sort )

نویسنده : فاطمه قلمی
ارسال شده در: 19 می 2025
ارسال دیدگاه: 0

مقدمه

الگوریتم مرتب‌سازی حبابی (Bubble Sort) یکی از ساده‌ترین و ابتدایی‌ترین الگوریتم‌های مرتب‌سازی در علوم کامپیوتر است. این الگوریتم به دلیل سادگی در فهم و پیاده‌سازی، اغلب به عنوان مقدمه‌ای برای آموزش الگوریتم‌های مرتب‌سازی پیچیده‌تر به دانشجویان علوم کامپیوتر معرفی می‌شود. با این حال، به دلیل کارایی پایین در مقایسه با الگوریتم‌های دیگر، استفاده از آن در برنامه‌های کاربردی واقعی به ندرت توصیه می‌شود. در این مقاله، به بررسی جامع الگوریتم مرتب‌سازی حبابی، کاربردهای محدود آن، نحوه پیاده‌سازی، تحلیل پیچیدگی زمانی و فضایی، و مقایسه آن با سایر الگوریتم‌های مرتب‌سازی خواهیم پرداخت.

مبانی نظری و عملکرد الگوریتم مرتب‌سازی حبابی

الگوریتم مرتب‌سازی حبابی با مقایسه مکرر عناصر مجاور در یک لیست یا آرایه و جابجایی آن‌ها در صورت لزوم، عمل مرتب‌سازی را انجام می‌دهد. این فرآیند به گونه‌ای است که عناصر بزرگتر به تدریج مانند حباب به سمت انتهای لیست “بالا” می‌روند.

عملکرد الگوریتم به صورت زیر خلاصه می‌شود:

مقایسه: الگوریتم از ابتدای لیست شروع کرده و عناصر مجاور (عنصر i و عنصر i+1) را با یکدیگر مقایسه می‌کند.
جابجایی (Swapping): اگر عنصر i بزرگتر از عنصر i+1 باشد، جای آن‌ها با یکدیگر عوض می‌شود. به این ترتیب، بزرگترین عنصر در هر تکرار به انتهای قسمت مرتب نشده لیست منتقل می‌شود.
تکرار: مراحل 1 و 2 برای تمام عناصر لیست، از ابتدای لیست تا انتهای قسمت مرتب نشده، تکرار می‌شوند.
بهینه‌سازی: در هر تکرار، بزرگترین عنصر به جایگاه صحیح خود منتقل می‌شود. بنابراین، در تکرار بعدی، نیازی به بررسی عنصر آخر نیست. الگوریتم تا زمانی که هیچ جابجایی در یک تکرار انجام نشود، به کار خود ادامه می‌دهد. این بهینه‌سازی باعث می‌شود در صورتی که لیست از قبل مرتب باشد، الگوریتم سریع‌تر به پایان برسد.

مثال:

فرض کنید لیست زیر را برای مرتب‌سازی با استفاده از الگوریتم حبابی در اختیار داریم:

[5, 1, 4, 2, 8]

مراحل اجرای الگوریتم به صورت زیر خواهد بود:

تکرار اول:

( 5, 1, 4, 2, 8) -> ( 1, 5, 4, 2, 8) (5 > 1، جای آن‌ها عوض شد)
(1, 5, 4, 2, 8) -> (1, 4, 5, 2, 8) (5 > 4، جای آن‌ها عوض شد)
(1, 4, 5, 2, 8) -> (1, 4, 2, 5, 8) (5 > 2، جای آن‌ها عوض شد)
(1, 4, 2, 5, 8) -> (1, 4, 2, 5, 8) (5 < 8، نیازی به جابجایی نیست)

پس از تکرار اول، لیست به صورت [1, 4, 2, 5, 8] در می‌آید. بزرگترین عنصر (8) به جایگاه صحیح خود در انتهای لیست منتقل شده است.

تکرار دوم:

( 1, 4, 2, 5, 8) -> ( 1, 4, 2, 5, 8) (1 < 4، نیازی به جابجایی نیست)
(1, 4, 2, 5, 8) -> (1, 2, 4, 5, 8) (4 > 2، جای آن‌ها عوض شد)
(1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8) (4 < 5، نیازی به جابجایی نیست)

پس از تکرار دوم، لیست به صورت [1, 2, 4, 5, 8] در می‌آید.

تکرار سوم:

( 1, 2, 4, 5, 8) -> ( 1, 2, 4, 5, 8) (1 < 2، نیازی به جابجایی نیست)
(1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8) (2 < 4، نیازی به جابجایی نیست)

پس از تکرار سوم، لیست به صورت [1, 2, 4, 5, 8] در می‌آید.

از آنجایی که هیچ جابجایی در تکرار سوم انجام نشد، الگوریتم متوقف شده و لیست مرتب شده به عنوان خروجی ارائه می‌شود.

پیاده‌سازی الگوریتم مرتب‌سازی حبابی

در اینجا نمونه‌ای از پیاده‌سازی الگوریتم مرتب‌سازی حبابی در زبان برنامه‌نویسی پایتون ارائه می‌شود:

در این کد، تابع bubble_sort یک آرایه arr را به عنوان ورودی دریافت کرده و آن را با استفاده از الگوریتم مرتب‌سازی حبابی مرتب می‌کند. متغیر swapped برای بهینه‌سازی الگوریتم استفاده می‌شود. اگر در یک تکرار هیچ جابجایی انجام نشود، به این معنی است که آرایه مرتب شده است و الگوریتم می‌تواند متوقف شود.

پیچیدگی زمانی و فضایی

پیچیدگی زمانی:
- بهترین حالت (Best Case): O(n) – زمانی رخ می‌دهد که لیست از قبل مرتب باشد. به دلیل بهینه‌سازی با استفاده از متغیر swapped.
- حالت متوسط (Average Case): O(n^2)
- بدترین حالت (Worst Case): O(n^2) – زمانی رخ می‌دهد که لیست به صورت معکوس مرتب شده باشد.
پیچیدگی فضایی: O(1) – الگوریتم مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی درجا (in-place) است، به این معنی که به فضای اضافی قابل توجهی نیاز ندارد.

کاربردها و محدودیت‌ها

با وجود سادگی، الگوریتم مرتب‌سازی حبابی کاربردهای محدودی دارد. به دلیل پیچیدگی زمانی O(n^2) در حالت متوسط و بدترین حالت، برای مرتب‌سازی لیست‌های بزرگ به هیچ وجه توصیه نمی‌شود.

آموزش: به عنوان یک مثال ساده برای آموزش مفاهیم اولیه الگوریتم‌های مرتب‌سازی به دانشجویان.
مرتب‌سازی لیست‌های بسیار کوچک: در صورتی که لیست برای مرتب‌سازی بسیار کوچک باشد، سربار (overhead) سایر الگوریتم‌های مرتب‌سازی پیچیده‌تر ممکن است بیشتر از مرتب‌سازی حبابی باشد.
تشخیص لیست‌های از قبل مرتب شده: به دلیل پیچیدگی زمانی O(n) در بهترین حالت، برای تشخیص سریع اینکه آیا یک لیست از قبل مرتب شده است یا خیر، می‌تواند مفید باشد.

محدودیت‌ها:

کارایی پایین: کارایی بسیار پایین در مقایسه با الگوریتم‌های مرتب‌سازی دیگر مانند مرتب‌سازی ادغامی (Merge Sort)، مرتب‌سازی سریع (Quick Sort)، و مرتب‌سازی هیپ (Heap Sort).
عدم مقیاس‌پذیری: به خوبی با افزایش حجم داده‌ها مقیاس‌پذیر نیست.

مقایسه با سایر الگوریتم‌های مرتب‌سازی

در مقایسه با سایر الگوریتم‌های مرتب‌سازی، مرتب‌سازی حبابی اغلب به عنوان یکی از کم‌کارآمدترین الگوریتم‌ها در نظر گرفته می‌شود. الگوریتم‌های مرتب‌سازی ادغامی و مرتب‌سازی سریع دارای پیچیدگی زمانی O(n log n) هستند که به طور قابل توجهی بهتر از O(n^2) مرتب‌سازی حبابی است. الگوریتم مرتب‌سازی هیپ نیز دارای پیچیدگی زمانی O(n log n) است و در برخی موارد می‌تواند از مرتب‌سازی سریع نیز بهتر عمل کند.

با این حال، در شرایط خاص، مانند مرتب‌سازی لیست‌های بسیار کوچک یا تشخیص لیست‌های از قبل مرتب شده، مرتب‌سازی حبابی می‌تواند گزینه مناسبی باشد. همچنین، سادگی پیاده‌سازی آن، آن را به ابزاری ارزشمند برای آموزش مفاهیم اولیه الگوریتم‌ها تبدیل کرده است.

نتیجه‌گیری

الگوریتم مرتب‌سازی حبابی با وجود سادگی، به دلیل کارایی پایین در بیشتر سناریوها، کاربردهای محدودی دارد. پیچیدگی زمانی O(n^2) آن باعث می‌شود که برای مرتب‌سازی لیست‌های بزرگ مناسب نباشد. با این حال، به عنوان یک مثال آموزشی ساده و برای مرتب‌سازی لیست‌های بسیار کوچک، می‌تواند مفید باشد. در عمل، استفاده از الگوریتم‌های مرتب‌سازی پیچیده‌تر و کارآمدتر مانند مرتب‌سازی ادغامی، مرتب‌سازی سریع، یا مرتب‌سازی هیپ توصیه می‌شود. آگاهی از نقاط قوت و ضعف هر الگوریتم، به برنامه‌نویسان کمک می‌کند تا بهترین الگوریتم را برای نیازهای خاص خود انتخاب کنند.

فاطمه قلمی

بازدید: