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

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

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

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

اساساً، یک الگوریتم مرتب‌سازی یک برنامه کامپیوتری است که داده‌ها را به ترتیب خاصی، مانند ترتیب حروف الفبا یا ترتیب عددی، معمولاً صعودی یا نزولی، سازمان‌دهی(مرتب) می‌کند.

الگوریتم های مرتب سازی برای چه مواردی استفاده می شوند؟

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

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

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

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

انواع مختلف مرتب سازی در ساختارهای داده

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

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

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

• مرتب سازی حبابی

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

مرتب‌سازی حبابی گاهی اوقات به عنوان "مرتب‌سازی sinking " نیز شناخته می‌شود.

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

• مرتب سازی insertion

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

نحوه کار کردن این مرتب سازی :لیست مرتب شده جزئی در ابتدا فقط شامل اولین آیتم در لیست است. با هر تکرار، یک آیتم از داده های ورودی "هنوز برای سفارش بررسی نشده" حذف می شود و در لیست مرتب شده insertion می شود.

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

یک الگوریتم مرتب‌سازی محبوب تقسیم کنید و بر اساس اصل تقسیم‌بندی یک آرایه به دو آرایه فرعی است - یکی حاوی آیتم های کوچک‌تر از آیتم pivot و دیگری حاوی آیتم های بزرگ‌تر از آیتم pivot است. سپس دو آرایه فرعی به صورت بازگشتی مرتب می شوند.

مراحل اساسی مرتب سازی سریع عبارتند از:

1. یک آیتم pivot از آرایه را انتخاب کنید.
2. آرایه را به دو آرایه فرعی تقسیم کنید، یکی حاوی آیتم های کوچکتر از پیوت و دیگری حاوی آیتم های بزرگتر از pivot.
3. با استفاده از مرتب سازی سریع، دو آرایه فرعی را به صورت بازگشتی مرتب کنید.
4. دو آرایه فرعی مرتب شده را با هم ترکیب کنید.

• مرتب سازی bucket

مرتب‌سازی bucket یک الگوریتم مفید برای مرتب‌سازی داده‌های توزیع شده یکنواخت است و به راحتی می‌توان آن را برای بهبود عملکرد موازی کرد.

مراحل اساسی مرتب سازی bucket عبارتند از:

1. آرایه ای از آیتم های خالی ایجاد کنید.
2. داده های ورودی را طبق یک تابع تعریف شده در سطل ها پراکنده کنید.
3. هر سطل را با استفاده از الگوریتم دیگری یا به صورت بازگشتی با مرتب سازی bucket مرتب کنید.
4. آیتم های مرتب شده را از هر سطل در آرایه اصلی جمع آوری کنید.

• مرتب سازی shell

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

• مرتب سازی ادغام

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

منبع:10 تا از بهترین الگورتیم های مرتب سازی در پایتون

آموزش برنامه نویسی _ anophel

ما را در شبکه های اجتماعی دنبال کنید:

تلگرام: anophel

اینستاگرام: anophel

یوتیوب: anophel