الگوریتم مرتب سازی درجی (Insertion Sort Algorithm) — به زبان ساده و جامع

در این مقاله می‌خواهیم درمورد الگوریتم مرتب سازی درجی صحبت کنیم. این الگوریتم به خاطر سادگی و کارایی‌اش در مرتب سازی داده‌های کوچک یا تقریباً مرتب شده، حائز اهمیت است. این الگوریتم، علیرغم محدودیت‌هایی که در برابر داده‌های حجیم دارد، در توسعه وب و کاربردهای بلادرنگ، راه‌حلی عملی و مناسب ارائه می‌دهد.

مقدمه‌ای بر مرتب سازی

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

چرا مرتب سازی در علوم داده و برنامه نویسی مهم است؟

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

معرفی کلی الگوریتم‌های مرتب سازی

الگوریتم‌های مرتب سازی روش‌هایی هستند که برای مرتب‌کردن مجموعه‌ای از داده‌ها بر اساس ترتیب خاصی (معمولاً صعودی یا نزولی) طراحی شده‌اند. این الگوریتم‌ها از نظر نحوه‌ی عملکرد، پیچیدگی زمانی، میزان مصرف حافظه و پایداری با یکدیگر تفاوت دارند. از جمله رایج‌ترین آن‌ها می‌توان به مرتب سازی حبابی (Bubble Sort)، مرتب سازی انتخابی (Selection Sort)، مرتب سازی درجی (Insertion Sort)، مرتب سازی سریع (Quick Sort)، مرتب سازی ادغامی (Merge Sort) و مرتب سازی درختی (Heap Sort) اشاره کرد. انتخاب الگوریتم مناسب، به حجم داده، نوع داده‌ها و نیاز به پایداری بستگی دارد.

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

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

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

ویژگی مهم این الگوریتم آن است که هر بار فقط یک عنصر به بخش مرتب‌شده اضافه می‌شود و این عملیات از طریق مقایسه با عناصر قبلی و جابه‌جایی انجام می‌گیرد. اگر عنصر جدید کوچکتر از عناصر قبلی باشد، آن‌ها یکی یکی به سمت راست منتقل می‌شوند تا جای مناسب برای درج عنصر جدید پیدا شود. الگوریتم درجی به‌دلیل سادگی و عملکرد خوبش در آرایه‌های کوچک یا تقریباً مرتب، در بسیاری از کاربردهای واقعی به‌خصوص در مرتب سازی درجا (in-place) و بلادرنگ استفاده می‌شود.

• پاورپوینت مقایسه الگوریتم های مرتب سازی (Sorting algorithm) — کلیک کنید

مقایسه با مرتب سازی کارت‌های بازی در دست انسان

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

الگوریتم Insertion Sort چگونه کار می‌کند؟

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

نحوه عملکرد الگوریتم مرتب سازی درجی (بررسی کامل)

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

۱- فرض مرتب بودن اولین عنصر

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

۲- مقایسه عنصر بعدی با عناصر قبلی

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

۳- درج عنصر در جای مناسب

پس از مقایسه و یافتن موقعیت مناسب، عنصر جدید در جای خود قرار می‌گیرد. برای قرار دادن عنصر در جای خود، تمامی عناصر بزرگ‌تر از آن به سمت راست جابجا می‌شوند تا فضایی برای قرار گرفتن عنصر جدید در بخش مرتب‌شده ایجاد شود. این جابجایی‌ها ممکن است چندین بار انجام شوند تا جایگاه دقیق عنصر موردنظر تعیین گردد.

۴- تکرار تا پایان لیست

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

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

پاورپوینت تکنیک های مرتب سازی

کلیک کنید

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

برای فهمیدن هرچه بهتر نحوه عملکرد الگوریتم مرتب سازی درجی، بیایید با یک مثال مسئله را توضیح دهیم. فرض کنید یک آرایه‌ای دارید که نامرتب است، و می‌خواهید به کمک این الگوریتم این آرایه را مرتب کنید. ابتدا آرایه را در نظر می‌گیریم، برای مثال: [۶ ,۵ ,۱۳ ,۱۱ ,۱۲]

