Блог

Я создал базовую реализацию сортировки выбора, используя Math.min() javascript. Может ли кто-нибудь указать способы, с помощью которых можно сделать это более эффективным или элегантным? Что-то, чего я мог бы избежать, И т. Д.? Спасибо всем, код приведен ниже:

 let arr = [2, 0, 5, 1, 3, 2, 6, 4, 9, 0, 10, 2, 14, 8];

function selectionSort(array) {
  let workingArr = [...array]; //don't want to modify original array
  let sortedArr = []; //this will be returned as result

  for (let i = 0; i < array.length; i  ) {
    
    let sliced = workingArr.slice(0); 
    let min = Math.min(...sliced); //minimum of the slice
    sortedArr[i] = min; 
    let index = workingArr.indexOf(min);
    workingArr.splice(index, 1);
  }
  return sortedArr; 
}

let x = selectionSort(arr);
console.log(x);
document.body.innerHTML = x;

 

Я не уверен в определении сортировки выбора, используемого здесь, но здесь у вас есть две версии вашего кода, в которых: 1) вы удаляете ненужные копии массивов (неэффективное пространство) и 2) у вас есть более элегантное решение.

Ваше оригинальное решение оптимизировано

 function selectionSort(array) {
  const localArr = [...array];
  const res = [];
  for (let i = 0; i < localArr.length; i  ) { 
    const min = Math.min(...localArr);                                  
    localArr.splice(localArr.indexOf(min), 1);
    i--;
    res.push(min);
  }
  return res;
}
 

Используйте Array.prototype.reduce

 function selectionSort(array) {
  const localArr = [...array];
  return array.reduce((acc) => { 
    const min = Math.min(...localArr);                                 
    localArr.splice(localArr.indexOf(min), 1);
    return acc.concat(min);
  }, []);
}
 

Примечание: в вашей оригинальной версии функции вы, похоже, заботились о неизменности. Затем в теле функции, которую вы используете Array.prototype.splice , и Array.prototype.push которые оба противоречат принципу неизменности FP. Я не использую здесь чисто FP-подход просто для краткости, но вам следует изучить другие методы arrays, которые, так сказать, являются более «надежными».

Кажется, здесь никто ничего не нашел. Но я наконец нашел то, чего можно было избежать в исходном коде. Я понял, что нет необходимости создавать фрагменты массива с именем workingArr в приведенном выше коде (в вопросе). Вот модифицированный код, который проще.

 let arr = [2, 0, 5, 1, 3, 2, 6, 4, 9, 0, 10, 2, 14, 8];

function selectionSort(array) {
  let workingArr = [...array]; //don't want to modify original array
  let sortedArr = []; //this will be returned as result

  for (let i = 0; i < array.length; i  ) {
    //run upto full length of original array
    let min = Math.min(...workingArr); //minimum of the slice
    sortedArr[i] = min; //minimum found inserted into sortedArr
    let index = workingArr.indexOf(min); //find inserted ele's position in original input array's copy, so that we can use it to removed ele from that same array (otherwise in next pass that element will still come out as min)
    workingArr.splice(index, 1);
  }
  return sortedArr; //return resulting array
}

let x = selectionSort(arr);
console.log(x);

console.log(x.reverse()); //for descending sort