مرتب سازی درج (Insertion Sort)
در «مرتب سازی درج (Insertion Sort)» لیست به دو بخش تقسیم می شود. بخش اول مرتب است و بخش دوم هنوز نامرتب است. سپس هر بار یک مقدار از بخش نامرتب برداشته می شود و در جای درستِ بخش مرتب قرار می گیرد.
ایده اصلی مرتب سازی درج
ابتدا عنصرِ بعدی را انتخاب کن. سپس جای درستش را در بخش مرتب پیدا کن. بعد آن را همان جا قرار بده. بنابراین مرز بخش مرتب، آرام آرام جلو می آید.
پیاده سازی پایه با pop/insert
در این نسخه، مقدار را برمی داریم و سپس در مکان درست درج می کنیم. این شبیه مرتب کردن کارت ها در دست است.
mylist = [64, 34, 25, 12, 22, 11, 90, 5]
n = len(mylist)
for i in range(1, n):
insert_index = i
current_value = mylist.pop(i)
for j in range(i - 1, -1, -1):
if mylist[j] > current_value:
insert_index = j
mylist.insert(insert_index, current_value)
print(mylist)
بهبود: شیفتِ حداقلی و شکستن حلقه
برای سرعت بهتر، مقدار را کپی می کنیم و سپس فقط عناصرِ لازم را شیفت می دهیم. همچنین وقتی جای درست پیدا شد، حلقه را می شکنیم.
mylist = [64, 34, 25, 12, 22, 11, 90, 5]
n = len(mylist)
for i in range(1, n):
insert_index = i
current_value = mylist[i]
for j in range(i - 1, -1, -1):
if mylist[j] > current_value:
mylist[j + 1] = mylist[j]
insert_index = j
else:
break
mylist[insert_index] = current_value
print(mylist)
گام های عملی
- ابتدا عنصرِ بعدی را انتخاب کن.
- سپس در بخش مرتب، مکان درست را بیاب.
- بعد عنصر را درج یا شیفت بده.
- در نتیجه مرز مرتب یک خانه جلو می رود.
- تا پایان لیست همین روند تکرار می شود.
پیچیدگی زمانی
در میانگین حالت، هر عنصر حدود نصف لیست را مقایسه می کند. این کار برای همه عناصر تکرار می شود. بنابراین «پیچیدگی زمانی (Time Complexity)» برابر O(n^2) است. با این حال، اگر تقریباً مرتب باشد، عملکرد بسیار بهتر می شود.
نکته: برای مقایسه، به مرتب سازی انتخابی و همچنین به مرتب سازی سریع سر بزن.
جمع بندی سریع
- هر بار یک عنصر درج می شود.
- نسخه بهبود یافته شیفتِ کمتری دارد.
- میانگین زمان O(n^2) است.
- روی لیست های تقریباً مرتب سریع تر است.
- برای آموزش بسیار قابل فهم است.