الگوریتم مرتب سازی درجی Insertion Sort

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



الگوریتم مرتب سازی درجی

• در مرتب سازی درجی، ابتدا عنصر دوم با عنصر اول لیست مقایسه می‌شود و در صورت لزوم با عنصر اول جابجا می‌شود به طوری که عناصر اول و دوم تشکیل یک لیست مرتب دوتایی را بدهند. سپس عنصر سوم به ترتیب با دو عنصر قبلی خود یعنی عناصر دوم و اول مقایسه و درجای مناسبی قرار می‌گیرد به طوری که عناصر اول و دوم و سوم تشکیل یک لیست مرتب سوم و دوم و اول مقایسه و درجای مناسب قرار می‌گیرد به طوری که عناصر اول و دوم و سوم و چهارم تشکیل یک لسیت مرتب چهارتایی را بدهند و در حالت کلی عناصر i ام با i-1 عنصر قبلی خود مقایسه می‌گردد تا در مکان مناسب قرار گیرد به طوری که i عنصر تشکیل یک لیست مرتب i تایی را بدهند و این روند تا مرتب شدن کامل لیست ادامه می‌یابد. یا به صورت دقیق تر:
• مرحلهٔ 1:[1]A خودش به طور بدیهی مرتب است.
• مرحلهٔ 2:[2]A را یا قبل از یا بعد از [1]A درج می‌کنیم طوری که [1]A و [2]A مرتب شوند.
• مرحلهٔ 3:[3]A را در مکان صحیح در [1]A و [2]A درج می‌کنیم به گونه‌ای که [1]Aو [2]A و[3]A مرتب شده باشند.
• مرحله A[n]:n را در مکان صحیح خود در [1]Aو [2]A و... و[A[n-1 به گونه‌ای درج می‌کنیم که کل آرایه مرتب باشد.
• زمان اجرای الگوریتم مرتب سازی درجی از(O(n^2 است.
• این الگوریتم از الگوریتم‌های پایدار می‌باشد و در یک آرایهٔ کاملا مرتب بهترین حالت را دارد و برای یک آرایهٔ مرتب شده معکوس بدترین حالت را دارد.
• ثابت شده‌است که برای nهای کوچکتر از 20 مرتب سازی درجی سریع ترین روش مرتب سازی است.

پیچیدگی زمانی مرتب‌سازی درجی

بدترین حالت این الگوریتم زمانی اتفاق می‌افتد که لیست به صورت معکوس مرتب باشد. در این حالت حلقه داخلی در مرحله اول یک بار، در مرحله دوم دو بار، در مرحله سوم سه بار، و در حالت کلی در مرحله iام (i < n) به تعداد i بار تکرار می‌شود. پس اگر ( T( n تعداد مقایسه‌های حلقه داخلی به ازای n عنصر را نشان دهد، می‌توان نوشت:

 

T( n ) = 1 + 2 + 3 + ... + (n - 1) = n ( n - 1 ) / 2 ≈ n² / 2

 

که از مرتبه اجرای ( Θ( n² است.

بهترین حالت الگوریتم زمانی است است که لیست از پیش مرتب‌شده باشد. در این حالت هر حلقه درونی با یکبار مقایسه خاتمه پیدا می‌کند. در نتیجه تعداد کل مقایسه‌ها از مرتبه ( Θ( n خواهد بود.

حالت متوسط برای شرایطی که عناصر به صورت تصادفی پخش شده باشند محاسبه می‌شود. در این حالت در هر تکرار حلقه بیرونی، حلقه داخلی برای یافتن محل مناسب درج عنصر جدید به طور میانگین نصف لیست مرتب‌شده را پیمایش می‌کند. در نتیجه حدود n² / 4 مقایسه صورت خواهد گرفت (چرا؟). این تعداد اگرچه از مرتبه اجرایی ( Θ( n² است، اما در مقایسه با بدترین حالت (تقریبا n² / 2 مقایسه) عملکرد بهتری را نشان می‌دهد.

ویژگی‌های مرتب‌سازی درجی

1- پیچیدگی زمانی الگوریتم مرتب‌سازی درجی در بدترین حالت و حالت متوسط ( Θ( n²، و در بهترین حالت ( Θ( n است.

2- یکی از ویژگی‌های مهم مرتب‌سازی درجی این است که در حالت متوسط برای درج عنصر جدید در لیست مرتب‌شده نیاز به مقایسه عنصر با تمامی عناصر ندارد. به همین دلیل کارآیی آن در مقایسه با بدترین حالت بهتر است. از سوی دیگر، این روش برای مرتب کردن عناصر به جای عمل جابجایی - که نیاز به سه عمل اصلی مقداردهی دارد - از کپی کردن استفاده می‌کند. در این روش ابتدا مقدار عنصر جدید در یک متغیر کمکی (در قطعه کد فوق متغیر t) ذخیره شده و جابجا کردن عناصر بزرگتر به انتهای لیست با یک عمل اصلی انجام می‌گیرد. در انتها نیز مقدار عنصر جدید در محل مناسب درج می‌شود. در چنین حالتی تعداد اعمال اصلی انچام شده کمتر از تعداد اعمال مورد نیاز در عمل جابجایی است. به همین دلیل این روش به روش‌های مقدماتی دیگر (مانند روش مرتب‌سازی حبابی و انتخابی) ارجحیت داشته و در مراحل نهایی مرتب‌سازی‌های پیشرفته (مانند روش مرتب‌سازی سریع) از این روش به عنوان روش مرتب‌سازی جایگزین استفاده می‌شود. اگر تعداد عناصر لیست کمتر از بیست عنصر باشد، این روش در مقایسه بار روش‌های متداول مرتب‌سازی سریعتر عمل می‌کند.

3- حافظه مصرفی مرتب‌سازی درجی از مرتبه ( Θ( 1  بوده و مستقل از اندازه لیست است. چنین الگوریتمی را مرتب‌سازی درجا گویند.

4- در صورتی که مرتب‌سازی درجی به صورت قطعه‌کد فوق پیاده‌سازی شود، یک مرتب‌سازی پایدار خواهد بود. یعنی ترتیب عناصر با مقادیر یکسان در حین مرتب‌سازی تغییر نمی‌کند. اما اگر به جای شرط [ t >= arr[ j - 1 از شرط [ t > arr[ j - 1 استفاده شود، الگوریتم ناپایدار خواهد شد.

خب این یه سری اموزش هایی بود که تو اینترنت پیدا کردم و خوب توضیح داده بودن. به نظر من موقع یاد گرفتن الگوریتم اگه دیدید نمی فهمید بهترین کار اینه که انیمیشنشو پیدا کنید و نگاه کنید. اون موقع خیلی راحت تر یاد می گیرید. به خاطر همین من یه سری لینک که به صورت انیمشن هست رو براتون می ذارم تا الگوریتم مرتب سازی درجی رو بهتر بهتر و راحت تر یاد بگیرید.

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

لینک یک

لینک دو 

لینک سه

منابع :

سایت ویکی پدیا

سایت الگوریتم ها