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

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

مرتب‌سازی حبابی (به انگلیسی: 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


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

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

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

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

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

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