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


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

چرا مرتب سازی؟

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

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

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

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

در این مقاله به بررسی انواعی از الگوریتم های مرتب سازی خواهیم پرداخت. این الگوریتم ها شامل : مرتب سازی ادغامی (Merge Sort)، مرتب سازی انتخابی، مرتب سازی سریع، مرتب سازی حبابی و مرتب سازی درجی (Insertion Sort) می شوند.

مرتب سازی انتخابی Selection Sort

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

بنابراین در حالت صعودی، این الگوریتم مرتباٌ کوچک ترین عنصر باقی مانده در لیست را پیدا می کند.

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

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

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

 

مرتب سازی درجی (Insertion Sort)

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

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

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

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

مرتب سازی حبابی (Bubble Sort)

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

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

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

در مثال، الگوریتم با مقایسه 29 و 10 شروع می کند. جابجایی صورت می گیرد. همین عملیات برای 29 و 14 تکرار می شود. این کار تا قرار گرفتن ماکزیمم مقدار (در مثال 41) انجام می شود و 41 به آخرین خانه منتقل می شود.

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

مرتب سازی ادغامی (Merge Sort)

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

در این روش لیست، مرتبا به زیر مجموعه هایی تبدیل می شود و این کار تا جایی که هر زیر مجموعه شامل تک عضو شود، ادامه می یابد. عنصر اول هر زیر مجموعه با عناصر دیگر همان زیر مجموعه مقایسه و در صورت نیاز جابجا می گردد.

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

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

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

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

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

مرتب سازی سریع

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

هر کدام از عناصر ارایه می توانند عنصر محوری باشند اما برای سهولت عنصر اولی عنصر محوری در نظر گرفته می شود.

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

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

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

 

کدام الگوریتم مرتب سازی را انتخاب کنیم؟

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

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

به این پست امتیاز دهید

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

میانگین امتیاز / 5. تعداد:

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

  1. AffiliateLabz گفت:

    Great content! Super high-quality! Keep it up! 🙂

    1. نسیم نژند گفت:

      🙏🙏

دیدگاهتان را بنویسید

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

Enter Captcha Here : *

Reload Image