قسمت ۳ دوره الگوریتم و ساختمان داده: مرتب سازی انتخابی (Selection Sort)

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

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

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

نحوه عملکرد Selection Sort

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

مثال ساده: مرتب‌سازی یک آرایه

فرض کنید می‌خواهیم آرایه زیر را مرتب کنیم:
[29, 10, 14, 37, 13]

• در گام اول، کوچک‌ترین عدد پیدا شده (10) با اولین عدد (29) جابه‌جا می‌شود:
  [10, 29, 14, 37, 13]
• در گام دوم، کوچک‌ترین عدد باقی‌مانده (13) با دومین عدد (29) جابه‌جا می‌شود:
  [10, 13, 14, 37, 29]
• این روند ادامه می‌یابد تا لیست به شکل نهایی خود مرتب شود:
  [10, 13, 14, 29, 37]

مزایا و معایب Selection Sort

مزایا:

• ساده و قابل فهم.
• مناسب برای آرایه‌های کوچک.

معایب:

• کارایی پایین در آرایه‌های بزرگ به دلیل پیچیدگی زمانی O(n^2).
• تعداد مقایسه‌ها زیاد است و برای داده‌های بزرگ ناکارآمد می‌شود.

کاربردهای Selection Sort

1. آموزش مفاهیم مرتب‌سازی: این الگوریتم به دلیل سادگی، ابزار مناسبی برای یادگیری الگوریتم‌های مرتب‌سازی است.
2. مرتب‌سازی لیست‌های کوچک: اگر تعداد عناصر لیست کم باشد، Selection Sort گزینه مناسبی است.

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

• پیچیدگی زمانی: بهترین حالت: O(n^2) - بدترین حالت: O(n^2)
  
• پیچیدگی مکانی:O(1) (این الگوریتم نیاز به فضای اضافی ندارد.)
  

نتیجه‌گیری

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

📌 برای مشاهده فیلم آموزشی این قسمت و دسترسی کامل به دوره، به لینک زیر مراجعه کنید:
لینک ویدئو در یوتیوب

برای تماشا قسمت چهارم این مقاله، اینجا را کلیک کنید

✨ اگر این مقاله برای شما مفید بود، آن را با دوستان برنامه‌نویس خود به اشتراک بگذارید. منتظر نظرات و سوالات شما هستم! 🌟