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

مقدمه

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

قبل از این که به ادامه بحث بپردازیم، مطالب الگوریتم های مرتب سازی را که منتشر کرده ایم را بار دیگر معرفی می کنم:

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

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

بخش مرتب شده در ابتدای کار طولی برابر با ۱ دارد و که جایگاه آن در خانه اول خواهد بود. سپس ما روی بقیه آرایه که بخش مرتب نشده است، حرکت می کنیم و عنصر مناسب را پیدا و در آن جایگاه قرار می دهیم. با تکرار رویه جستجو در بخش مرتب نشده، هر بار یک عنصر مناسب دیگر را پیدا می کنیم و در بخش مرتب شده قرار می دهیم که با این کار طول بخش مرتب یکی بیشتر می شود.

عنصر مناسبی که در هر بار جستجو تا انتهای بخش دوم (بخش مرتب نشده سمت راست آرایه) پیدا می شود، به بخش مرتب شده اضافه می شود. نحوه اضافه کردن هم به صورت هُل دادن (shift) عناصر به سمت راست است تا جایگاه عنصر خالی شود.

مثال از عملکرد مرتب سازی درجی

برای مثال، اگر در آرایه زیر بخش پررنگ، بخش مرتب شده باشد (به صورت صعودی)، ادامه اجرای الگوریتم به صورت زیر است:

۳ ۵ ۷ ۸ ۴ ۲ ۱ ۹ ۶ :

در این مرحله ۴ را به آرایه در جایگاه بعد از ۳ درج می کنیم. برای این کار با حرکت ۴ به سمت چپ خود، تمام عناصر بعد از ۳ به سمت راست Shift می شوند. به انتقال های زیر دقت کنید:

۳ ۵ ۷ x 8 ۲ ۱ ۹ ۶

۳ ۵ x 7 8 ۲ ۱ ۹ ۶

۳ x 5 7 8 ۲ ۱ ۹ ۶

۳ x 5 7 8 ۲ ۱ ۹ ۶

 

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

تصویر متحرک زیر هم اجرای بخش های مختلف الگوریتم را روی یک مثال دیگر نشان می دهد.

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

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

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

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

سپس اولین عنصر از بخش غیرمرتب (همان عنصر دوم آرایه) با آخرین عنصر بخش مرتب شده مقایسه می شود. عنصر غیرمرتب فعلی در متغیر current به طور موقت نگهداری می شود و اگر بزرگترین عنصر داخل بخش مرتب از مقدار current هم بزرگتر باشد، آن عنصر و همه سمت راستی هایش هُل داده می شوند تا جای عنصر current باز شود و به بخش مرتب شده منتقل شود.

توجه داشته باشید که این هُل دادن به این صورت است که هر عنصر به جای سمت راستی خود می نشید و در آن کپی می شود. که این کار درون حلقه داخلی while انجام شده است.

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

با تکه کد زیر هم می توانید تابع insertionSort تعریف شده را در تابعی دیگر به کار بگیرید.

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

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

در ادامه و برای بررسی پیچیدگی زمانی الگوریتم مرتب سازی درجی، به بدترین حالت ممکن در اجرا می پردازیم.

اگر در هر مرحله ما مجبور باشیم هر عنصر را در طول کل آرایه و به اندازه آن منتقل کنیم، درجه زمانی آن O(n) خواهد بود. حالا این کار را برای تمام عناصر هم انجام دهیم که این یعنی به درجه زمانی O(n^2) می رسیم.

جالب است بدانید که این بدترین حالت هم زمانی اتفاق می افتد که آرایه ای که برای مرتب سازی به الگوریتم داده می شود، از قبل به صورت معکوس مرتب باشد؛ مثلاً آرایه نزولی را برای مرتب سازی صعودی به الگوریتم بدهیم.

 

 

 

این مطلب با تلخیص از مرجع https://stackabuse.com/insertion-sort-in-java نوشته شده است.

 

 

نظرتان را برای ما بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *