برنامه نویسی 141 بازدید

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

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

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

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

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

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

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

مرتب‌سازی انتخابی

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

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

مرتب‌سازی درجی

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

مرتب‌سازی ادغامی یک نمونه کاملاً عالی از الگوریتم تقسیم و حل (Divide and Conquer) محسوب می‌شود. در این روش مرتب سازی صرفاً از 2 مرحله آن الگوریتم استفاده می‌شود که شامل تقسیم پیوسته و ادغام مکرر است.

تقسیم پیوسته

در این مرحله لیست نامرتب به طور پیوسته تقسیم می‌شود تا این که به N زیرمجموعه برسیم. در این حالت هر زیرمجموعه 1 عنصر دارد که نامرتب است و N تعداد عناصر لیست اصلی است.

ادغام مکرر

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

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

مرتب‌سازی سریع (Quick Sort)

مرتب‌سازی سریع نیز یک الگوریتم «تقسیم و حل» مانند مرتب‌سازی ادغامی است. با این که این روش کمی پیچیده‌تر است؛ اما در اغلب موارد، پیاده‌سازی استاندارد آن به طور قابل توجهی سریع‌تر از مرتب‌سازی ادغامی عمل می‌کند و به ندرت به پیچیدگی بدترین حالت خود یعنی $$O(n^2)$$ می‌رسد. این روش مرتب‌سازی 3 مرحله به صورت زیر دارد.

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

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

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

==

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

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