Задача Selection Sort в JavaScript - решение одной из задач программирования freeCodeCamps.
Мы учимся решать задачи для алгоритмов и структур данных с различных платформ, просто чтобы улучшить наши методы решения проблем.
Если вы пропустили, ознакомьтесь с последним испытанием, указанным ниже:
Задача:
Здесь мы реализуем сортировку выбора. Сортировка по выбору работает путем выбора минимального значения в списке и замены его первым значением в списке. Затем он начинается со второй позиции, выбирает наименьшее значение в оставшемся списке и меняет его местами на второй элемент. Он продолжает перебирать список и менять местами элементы, пока не достигнет конца списка. Теперь список отсортирован. Сортировка выбора во всех случаях имеет квадратичную временную сложность.
Инструкция:
Напишите функцию selectionSort, которая принимает на вход массив целых чисел и возвращает массив этих целых чисел в отсортированном порядке от наименьшего к наибольшему.
Примечания:
Мы вызываем эту функцию из-за кулис; Используемый нами тестовый массив закомментирован в редакторе. Попробуйте записать массив, чтобы увидеть свой алгоритм сортировки в действии!
- selectionSort должен быть функцией
- selectionSort должен возвращать отсортированный массив (от наименьшего к наибольшему)
- selectionSort должен возвращать массив, который не изменился, за исключением порядка.
- selectionSort не должен использовать встроенный метод .sort ()
function selectionSort(array) {
// change code below this line
return array;
// change code above this line
}
toSort = [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92];
Наше решение
function selectionSort(array) {
// change code below this line
for (let index = 0; index < array.length — 1; index++) {
let leastElement = index;
for (let j = index + 1; j < array.length; j++) {
if (array[j] < array[leastElement]) {
leastElement = j;
}
}
// const temp = array[index];
// array[index] = array[leastElement];
// array[leastElement] = temp;
// we can refactor the above code as shown below
[array[index], array[leastElement]] = [array[leastElement], array[index]];
}
return array;
// change code above this line
}
toSort = [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92];
console.log(selectionSort(toSort));
Объяснение
Мы выполним первую итерацию, чтобы найти серию наименьших элементов в предоставленном массиве. Затем мы найдем следующее наименьшее число в массиве, которое будет длиной массива минус 1.
Как только мы поменяем местами первый элемент с самым маленьким в массиве, все будет в порядке, и нам не нужно будет возвращаться снова. Затем мы выполним еще один цикл. Для этого внутреннего цикла помните, что в нашем начальном цикле for мы нашли наименьший элемент в массиве, чтобы найти следующее наименьшее число, нам нужно будет перейти к следующему числу, которое в нашем случае будет index + 1.
Просто после первой итерации некоторые из наших чисел уже будут зафиксированы на своих местах. Кроме того, мы объявили наименьший элемент индекса, чтобы он напоминал позицию наименее замененного числа в данном массиве. Затем мы можем использовать оператор условного if для проверки соответствующих условий.
Мы проверим, меньше ли массив с индексом j, чем массив с наименьшим индексом, тогда мы собираемся установить для наименьшего элемента в индексе значение j. это будет продолжаться до тех пор, пока массив не будет зациклен.
Теперь нам нужно будет поменять местами элементы в массиве. Мы собираемся изменить текущую итерацию с помощью наименьшего количества элементов. Здесь мы можем ввести временную переменную и установить ее в массив по индексу, а затем мы продолжим и поменять местами массив с наименьшим элементом, а также массив по крайней мере с элементом на временную переменную.
Как мы видели из нашего решения выше, это не чистая функция. Почему нет. Попробуйте выйти из исходного массива, мы увидим, что он изменяет исходный массив, и это не подходит для чистого функционального программирования.
Дополнительный рефакторинг:
Мы можем сделать неглубокую копию массива и использовать неглубокий скопированный массив вместо предоставленного массива. Мы можем реализовать это с помощью метода .slice (). Этот метод массива позволяет нам сделать неглубокую копию исходного массива.
Если вы хотите узнать больше о методах массивов, ознакомьтесь со статьей, приведенной ниже.
function selectionSort(array) {
// change code below this line
const shallowCopy = array.slice();
for (let index = 0; index < shallowCopy.length — 1; index++) {
let leastElement = index;
for (let j = index + 1; j < shallowCopy.length; j++) {
if (shallowCopy[j] < shallowCopy[leastElement]) {
leastElement = j;
}
}
// const temp = array[index];
// array[index] = array[leastElement];
// array[leastElement] = temp;
// we can refactor the above code as shown below
[shallowCopy[index], shallowCopy[leastElement]] = [shallowCopy[leastElement], shallowCopy[index]];
}
return shallowCopy;
// change code above this line
}
toSort = [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92];
console.log(selectionSort(toSort));
console.log(toSort);
Наша функция теперь ведет себя как чистая функция. Для подтверждения ознакомьтесь с приведенным ниже фрагментом.
[1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 564]
[1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]
Заключительные мысли
Спасибо, что дочитали эту статью до сих пор, я надеюсь, что вы нашли эту статью полезной в решении этой проблемы.
У вас есть лучшее решение или есть какие-либо вопросы, я хотел бы услышать от вас в разделе комментариев?
Другие материалы:
Больше контента на plainenglish.io
