آشنایی با مرتب سازی انتخابی (Selection Sort) در ساختمان داده ها

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

همان طور که از نام این روش پیداست باید بزرگ ترین یا کوچک ترین عنصر را در بین ورودی ها پیدا نمائیم .

برای مثال : اگر اعداد ۱۱ – ۳۳ – ۵۵ – ۲۲ – ۹۹ – ۴۴ را داریم و می خواهیم به صورت صعودی آن ها را با استفاده از روش انتخابی مرتب نمائیم :

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

مرحله اول مرتب سازی : ۹۹ – ۳۳- ۵۵ – ۲۲ – ۱۱ – ۴۴ می باشد.

در مرحله بعد دوباره عنصر اول را به عنوان بزرگترین در نظر می گیریم و سپس آن را با عناصر دیگر مقایسه می کنیم اما در این مرحله تا n-1 پیش می رویم یعنی عنصر آخری را در مقایسه شرکت نمی دهیم .

مرحله دوم مرتب سازی : ۹۹ – ۵۵ – ۳۳- ۲۲- ۱۱- ۴۴

مرحله سوم مرتب سازی : ۹۹ – ۵۵ – ۴۴ – ۲۲ – ۱۱ – ۳۳

مرحله چهارم مرتب سازی : ۹۹ – ۵۵ – ۴۴ – ۳۳ – ۱۱ – ۲۲

مرحله پنجم مرتب سازی : ۹۹ – ۵۵ – ۴۴ – ۳۳ – ۲۲ – ۱۱

همانطور که ملاحظه شد با ۶ ورودی ؛ ۵ مرحله پیش رفتیم و در مرحله اول ۵ مقایسه ، در مرحله دوم ۴ ، در مرحله سوم ۳ ، در محله چهارم ۲ مقایسه و در مرحله آخر ۱ مقایسه صورت گرفت. یعنی در صورت داشتن n عدد ورودی:

(n-1) + …. +۱ +۲ + ۳

مقایسه صورت می گیرد . مرتبه اجرایی این روش از لحاظ مقایسه در بهترین ، حالت متوسط و بدترین حالت O(n^2) می باشد اما  مرتبه اجرایی از لحاظ تعویض در بهترین حالت O(1)  و در سایر حالات O(n)  می باشد.

 

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

 

دیدگاهتان را بنویسید

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