خوارزميات JavaScript: فرز التحديد

افترض أن لدينا مجموعة من الأرقام ، ونريد تصنيفها حسب حجم العنصر.

يمكن أن يكون لديك مجموعة من الكائنات ، ويمكنك مقارنة خاصية كائن ، مثل الفرز حسب العمر ، أو أبجديًا حسب الاسم الأخير. التفاصيل لا تتغير.

نعمل بهذه الطريقة: نختار العنصر الأول. ثم نقارنها بالعنصر الثاني. إذا كان العنصر الثاني أصغر ، فسنبدله بالعنصر الأول. وهكذا ، نقارن هذا العنصر الأول بـكلعنصر في المصفوفة.

بمجرد أن نعرف أن لدينا أصغر عنصر ، ننتقل إلى العنصر الثاني ونقارنه بهكلعنصر في المصفوفة ، تجاهل الفهرس 0 ، لأننا نعلم بالفعل أن هذا هو الحد الأدنى. وهكذا ، حتى نهاية المصفوفة.

كما ترى ، فإن الخوارزمية باهظة الثمن. إنه لا يتكرر فقط في كل عنصر من عناصر المصفوفة: لكل عنصر ، فإنه يكرر المصفوفة مرة أخرى.

تعقيدهاO(n^2). لاحظ أن عدد العناصر التي نقارنها من الناحية الفنية يظل أصغر ، لكن هذا لا يعني أي شيء من حيث اصطلاحات Big O للتعقيد.

هنا تنفيذنا لـاختيار نوع.

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]


المزيد من دروس js: