الگوریتم مرتب‌سازی انتخابی
یک بخشی به وبلاگ اضافه نمودم به نام الگوریتم و ساختار داده ها در رشته نرم افزار که چالشی جدید رو برایم در زمینه مطالعه کتاب های سالها قبل بوجود آورد . امسال در شرکتی که دوستم کار میکرد رفتم و از قضا یک فرم استخدامی دیدم که برای استخدام مبتدی ها و مید لول و سنیور دسته بندی شده بود و هرکدوم حدودا 8 صفحه بود . سوالات این بخش از رو چندتاش رو خوندم دیدم راحت هستش و بعضی ها هم خیلی سخت بود انصافا .
شروع کردم به مطالعه در مورد همه این سوالات که بیشترش مفاهیمی از سوالات ساختمان داده ، طراحی الگوریتم ،ساختار داده ها و چالش هایی که در این زمینه و همچنین پایگاه داده بود دیدم ودر این دسته بندی وبلاگم شروع میکنم تمامی این سوالات را نوشته و به آن پاسخ خواهم داد .
حال بریم سراغ اولین مقاله که در مورد الگوریتم مرتب سازی انتخابی هستش
به زبان ساده این الگورتم مرتب سازی که اسمش روش هستش و هر دفعه یه انتخاب رو انجام میده
به این صورت که ابتدا اولین عدد رو انتخاب میکنه و تا آخر لیست میره میگرده ببینه کوچکتر از این لیست هست تا نه اگر بود که با همین عدد جابه جاش میکنه اگر نبود بی خیال میشه و میره سراغ بعدی تا آخر لیست این کار رو انجام میده و کارش به پایان میرسونه .
این الگوریتم دوتا آرایه داره
- آرایه ای که از قبل مرتب هستش
- و آرایه باقی مانده
در هر تکرار مرتب‌سازی انتخابی، حداقل مولفه در آرایه را از آرایه کوچکتر برداشته و به مرتب شده منتقل می دهد
در ادامه یکبار این الگوریتم رو مرحله به مرحله بررسی میکنیم
بیایید آرایه زیر را به عنوان مثال در نظر بگیریم: arr[] = {64, 25, 12, 22, 11}
اولین مرحله :
برای اولین موقعیت در آرایه مرتب شده، کل آرایه از شاخص 0 تا 4 به ترتیب پیمایش می شود. اولین موقعیتی که در حال حاضر 64 ذخیره شده، پس از عبور از کل آرایه مشخص می شود که 11 کمترین مقدار است
- بنابراین، 64 را با 11 جایگزین کنید. پس از یک بار تکرار ، 11 ، که کمترین مقدار در آرایه است، در موقعیت اول لیست مرتب شده ظاهر شود.
مرحله دوم :
برای موقعیت دوم، جایی که 25 وجود دارد، دوباره بقیه آرایه را به صورت متوالی پیمایش میکنیم
- پس از پیمایش، متوجه شدیم که 12 دومین مقدار کمتر در آرایه است و باید در مکان دوم آرایه ظاهر شود، بنابراین این مقادیر را عوض میکنیم.
مرحله سوم:
اکنون، برای مکان سوم، جایی که 25 وجود دارد، دوباره بقیه آرایه را پیمایش می نماییم و سومین کمترین مقدار موجود در آرایه را پیدا می نماییم
- در حین پیمایش، 22 به عنوان سومین کمترین مقدار ظاهر شد و باید در جایگاه سوم آرایه ظاهر شود، بنابراین 22 را با عنصر موجود در جایگاه سوم تعویض می نماییم.
مرحله چهارم :
همچنین، برای مرحله چهارم، بقیه آرایه را پیمایش نموده و چهارمین عنصر کوچک را در آرایه پیدا می نماییم.
- از آنجایی که 25 چهارمین مقدار پایین است، بنابراین در جایگاه چهارم قرار می گیرد.
مرحله پنجم :
در نهایت بزرگترین مقدار موجود در آرایه به طور خودکار در آخرین موقعیت آرایه قرار می گیرد
- آرایه به دست آمده آرایه مرتب شده است.
نکات :
پیچیدگی زمانی
یافتن کوچکترین عنصر برای انتقال به بخش مرتب شده، درجه زمانی O(n) خواهد داشت، چرا که با به اندازه طول آرایه مقایسه انجام داد. همچنین این کار را به اندازه طول آرایه باید تکرار کنیم تا تمام عناصر در جایگاه مرتب قرار بگیرند.
پس درجه زمانی الگوریتم مرتب سازی انتخابی O(n^2) است.
ویژگی‌های مرتب‌سازی انتخابی
۱-با توجه به قطعه کد نوشته شده، ترتیب عناصر تغییری در عملکرد آن اینجا نمی‌کند. یعنی این الگوریتم برای داده‌های کاملاً مرتب، نامرتب تصادفی و مرتب معکوس به یک ترتیب عمل کرده و تمام مقایسه‌های محاسبه شده در رابطه فوق را انجام می‌دهد؛ بنابراین پیچیدگی این الگوریتم در بهترین حالت و حالت متوسط نیز (Θ(n2 است.
۲- مرتب‌سازی انتخابی یک روش مرتب‌سازی درجا است. یعنی عملیات مرتب‌سازی در داخل خود لیست و بدون نیاز به حافظه کمکی بزرگ انجام می‌گیرد.
مقایسه‌ی الگوریتم‌های مرتب سازی
در جدول زیر چند نمونه از الگوریتم‌های مرتب‌سازی را با هم مقایسه میکنیم.
الگوریتم مرتب سازی انتخابی پایدار نیست ، از نظر حافظه O(1) و در بهترین زمان اجرا O(n^2) و بدترین زمان اجرا O(n^2) می باشد
کدهای این الگوریتم را میتوانید در ریپو زیر به زبان سی شارپ ببینید .
mahditahanian