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

در حالی که مرتب سازی پوسته کارآمدترین روش نیست، افراد مبتدی از تمرین آن سود زیادی می برند.

مرتب سازی پوسته یک تکنیک مرتب سازی است که یک لیست داده شده را به زیر لیست ها تقسیم می کند و سپس آنها را با استفاده از مرتب سازی درج مرتب می کند. این الگوریتم از یک شکاف n استفاده می کند که مواردی را انتخاب می کند که n فاصله از هم دارند تا فهرست های فرعی را تشکیل دهند.

سپس فهرست‌های فرعی با استفاده از مرتب‌سازی درج مرتب می‌شوند و پس از آن با هم ترکیب می‌شوند. لیست ترکیبی به طور کامل مرتب نشده است اما به الگوریتم این مزیت را می دهد که آیتم ها به موقعیت های نهایی خود نزدیک تر هستند.

مرتب سازی درج دوباره برای مرتب سازی نهایی لیست استفاده می شود.

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

شرح بالا ممکن است چندان منطقی نباشد، اما یک مثال باید کمک کند. فرض کنید لیست را دارید: [39، 6، 2، 51، 30، 42، 7، 4، 16] و مقدار فاصله سه.

اولین فهرست فرعی دارای موارد است: 39، 51، 7

دومین فهرست فرعی: 6، 30، 4

سومین و آخرین فهرست فرعی: 2، 42، 16

پس از مرتب سازی درج، هر یک از فهرست های فرعی به صورت زیر مرتب می شوند:

اولی: 7، 39، 51

دومی: 4، 6، 30

سوم: 2، 16، 42

فهرست فرعی مرتب شده اکنون به روشی خاص ترکیب شده است. هر مورد از فهرست فرعی در فهرستی قرار می گیرد که مقدار فهرست فرعی مرتب نشده اصلی از آن جمع آوری شده است.

مطالب مرتبط: مقدمه ای بر الگوریتم مرتب سازی حبابی

بنابراین به دنباله زیر خواهید رسید:

[7، 4، 2، 39، 6، 16، 51، 30، 42]

توجه داشته باشید که لیست هنوز مرتب نشده است اما موارد به موقعیت هایی که قرار است در آن قرار گیرند نزدیک تر هستند. پس از انجام مرتب سازی درج در این ترکیب لیست، لیست در نهایت مرتب می شود:

[2، 4، 6، 7، 16، 30، 39، 42، 51]

تجزیه و تحلیل الگوریتم

پیچیدگی مرتب سازی پوسته بین O(n) و O(n2) است. محاسبه برای این نتیجه گیری خارج از محدوده این مقاله است.

پیاده سازی پایتون:

def shellSort(my_list):

n = len(my_list)

interval = n // 2 # floor division

while interval > 0:

for val in range(interval, n):

temp = my_list[val]

x = val

while x >= interval and my_list[x - interval] > temp:

my_list[x] = my_list[x - interval]

x = x - interval



my_list[x] = temp

interval = interval // 2 

حرکت به مرتب سازی ادغام

چندین الگوریتم مرتب سازی وجود دارد که هر کدام عملکرد منحصر به فردی دارند. مرتب سازی ادغام برای مثال از یک استراتژی تقسیم و غلبه استفاده می کند و دارای پیچیدگی O(nlogn) است.

مرتب سازی ادغام، در برخی موارد، بهتر از مرتب سازی پوسته است و قطعا ارزش دیدن دارد. باید در لیست خواندن الگوریتم‌های مرتب‌سازی شما قرار گیرد.

منبع مقاله