وبلاگ رسمی مهدی غلامی میاندهی

تابع مرتب سازی انتخابی(Selection Sort) در ++C

مرتب‌سازی انتخابی یکی از انواع الگوریتم مرتب‌سازی می‌باشد که جزو دستهٔ الگوریتمهای مرتب‌سازی مبتنی بر مقایسه‌است.این الگوریتم دارای پیچیدگی زمانی از درجهٔ (O(n ² است که به همین دلیل اعمال آن روی مجموعهٔ بزرگی از اعداد کارا به نظرنمی رسد و به طور عمومی ضعیفتر از نوع مشابهش که مرتب‌ساز درجی است عمل می‌کند.این مرتب سازی به دلیل سادگی اش قابل توجه‌است.

ویژگی‌های مرتب‌سازی انتخابی

1-با توجه به قطعه کد نوشته شده، ترتیب عناصر تغییری در عملکرد آن اینجا نمی‌کند. یعنی این الگوریتم برای داده‌های کاملا مرتب، نامرتب تصادفی و مرتب معکوس به یک ترتیب عمل کرده و تمام مقایسه‌های محاسبه شده در رابطه فوق را انجام می‌دهد. بنابراین پیچیدگی این الگوریتم در بهترین حالت و حالت منوسط نیز ( Θ( n ² است.

2- مرتب‌سازی انتخابی یک روش مرتب‌سازی درجا است. یعنی عملیات مرتب‌سازی به در داخل خود لیست و بدون نیاز به حافظه کمکی بزرگ انجام می‌گیرد.

3- در پیاده‌سازی مرتب‌سازی انتخابی به روش فوق، اگر دو عنصر با مقدار بیشینه داشته باشیم، اولی انتخاب شده و به انتهای لیست منتقل می‌شود. در نتیجه ترتیب آنها به هم می‌خورد. بنابراین این پیاده‌سازی روش پایدار نیست. در روش پایدار ترتیب عناصر با مقدار یکسان تغییر نمی‌کند. اما اگر در مقایسه عناصر آرایه به جای > از => استفاده کنید، مرتب‌سازی پایدار خواهد شد.