ویرگول
ورودثبت نام
Davood Habbabi
Davood Habbabiاگر وقت کنم چیزایی که یاد گرفتم رو می نویسم
Davood Habbabi
Davood Habbabi
خواندن ۲ دقیقه·۵ سال پیش

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

این نوع الگوریتم هم خیلی سادس و فهمیدنش اصلا کار سختی نیست

به تصویر بالا دقت کنید

طبق این الگوریتم توی قدم اول میاد و اولین ایندکس از ارایه رو در نظر می گیره و توی بقیه ارایه می گرده دنبال کوچک ترین عدد که کوچک تر از ایندکس اول باشه رو پیدا می کنه

وقتی که عددی پیدا کرد که کوچیک تر باشه میاد جای ایندکس اول و عدد کوچک تر رو عوض می کنه توی پالس بعدی ایندکس دوم رو در نظر می گیره و باز بررسی می کنه کوچک ترین عدد که کوچک تر از ایندکس دوم باشه رو پیدا می کنه و جاشونو عوض می کنه

این روند به تعداد مقادیر موجود در ارایه ( arr.length) تکرار می شه تا ارایه مرتب بشه

اگر دقت کنید خود به خود ارایه ما تبدیل به دو بخش مرتب شده و مرتب نشده از ایندکس صفر تا ایندکس اخر تقسیم می شه

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


بریم کدش رو بررسی کنیم


function selectionSort(arr) { for (let i = 0; i < arr.length; i++) { let minIndex = i; //(1) for (let j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (i !== minIndex) { //(2) const lesser = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = lesser; } } return arr; }

خب خود کد تقریبا همه چیز رو گفته و زیاد به توضیح نداره


  • (1) در این بخش از طریق یه حلقه و یک متغییر کوچک ترین ایندکس بعد از ایندکس n رو پیدا می کنیم
  • (2)در این بخش هم با استفاده از یک متغییر کمکی جای کوچکترین عدد رو با ایندکس فعلی عوض می کنیم



امیدوارم مفید باشه :)

آقا داود

۴
۰
Davood Habbabi
Davood Habbabi
اگر وقت کنم چیزایی که یاد گرفتم رو می نویسم
تیم فرانت اند تومن
تیم فرانت اند تومن
محیطی برای اشتراک گذاری تجربیات و معلومات تیم فنی (فرانت اند) تومن
شاید از این پست‌ها خوشتان بیاید