علم کامپیوتر همه چیز در مورد درک پیچیدگی های الگوریتم ها و ساختارهای داده است.
شما فهرستی از مواردی دارید که باید مرتب شوند، اما زمان یا منابع لازم برای استفاده از الگوریتم مرتبسازی پیچیدهتر را ندارید.
مرتبسازی درج یکی از سادهترین الگوریتمهای مرتبسازی است، اما برای فهرستهای بزرگ میتواند کند باشد.
پیاده سازی و درک آسان این روش را در بین برنامه نویسان محبوب کرده است. برای لیست های کوچک یا زمانی که به یک راه حل سریع نیاز دارید عالی است.
در این پست وبلاگ، به پیچیدگی زمانی مرتبسازی درج میپردازیم. این الگوریتم برای مرتب سازی آرایه ها استفاده می شود و دارای زمان اجرا O(n2). این بدان معنی است که پیچیدگی زمانی با اندازه آرایه افزایش می یابد.
با این حال، این الگوریتم می تواند اغلب سریعتر از سایر الگوریتم های مرتب سازی، مانند مرتب سازی سریع باشد.
بیایید نگاهی دقیق تر به نحوه کار مرتب سازی درج بیندازیم!
الگوریتم مرتب سازی درج چیست؟
یک عنصر در یک زمان، مرتب سازی درج یک آرایه قابل مرتب سازی ایجاد می کند که اغلب به عنوان یک لیست نامیده می شود.
به عنوان مثال، مرتبسازی در برنامههای کامپیوتری پیچیده مانند کامپایلرها اعمال میشود، جایی که ترتیب توکنها برای تفسیر برنامه مهم است.
مرتب سازی درج چگونه کار می کند؟
وقتی از مرتبسازی درج برای مرتبسازی یک آرایه استفاده میکنیم، الگوریتم با یافتن کوچکترین مورد در لیست و درج آن در موقعیت صحیح شروع میشود.
سپس کوچکترین مورد بعدی را پیدا کرده و در موقعیت صحیح قرار می دهد و به همین ترتیب.
الگوریتم با چرخش در لیست کار می کند و هر مورد را با مورد قبل از آن مقایسه می کند.
اگر موارد در ترتیب اشتباه باشند، الگوریتم آنها را تعویض می کند. سپس بررسی می کند که آیا لیست مرتب شده است یا خیر، و اگر مرتب شده است، الگوریتم به پایان می رسد.
در عمل، مرتبسازی درج اغلب با استفاده از چند خط کد پیادهسازی میشود که آن را به یک انتخاب محبوب برای مرتبسازی آرایههای کوچک تبدیل میکند. با این حال، هنگام استفاده از این الگوریتم باید پیچیدگی زمانی را در نظر گرفت.
مثال:
در اینجا نمونه ای از نحوه کار مرتب سازی درج آورده شده است. از آرایه زیر استفاده خواهیم کرد:
1، 2، 3، 4، 5، 6
الگوریتم با یافتن کوچکترین مورد در لیست، که 1 است، شروع می شود. سپس آن را در موقعیت صحیح، اولین موقعیت، قرار می دهد. سپس کوچکترین مورد بعدی را پیدا می کند که 2 است. آن را در موقعیت صحیح قرار می دهد که موقعیت دوم است.
سپس کوچکترین مورد بعدی را پیدا می کند که 3 است. آن را در موقعیت صحیح قرار می دهد که موقعیت سوم است.
سپس کوچکترین مورد بعدی را پیدا می کند که 4 است. آن را در موقعیت صحیح قرار می دهد که موقعیت چهارم است و غیره. لیست اکنون مرتب شده است!
از مثال میتوانیم ببینیم که الگوریتم برای مرتبسازی فهرست شش مقایسه و تعویض انجام میدهد. این به این دلیل است که n طول می کشد2 مقایسه و مبادله برای مرتب کردن لیستی از n مورد. در این مورد n=6.
چگونه می توان پیچیدگی زمان مرتب سازی درج را بهبود بخشید؟
در حالی که مرتبسازی درج زمان اجرا O(n) دارد2، می توان با استفاده از الگوریتم مرتب سازی بهتر، مانند مرتب سازی سریع، آن را بهبود بخشید.
Quicksort دارای زمان اجرا O(n log n) است که بسیار سریعتر از O(n است2).
با این حال، در برخی موارد، مرتبسازی درج میتواند سریعتر از مرتبسازی سریع باشد.
برای مثال، اگر فهرست از قبل مرتب باشد، مرتبسازی درج زمان کمتری نسبت به مرتبسازی سریع خواهد داشت.
در عمل، مرتبسازی درج اغلب با استفاده از چند خط کد پیادهسازی میشود که آن را به یک انتخاب محبوب برای مرتبسازی آرایههای کوچک تبدیل میکند.
با این حال، هنگام استفاده از این الگوریتم باید پیچیدگی زمانی را در نظر گرفت.
پیچیدگی های زمانی
بدترین مورد پیچیدگی O(n2):
پیچیدگی زمانی با اندازه آرایه افزایش می یابد. طول می کشد n2 مقایسه و مبادله برای مرتب کردن لیستی از n مورد.
به عنوان مثال، اگر آرایه ای به اندازه 1000 داشته باشیم، الگوریتم برای مرتب کردن آرایه، 1,000,000 مقایسه و تعویض انجام می دهد.
بهترین پیچیدگی پرونده O(n):
پیچیدگی زمانی برابر با اندازه آرایه ورودی است. من
t برای مرتب کردن لیستی از n مورد، n مقایسه و مبادله انجام می دهد. به عنوان مثال، آرایه ای به اندازه 5 را در نظر بگیرید. الگوریتم برای مرتب کردن آرایه پنج مقایسه و تعویض انجام می دهد.
میانگین پیچیدگی پرونده O(n2):
پیچیدگی زمانی بین بدترین و بهترین پیچیدگی ها در این مورد است.
طول می کشد n2 مقایسه و مبادله برای مرتب کردن لیستی از n مورد.
بنابراین، مرتبسازی درج یک الگوریتم مرتبسازی پایدار است.
چرا مرتب سازی درج پایدار است؟
مرتب سازی درج پایدار است زیرا ترتیب عناصر مساوی را در آرایه ورودی حفظ می کند.
این برای بسیاری از کاربردها، مانند بازیابی داده ها یا تجزیه و تحلیل مالی، مهم است. به عنوان مثال، اگر ما دو لیست از اعداد داریم و می خواهیم آنها را با هم مقایسه کنیم، باید مطمئن شویم که ترتیب عناصر حفظ شده است.
اگر لیست ها مرتب نشده باشند، آنها را به طور دقیق با هم مقایسه نمی کنیم.
پاسخ دهید