بررسی الگوریتم مرتب سازی 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)در این بخش هم با استفاده از یک متغییر کمکی جای کوچکترین عدد رو با ایندکس فعلی عوض می کنیم

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

آقا داود