مرتبسازی حبابی
از ویکیپدیا، دانشنامهٔ آزاد.
مرتبسازی حبابی (به انگلیسی: Bubble sort) یک الگوریتم مرتبسازی سادهاست که لیست را پشت سرهم پیمایش میکند تا هر بار عناصر کنارهم را با هم سنجیده و اگر در جای نادرست بودند جابهجایشان کند. دراین الگوریتم این کار باید تا زمانی که هیچ جابهجایی در لیست نیاز نباشد انجام میدهد و در آن زمان لیست مرتب شدهاست. این مرتبسازی از آن رو حبابی نامیده میشود که هر عنصر با عنصر کناری خود سنجیدهشده و درصورتی که از آن کوچکتر باشد جای آن را گرفته و جای خود را به آن میدهد و این کار همچنان پیش میرود تا کوچکترین عنصر به بالای لیست برسد و دیگران نیز به ترتیب در جای خود قرار گیرند (یا بالاتر روند یا به پایین لیست رانده شوند.) این عمل همانند پویش حباب به بالای مایع است.
این مرتبسازی از آن رو که برای کار با عناصر آنها را با یکدیگر میسنجد، یک مرتبسازی سنجشی است.
بیان سادهٔ شبه کد مرتبسازی حبابی :
procedure bubbleSort(A : list of sortable items) defined as:
do
swapped := false
for each i in ۰ to length(A) - ۲ do:
if A[ i ] > A[ i + ۱ ] then
swap(A[ i ], A[ i + ۱ ])
swapped := true
end if
end for
while swapped
end procedure
فهرست مندرجات |
[ویرایش] تحلیل
[ویرایش] بدترین حالت
این الگوریتم در بدترین حالت از مرتبهٔ Θ(n۲) است. چون در بدترین حالت هر عنصر باید n-۱ بار فهرست را بپیماید.
[ویرایش] بهترین حالت
بهترین حالت این است که لیست مرتب شدهباشد که در این حالت الگوریتم از مرتبه O(n) است.
[ویرایش] پیادهسازیهای دیگر
از آنجا که در هر پیمایش عنصر بزرگتر پشتِسرِهم به پایین فهرست رانده میشود، بسیار روشن است که در پایان هر پیمایش پایینترین عنصر بزرگترین آن است. پس نیاز نیست که هر بار تا عنصر nام پیش رویم و در پیمایش دوم میتوانیم تنها تا عنصر (n-۱)ام پیش رویم و به همین ترتیب در پیمایش iام پیشروی تا عنصر (n-i)ام بسندهاست.
شبه کد این روش:
procedure bubbleSort(A : list of sortable items) defined as:
n := length(A) - ۱
do
swapped := false
n := n - ۱
for each i in ۰ to n do:
if A[ i ] > A[ i + ۱ ] then
swap(A[ i ], A[ i + ۱ ])
swapped := true
end if
end for
while swapped
end procedure
[ویرایش] گونههای دیگر
مرتبسازی زوج-فرد پیادهسازی این الگوریتم به شیوهٔ موازی است.
[ویرایش] جستارهای وابسته
- الگوریتمهای مرتبسازی
- مرتبسازی سنجشی
[ویرایش] پیوند به بیرون
[ویرایش] منابع
- Wikipedia contributors, «Bubble sort», Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/wiki/Bubble_sort (دسترسی در ۱۲:۵۷ PM ۴/۱۶/۲۰۰۷)



