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

مقدمه

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

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

شرح الگوریتم مرتب سازی انتخابی

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

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

مثال از روند اجرای مرتب سازی انتخابی

به مثال زیر دقت کنید:

  • ۳ ۵ ۱ ۲ ۴
  • ۱ ۵ ۳ ۲ ۴
  • ۱ ۲ ۳ ۵ ۴
  • ۱ ۲ ۳ ۵ ۴
  • ۱ ۲ ۳ ۴ ۵
  • ۱ ۲ ۳ ۴ ۵

بخش پر رنگ تر در لیست اعداد، در واقع همان بخش مرتب شده است.

پیاده سازی مرتب سازی انتخابی

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

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

بنابراین آن کوچکترین عنصر بخش مرتب نشده به انتهای بخش مرتب شده اضافه می شود و با این کار طول بخش مرتب شده یکی اضافه می شود و از طول بخش مرتب نشده کاسته می شود.

با تکرار این کار به اندازه تعداد عناصر، آرایه مرتب شده به دست می آید.

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

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

پس درجه زمانی الگوریتم مرتب سازی انتخابی O(n^2) است.

 

 

نظرتان را برای ما بنویسید

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