الگوریتم مرتب سازی شانه ای (Comb Sort)

  • دوشنبه 18 نوامبر 2019
  • بازدید ۵۹ نفر

comb sort algorithm 7350 تصویر

الگوریتم مرتب سازی شانه ای (Comb Sort)

ایده اصلی مرتب سازی حبابی و مرتب سازی شانه ای یکی است. به عبارت دیگر می توان گفت که الگوریتم مرتب سازی شانه ای (Comb Sort)، بهبود یافته الگوریتم Bubble Sort است. در روش مرتب سازی حبابی، در هر مرحله هر مقدار با مقدار بعدی مقایسه می شود و میزان شکاف (Gap) همیشه ۱ است. اما در مرتب سازی شانه ای، موارد در یک شکاف خاص طبقه بندی می شوند و بعد از اتمام هر مرحله، اندازه شکاف کاهش می یابد تا به ۱ برسد. ضریب کاهش شکاف ۱٫۳ است. یعنی پس از اتمام هر مرحله شکاف بر ۱٫۳ تقسیم می شود.

comb sort algorithm 4350 1 تصویر

پیاده سازی الگوریتم Comb Sort

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

امتحان کنید

خروجی:

شبیه سازی

آرایه زیر را در نظر بگیرید (مقدار اولیه شکاف ۱۰ است):

نکات

  • پیچیدگی زمانی در بهترین حالت: O(n log n)
  • پیچیدگی زمانی در حالت متوسط: O(n2/2p)
  • پیچیدگی زمانی در بدترین حالت: O(n2)
  • پیچیدگی فضایی: O(1)
ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

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