الگوریتم مرتب سازی شل (Shell Sort)

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

shell sort algorithm 7348 تصویر

الگوریتم مرتب سازی شل (Shell Sort)

الگوریتم مرتب سازی شل (Shell Sort) نسخه تغییر یافته الگوریتم مرتب سازی درجی (Insertion Sort) است. در مرتب سازی درجی ما عناصر را فقط یک خانه به جلو حرکت دهیم. همین موضوع باعث می شود تا برای انتقال یک عنصر به موقعیت خیلی جلوتر، تعداد حرکات افزایش یابد. در الگوریتم مرتب سازی شل امکان مبادله عناصر دور هم فراهم شده است.

الگوریتم مرتب سازی شل برای رفع ایرادات زیر که در مرتب سازی درجی وجود دارد، ایجاد شده است:

  • کارایی مرتب سازی درجی زمانی خوب است که آرایه تقریبا مرتب باشد.
  • بازده کمی دارد، چون در هر زمان فقط به اندازه یک موقعیت مقادیر را جا به جا می می کند.

shell sort algorithm 7348 1 تصویر

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

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

امتحان کنید

خروجی:

نکات

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

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