مرتب‌سازی حبابی

از ویکی‌پدیا، دانشنامهٔ آزاد

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

این مرتب‌سازی از آن رو که برای کار با عناصر آن‌ها را با یکدیگر می‌سنجد، یک مرتب‌سازی سنجشی است.

[ویرایش] عملکرد

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

[ویرایش] خرگوش ها و لاک پشت ها

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

[ویرایش] مثال قدم به قدم

اجازه بدهید یک آرایه از عددهای “5, 1, 4, 2, 8” اختیار کنیم و آن را به ترتیب صعودی با استفاده از مرتب سازی حبابی مرتب کنیم. در هر مرحله عناصری که در حال مقایسه شدن با یکدیگر هستند پر رنگ تر نشان داده شده اند:

گذر اول:

(1, 5, 4, 2, 8) <= (5, 1, 4, 2, 8)
در اینجا الگوریتم دو عنصر اول را مقایسه، و جابجا می‌کند.
(1, 4, 5, 2, 8) <= (1, 5, 4, 2, 8)
(1, 4, 2, 5, 8) <= (1, 4, 5, 2, 8)
(1, 4, 2, 5, 8) <= (1, 4, 2, 5, 8)
حالا آرایه مرتب شده است، ولی الگوریتم هنوز نمی‌داند که این کار کامل انجام شده است یا نه، که برای فهمیدن احتیاج به یک گذر کامل بدون هیچ جابجایی (swap) داریم:
گذردوم
(1, 2, 4, 5, 8) <= (1, 2, 4, 5, 8)
(1, 2, 4, 5, 8) <= (1, 2, 4, 5, 8)
(1, 2, 4, 5, 8) <= (1, 2, 4, 5, 8)
(1, 2, 4, 5, 8) <= (1, 2, 4, 5, 8)
در نهایت آرایه مرتب شده است و الگوریتم می‌تواند پایان پذیرد.

[ویرایش] پیاده سازی شبه کد

بیان سادهٔ شبه کد مرتب‌سازی حبابی :

‎

procedure bubbleSort( A : list of sortable items ) defined as:
do
swapped := false
for each i in 0 to length(A) - 2 inclusive do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
swapped := true
end if
end for
while swapped
end procedure

[ویرایش] تحلیل

نمونه‌ای از مرتب‌سازی حبابی که فهرستی از عددهای تصادفی را مرتب می‌کند.

[ویرایش] بدترین حالت

این الگوریتم در بدترین حالت از مرتبهٔ Θ(n^۲) است. چون در بدترین حالت هر عنصر باید n-۱ بار فهرست را بپیماید.

[ویرایش] بهترین حالت

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

[ویرایش] دیگر روش های پیاده سازی

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

‎

procedure bubbleSort( A : list of sortable items ) defined as:
  n := length( A )
  do
    swapped := false
    n := n - 1
    for each i in 0 to n - 1  inclusive do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped
end procedure

زمان اجرای این روش هنوز هم (O(n^2 است ولی در بدترین حالت (وقتی آرایه ورودی به صورت معکوس مرتب شده باشد) زمان اجرای آن دو برابر سریع تر از حالت عادی الگوریتم می‌باشد.

[ویرایش] گونه‌های دیگر

مرتب‌سازی زوج-فرد پیاده‌سازی این الگوریتم به شیوهٔ موازی است.

نمونه‌ای از عددهای تصادفی که به وسیله‌ٔ مرتب‌سازی زوج-فرد مرتب می‌شوند.

[ویرایش] جستارهای وابسته

• الگوریتم‌های مرتب‌سازی
• مرتب‌سازی سنجشی

[ویرایش] پیوند به بیرون

• مرتب‌سازی حبابی در ۲۰ زبان برنامه‌نویسی

[ویرایش] منابع

‎