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

  • سه شنبه ۳۰ مهر ۱۳۹۸
  • بازدید ۷۰ نفر

bubble sort algorithm 7311 تصویر

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

الگوریتم مرتب سازی حبابی (Bubble Sort) ساده ترین الگوریتم مرتب سازی است که با تغییر دادن مکرر عناصر مجاور در صورت نامرتب بودن، آرایه را مرتب می کند.

مثال

اولین گام:

  • ۵۱ ۴ ۲ ۸ ) –> ( ۱ ۵ ۴ ۲ ۸ ): در اینجا دو مقدار ۵ و ۱ با هم مقایسه می شوند و چون ۵ از ۱ بزرگتر است با هم عوض می شوند.
  • ( ۱ ۵۴ ۲ ۸ ) –>  ( ۱ ۴ ۵ ۲ ۸ ): چون ۵ > 4 است، تعویض می شوند.
  • ( ۱ ۴ ۵۲ ۸ ) –>  ( ۱ ۴ ۲ ۵ ۸ ): چون ۵ > 2 است، تعویض می شوند.
  • ( ۱ ۴ ۲ ۵۸ ) –> ( 1 4 2 ۵ ۸ ): در اینجا چون ۵ < 8 است، تعویضی نمی شود.

دومین گام:

  • ۱۴ ۲ ۵ ۸ ) –> ( ۱ ۴ ۲ ۵ ۸ ): تعویضی صورت نمی گیرد.
  • ( ۱ ۴۲ ۵ ۸ ) –> ( 1 ۲ ۴ ۵ ۸ ): چون ۴ > 2 است، تعویض می شوند.
  • ( ۱ ۲ ۴۵ ۸ ) –> ( 1 2 ۴ ۵ ۸ ): تعویضی صورت نمی گیرد.
  • ( ۱ ۲ ۴ ۵۸ ) –>  ( ۱ ۲ ۴ ۵ ۸ ): تعویضی صورت نمی گیرد.

حال آرایه ما مرتب شده است. اما الگوریتم از این موضوع با خبر نیست و تمام گام ها را انجام می دهد.

سومین گام:

  • ۱۲ ۴ ۵ ۸ ) –> ( ۱ ۲ ۴ ۵ ۸ ): تعویضی صورت نمی گیرد.
  • ( ۱ ۲۴ ۵ ۸ ) –> ( 1 ۲ ۴ ۵ ۸ ): تعویضی صورت نمی گیرد.
  • ( ۱ ۲ ۴۵ ۸ ) –> ( 1 2 ۴ ۵ ۸ ): تعویضی صورت نمی گیرد.
  • ( ۱ ۲ ۴ ۵۸ ) –> ( 1 2 4 ۵ ۸ ): تعویضی صورت نمی گیرد.

پیاده سازی این الگوریتم با زبان سی پلاس پلاس:

امتحان کنید

خروجی:

تصویری از نحوه کار این الگوریتم:

bubble sort algorithm 7311 1 تصویر

پیاده سازی این الگوریتم به زبان سی پلاس پلاس (بهینه شده):

امتحان کنید

خروجی:

نکات

  • در بدترین حالت و حالت متوسط پیچیدگی زمانی برابر با O(n*n) است. بدترین حالت زمانی است که آرایه به صورت بر عکس مرتب شده باشد.
  • در بهترین حالت پیچیدگی زمانی الگوریتم برابر با O(n) است. بهترین حالت زمانی است که آرایه قبلا مرتب شده باشد.
  • فضای موقت برابر با O(1) است.
ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

هیچ نظری ثبت نشده است