الگوریتم مرتب سازی انتخابی (Selection Sort)

  • پنج شنبه ۹ آبان ۱۳۹۸
  • بازدید ۴۷ نفر

selection sort algorithm 7309 تصویر

الگوریتم مرتب سازی انتخابی (Selection Sort)

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

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

  • زیر آرایه ای که مقادیر مرتب شده در آن قرار می گیرند.
  • زیر آرایه ای که مقادیر نامرتب در آن قرار دارند.

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

فلوچارت الگوریتم مرتب سازی انتخابی

Selection sort flowchart 7309 تصویر

مثال

پیاده سازی الگوریتم Selection Sort با زبان C++:

امتحان کنید

خروجی:

نکات

  • پیچیدگی زمانی این الگوریتم برابر با O(n2) است.
  • فضای موقت برابر با O(1) است.
  • یکی از مزایای Selection Sort این است که هرگز بیشتر از O(n) تعویض انجام نمی دهد. این موضوع برای زمانی که مقدار حافظه محدودی داریم، مناسب است.
ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

هیچ نظری ثبت نشده است