همانطور که می‌دانید، یک آرایه را از چپ به راست می‌خوانیم. در این مثال اولین عنصر آرایه ما ۱۲ است. در ادامه به صورت مرحله به مرحله مرتب سازی را توضیح خواهیم داد.

مرحله اول: فرض مرتب بودن اولین عنصر در ابتدا

اولین عنصر آرایه یعنی ۱۲ به عنوان بخش مرتب‌شده در نظر گرفته می‌شود. بنابراین، بخش مرتب‌شده‌ی آرایه [۱۲] است و بخش باقی‌مانده‌ی آرایه [۶ ,۵ ,۱۳ ,۱۱] به طور ناصحیح قرار دارد.

مرحله دوم: مقایسه و درج عنصر دوم (۱۱)

عنصر بعدی ۱۱ باید با اولین عنصر مقایسه شود.

• چون ۱۱ از ۱۲ کوچک‌تر است، ۱۱ باید در جایگاه خود در ابتدا قرار گیرد.
• در نتیجه، ۱۲ به سمت راست جابجا می‌شود و آرایه به صورت زیر تغییر می‌کند: [۶ ,۵ ,۱۳ ,۱۲ ,۱۱]

حالا بخش مرتب‌شده آرایه [۱۲, ۱۱] است.

مرحله سوم: مقایسه و درج عنصر سوم (۱۳)

عنصر ۱۳ باید با بخش مرتب‌شده [۱۲, ۱۱] مقایسه شود.

• چون ۱۳ بزرگ‌تر از ۱۲ است، هیچ جابجایی لازم نیست و ۱۳ در جایگاه خود باقی می‌ماند.
• آرایه تغییری نمی‌کند و همچنان به صورت زیر باقی می‌ماند: [۶ ,۵ ,۱۳ ,۱۲ ,۱۱]

حالا بخش مرتب‌شده آرایه [۱۳ ,۱۲ ,۱۱] است.

مرحله چهارم: مقایسه و درج عنصر چهارم (۵)

عنصر ۵ باید با تمام عناصر بخش مرتب‌شده [۱۳ ,۱۲ ,۱۱] مقایسه شود.

• ابتدا ۵ با ۱۳ مقایسه می‌شود و چون ۵ از ۱۳ کوچک‌تر است، ۱۳ به سمت راست جابجا می‌شود.
• سپس ۵ با ۱۲ مقایسه می‌شود و چون ۵ از ۱۲ کوچک‌تر است، ۱۲ به سمت راست جابجا می‌شود.
• در نهایت، ۵ با ۱۱ مقایسه می‌شود و چون ۵ از ۱۱ کوچک‌تر است، ۱۱ نیز به سمت راست جابجا می‌شود.
• در نهایت، ۵ در ابتدا قرار می‌گیرد.
• آرایه به این صورت تغییر می‌کند: [۶ ,۱۳ ,۱۲ ,۱۱ ,۵]

حالا بخش مرتب‌شده آرایه [۱۳ ,۱۲ ,۱۱ ,۵] است.

مرحله پنجم: مقایسه و درج عنصر پنجم (۶)

عنصر ۶ باید با تمام عناصر بخش مرتب‌شده [۱۳ ,۱۲ ,۱۱ ,۵] مقایسه شود.

• ابتدا ۶ با ۱۳ مقایسه می‌شود و چون ۶ از ۱۳ کوچک‌تر است، ۱۳ به سمت راست جابجا می‌شود.
• سپس ۶ با ۱۲ مقایسه می‌شود و چون ۶ از ۱۲ کوچک‌تر است، ۱۲ به سمت راست جابجا می‌شود.
• در نهایت، ۶ با ۱۱ مقایسه می‌شود و چون ۶ از ۱۱ کوچک‌تر است، ۱۱ به سمت راست جابجا می‌شود.
• سپس ۶ در جایگاه مناسب خود بین ۵ و ۱۱ قرار می‌گیرد.
• آرایه به این صورت تغییر می‌کند: [۱۳ ,۱۲ ,۱۱ ,۵ ,۶]

