
الگوریتمهای مرتبسازی بخش اساسی علوم کامپیوتر هستند و کاربردهای مختلفی دارند، از مرتبسازی دادهها در دیتابیس ها گرفته تا سازماندهی لیستهای پخش موسیقی. اما الگوریتم های مرتب سازی دقیقا چیست و چگونه کار می کنند؟ ما در این مقاله با ارائه نگاهی جامع به انواع مختلف الگوریتم ها و کاربرد آنها، از جمله کد نمونه، به این سوال پاسخ خواهیم داد.
قبل از اینکه شروع کنیم ما در این مقاله به صورت یکم تخصصی بررسی خواهیم کرد پس استفاده از نماد O بزرگ برای تجزیه و تحلیل پیچیدگی زمانی و پیچیدگی فضایی الگوریتمهای مختلف می باشد. اما ما همچنین مرورهای سطح بالایی را ارائه خواهیم کرد که باید به راحتی توسط اکثر افراد قابل درک باشد.
اساساً، یک الگوریتم مرتبسازی یک برنامه کامپیوتری است که دادهها را به ترتیب خاصی، مانند ترتیب حروف الفبا یا ترتیب عددی، معمولاً صعودی یا نزولی، سازماندهی(مرتب) میکند.
الگوریتمهای مرتبسازی عمدتاً برای مرتب کردن مجدد مقادیر زیادی از دادهها به شیوهای کارآمد استفاده میشوند تا بتوان آنها را راحتتر جستجو و تغییراتی در آن ایجاد کرد. آنها همچنین برای بهبود کارایی الگوریتم های دیگر مانند جستجو و ادغام، که بر داده های مرتب شده برای عملیات خود متکی هستند، استفاده می شوند.
الگوریتم های مرتب سازی برای سازماندهی داده ها در یک ترتیب خاص استفاده می شوند که جستجو، دسترسی و تجزیه و تحلیل را آسان تر می کند. در بسیاری از کاربردها، مرتبسازی بخش مهمی از قسمت پردازش داده است و کارایی الگوریتم مرتبسازی میتواند تأثیر قابلتوجهی بر عملکرد کلی سیستم داشته باشد.
انواع مختلفی از مرتب سازی موجود است. انتخاب الگوریتم مرتب سازی به عوامل مختلفی مانند اندازه مجموعه داده ها، نوع داده های مرتب شده و پیچیدگی زمانی و مکانی مورد نظر بستگی دارد.
بیایید اکنون ده مورد از بهترین الگوریتم های مرتب سازی را بررسی کنیم تا هنگام انتخاب یکی از آنها آگاه باشیم.
مرتبسازی حبابی(Bubble Sort) یک الگوریتم مرتبسازی ساده است که به طور مکرر لیست مشخصی از آیتمها را طی میکند، هر جفت از آیتمهای کنار هم(مجاور) را با هم مقایسه میکند و اگر ترتیب نامناسبی داشتند، آنها را تعویض میکند. این الگوریتم تا زمانی ادامه مییابد که از کل لیست بدون تعویض کردن از هیچ موردی عبور کند.
مرتبسازی حبابی گاهی اوقات به عنوان "مرتبسازی sinking " نیز شناخته میشود.
نحوه کار : از ابتدای لیست شروع می کند، هر جفت مجاور را با هم مقایسه کنید، اگر ترتیب درستی ندارند، موقعیت آنها را عوض می کند. پس از هر تکرار، یک آیتم کمتر برای مقایسه لازم است، تا زمانی که دیگر آیتمی برای مقایسه باقی نماند.
مرتبسازی insertion الگوریتم ساده دیگری است که آرایه مرتبشده نهایی را هر بار یک آیتم میسازد، و به دلیل نحوه قرار دادن آیتم های کوچکتر در موقعیتهای صحیح خود در آرایه مرتبشده، به این شکل نامگذاری شده است.
نحوه کار کردن این مرتب سازی :لیست مرتب شده جزئی در ابتدا فقط شامل اولین آیتم در لیست است. با هر تکرار، یک آیتم از داده های ورودی "هنوز برای سفارش بررسی نشده" حذف می شود و در لیست مرتب شده insertion می شود.
یک الگوریتم مرتبسازی محبوب تقسیم کنید و بر اساس اصل تقسیمبندی یک آرایه به دو آرایه فرعی است - یکی حاوی آیتم های کوچکتر از آیتم pivot و دیگری حاوی آیتم های بزرگتر از آیتم pivot است. سپس دو آرایه فرعی به صورت بازگشتی مرتب می شوند.
مراحل اساسی مرتب سازی سریع عبارتند از:
مرتبسازی bucket یک الگوریتم مفید برای مرتبسازی دادههای توزیع شده یکنواخت است و به راحتی میتوان آن را برای بهبود عملکرد موازی کرد.
مراحل اساسی مرتب سازی bucket عبارتند از:
مرتبسازی shell از یک الگوریتم مرتبسازی insertion استفاده میکند، اما به جای مرتبسازی کل لیست به یکباره، لیست به لیستهای فرعی کوچکتر تقسیم میشود. سپس این زیر لیست ها با استفاده از یک الگوریتم مرتب سازی insertion مرتب می شوند، بنابراین تعداد تبادلات مورد نیاز برای مرتب سازی لیست کاهش می یابد.
ایده اصلی مرتب سازی ادغام این است که لیست ورودی را به نصف تقسیم کنید، هر نیمه را به صورت بازگشتی با استفاده از مرتب سازی ادغام مرتب کنید، و سپس دو نیمه مرتب شده را دوباره با هم ادغام کنید. مرحله ادغام با مقایسه مکرر اولین آیتم هر نیمه و افزودن آیتم کوچکتر از این دو به لیست مرتب شده انجام می شود. این فرآیند تا زمانی که همه آیتم های با هم ادغام شوند تکرار می شود.
منبع:10 تا از بهترین الگورتیم های مرتب سازی در پایتون
آموزش برنامه نویسی _ anophel
ما را در شبکه های اجتماعی دنبال کنید:
تلگرام: anophel
اینستاگرام: anophel
یوتیوب: anophel