Почему длина массива должна храниться в алгоритме сортировки выбора? - PullRequest
Новая
       59

Почему длина массива должна храниться в алгоритме сортировки выбора?

1 голос
/ 22 января 2020

Код алгоритма из книги алгоритмов Гроккинга: 

const findSmallestIndex = (array) => {
  let smallestElement = array[0]; // Stores the smallest value
  let smallestIndex = 0; // Stores the index of the smallest value

  for (let i = 1; i < array.length; i++) {
    if (array[i] < smallestElement) {
      smallestElement = array[i];
      smallestIndex = i;
    }
  }

  return smallestIndex;
};

// 2. Sorts the array
const selectionSort = (array) => {
  const sortedArray = [];
  const length = array.length;

  for (let i = 0; i < length; i++) {
    // Finds the smallest element in the given array 
    const smallestIndex = findSmallestIndex(array);
    // Adds the smallest element to new array
    sortedArray.push(array.splice(smallestIndex, 1)[0]);
  }

  return sortedArray;
};

console.log(selectionSort([5, 3, 6, 2, 10])); // [2, 3, 5, 6, 10]

Проблема в функции selectionSort, хранящей длину массива в переменной wes, необходимой для правильной работы, и этот я не смог Не понимаю, я пытался не хранить длину в переменной: 

const selectionSort = (array) => {
  const sortedArray = [];


  for (let i = 0; i < array.length; i++) {
    // Finds the smallest element in the given array 
    const smallestIndex = findSmallestIndex(array);
    // Adds the smallest element to new array
    sortedArray.push(array.splice(smallestIndex, 1)[0]);
  }

  return sortedArray;
};

console.log(selectionSort([5, 3, 6, 2, 10])); // [2, 3, 5]

Я догадался, что проблема может быть в методе splice, потому что он уменьшает длину каждый раз в l oop, но я думаю, что индекс здесь не важен, поэтому проблема может быть не в этом!

Ответы [ 2 ]

2 голосов
/ 22 января 2020

Ваш код удаляет элемент из исходного массива, поэтому на каждой итерации i++ увеличивает i, а также splice уменьшает array.length. Это означает, что i и array.length сближаются на 2 каждый раз вместо 1, поэтому l oop повторяет только половину столько раз, сколько вы хотите. Это означает, что вы сортируете только половину элементов в sortedArray.

. Сначала копируя const length = array.length;, переменная length не изменяется внутри l oop, поэтому i++ делает i ближе к length на каждой итерации на 1, поэтому число итераций равно исходной длине массива, и каждый элемент сортируется.

В качестве примечания, ваш алгоритм сортируется в новый массив, но оставляет исходный массив пуст. Это, вероятно, никогда не то, что вы хотите; алгоритм сортировки должен либо сортировать массив на месте (оставляя исходный массив в отсортированном порядке), либо возвращать новый отсортированный массив (оставляя исходный массив без изменений). Вы можете исправить это, сделав копию array в начале вашей функции, чтобы алгоритм уничтожил копию вместо оригинала.

1 голос
/ 22 января 2020

Я помещаю это здесь по той единственной причине, что опубликованная реализация, очевидно из текста алгоритмов, слишком излишне усложнена и неэффективна. 

function selectionSort(array) {
  function smallestIndex(start) {
    let si = start;
    for (let i = start + 1; i < array.length; ++i) {
      if (array[i] < array[si])
        si = i;
    }
    return si;
  }

  for (let i = 0; i < array.length; i++) {
    let index = smallestIndex(i), t;
    // swap value into current slot
    t = array[index];
    array[index] = array[i];
    array[i] = t;
  }
  return array;
}

Здесь функция smallestIndex() улучшена занять исходную позицию в качестве параметра. Таким образом, он находит индекс наименьшего значения в остатке массива. На первой итерации это будет наименьшее значение во всем массиве. Это значение заменяется на то, что находится в текущей начальной точке, поэтому после этого первого раза через главную позицию l oop в массиве будет наименьшее значение во всем массиве.

На следующей итерации, поиск индекса начинается с 1, так что процесс найдет второе наименьшее значение из исходного массива и поменяет его на позицию 1.

Процесс продолжается через массив. Обратите внимание, что новые массивы не создаются, и нет вызовов методов Array с линейным временем.

...