حالا بخش مرتب‌شده آرایه [۱۳ ,۱۲ ,۱۱ ,۵ ,۶] است.

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

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

پیچیدگی زمانی

پیچیدگی زمانی یک الگوریتم به ما نشان می‌دهد که زمان اجرای الگوریتم چگونه با افزایش تعداد داده‌ها تغییر می‌کند. الگوریتم مرتب سازی درجی، به دلیل نحوه‌ی مقایسه و جابجایی مداوم عناصر، پیچیدگی زمانی متغیری دارد. در بهترین حالت که داده‌ها به صورت مرتب شده وارد می‌شوند (یا تقریباً مرتب باشند)، الگوریتم تنها نیاز به یک مقایسه برای هر عنصر دارد، که باعث می‌شود پیچیدگی زمانی در این حالت برابر با O(n) باشد. در حالت متوسط و بدترین حالت، که داده‌ها به طور تصادفی یا به صورت معکوس مرتب شده‌اند، الگوریتم باید برای هر عنصر با تمامی عناصر قبلی مقایسه کند و در نتیجه پیچیدگی زمانی برابر با O(n^۲) خواهد بود. بنابراین، الگوریتم مرتب سازی درجی در شرایط مختلف می‌تواند زمان‌های متفاوتی داشته باشد.

پیچیدگی فضایی

پیچیدگی فضایی به مقدار حافظه‌ای که الگوریتم برای اجرای خود نیاز دارد اشاره دارد. الگوریتم مرتب سازی درجی یکی از الگوریتم‌های درجا (in-place) است، به این معنی که این الگوریتم داده‌ها را درون خود آرایه مرتب می‌کند و نیازی به استفاده از فضای اضافی برای ذخیره‌سازی داده‌ها ندارد. به عبارت دیگر، این الگوریتم به حافظه اضافی نیاز ندارد و تنها از فضای ثابت برای مقایسه و جابجایی داده‌ها استفاده می‌کند. در نتیجه، پیچیدگی فضایی آن برابر با O(1) است. این ویژگی باعث می‌شود که الگوریتم از نظر استفاده از حافظه بسیار کارآمد باشد، به ویژه در مواردی که مقدار حافظه محدود است و نیازی به فضای اضافی برای ذخیره‌سازی داده‌ها وجود ندارد.

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

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

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

الگوریتم مرتب سازی درجی به دلیل سادگی پیاده‌سازی، پایداری (که در آن ترتیب عناصر با مقادیر یکسان حفظ می‌شود)، و سازگاری با داده‌های نیمه‌مرتب (که در آن داده‌ها کمتر نیاز به جابجایی دارند)، از مزایای قابل توجهی برخوردار است. همچنین، این الگوریتم برای آرایه‌های کوچک بسیار مناسب است و می‌تواند به راحتی در کاربردهایی که داده‌ها به تدریج وارد می‌شوند، عمل کند.

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

با وجود مزایای آن، الگوریتم مرتب سازی درجی در داده‌های بزرگ به شدت ناکارآمد است. پیچیدگی زمانی آن در بدترین حالت O(n^۲) است، که باعث می‌شود در صورت استفاده از داده‌های بزرگ، عملکرد آن به طور قابل توجهی کاهش یابد. همچنین در مقایسه با الگوریتم‌های پیچیده‌تر مانند مرتب سازی سریع (Quick Sort) یا مرتب سازی ادغامی (Merge Sort)، از نظر کارایی ضعیف‌تر است.

پاورپوینت الگوریتم مرتب سازی موازی برای اتوماتای سلولی خطی

کلیک کنید

نتیجه گیری

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