Selection Sort در جاوا اسکریپت

[مهدی حسن زاده]

فرض کنید آرایه ای از اعداد داریم و می خواهیم آن را بر اساس element size مرتب کنیم.

شما می توانید آرایه ای از objectsداشته باشید و می توانید یک ویژگی object را مانند مرتب سازی بر اساس سن یا حروف الفبا بر اساس نام خانوادگی مقایسه کنید. جزئیات تغییر نمی کند

ما به این ترتیب کار می کنیم: اولین مورد را انتخاب می کنیم. سپس آن را با مورد دوم مقایسه می کنیم. اگر مورد دوم کوچکتر است ، آن را با مورد اول عوض می کنیم. و غیره ، ما این مورد اول را با هر مورد در آرایه مقایسه می کنیم.

وقتی می دانیم که ما کوچکترین مورد را داریم ، به عنصر دوم می رویم و آن را با هر مورد در آرایه مقایسه می کنیم و index 0 را نادیده می گیریم ، زیرا قبلاً می دانیم که این حداقل است. و به همین ترتیب ، تا پایان آرایه.

همانطور که مشاهده می کنید ، الگوریتم بسیار expensive است. این نه تنها در هر مورد از آرایه تکرار می شود: برای هر مورد ، دوباره آرایه را تکرار می کند.

پیچیدگی آن O (n^2) است. توجه داشته باشید که از نظر فنی تعداد مواردی که ما مقایسه می کنیم کوچکتر می شود ، اما این از نظر قراردادهای Big O برای پیچیدگی معنی ندارد.

در اینجا پیاده سازی ما از نوع selection sort است.

 

JavaScript

const selectionSort = (originalList) => { //we first copy the array to avoid modifying the original array, since objects are passed by reference in JS const list = [...originalList] const len = list.length for (let i = 0; i < len; i++) { let min = i for (let j = i + 1; j < len; j++) { if (list[min] > list[j]) { min = j } } if (min !== i) { // a new minimum is found. Swap that with the current element ;[list[i], list[min]] = [list[min], list[i]] } } return list } const listOfNumbers = [1, 6, 3, 4, 5] console.log(selectionSort(listOfNumbers)) //[1,3,4,5,6]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

const selectionSort = (originalList) => {     //we first copy the array to avoid modifying the original array, since objects are passed by reference in JS     const list = [...originalList]     const len = list.length     for (let i = 0; i < len; i++) {       let min = i       for (let j = i + 1; j < len; j++) {         if (list[min] > list[j]) {           min = j         }       }       if (min !== i) {         // a new minimum is found. Swap that with the current element         ;[list[i], list[min]] = [list[min], list[i]]       }     }     return list   }      const listOfNumbers = [1, 6, 3, 4, 5]   console.log(selectionSort(listOfNumbers)) //[1,3,4,5,6]

[نویسنده]

نوشته‌ها