Задача пузырьковой сортировки в JavaScript - решение одного из вопросов для подготовки к собеседованию freeCodeCamp.
Перво-наперво, давайте посмотрим, что такое алгоритм.
Согласно Британнике, алгоритм - это конкретная процедура для решения четко определенной вычислительной задачи.
Алгоритмы и структуры данных позволяют нам изменить наше мышление и методы решения проблем. Это больше похоже на отжимание, чтобы наш мозг занялся и подумал так, чтобы мы могли решать проблемы.
Алгоритмы и структуры данных в основном включают работу с заданным набором данных и заставляют его делать что-то в соответствии с нашим определенным или заданным алгоритмом.
Для этой задачи мы собираемся решить задачу freeCodeCamp по подготовке к собеседованию.
Задача
Учитывая массив несортированных элементов, мы хотим иметь возможность возвращать отсортированный массив. Мы увидим несколько разных методов для этого и узнаем, какие компромиссы между этими подходами. Хотя в большинстве современных языков есть встроенные методы сортировки для подобных операций, все же важно понимать некоторые общие базовые подходы и узнавать, как их можно реализовать.
Здесь мы увидим пузырьковую сортировку. Метод пузырьковой сортировки начинается с начала несортированного массива и «пузырится» несортированные значения ближе к концу, выполняя итерацию по массиву до тех пор, пока он не будет полностью отсортирован. Он делает это, сравнивая соседние элементы и меняя их местами, если они вышли из строя. Метод продолжает цикл по массиву до тех пор, пока не перестанет происходить перестановка, и в этот момент массив не будет отсортирован.
Этот метод требует нескольких итераций по массиву и для среднего и худшего случаев имеет квадратичную временную сложность. Хотя это просто, в большинстве ситуаций это обычно непрактично.
Инструкции
Напишите функцию bubbleSort, которая принимает на вход массив целых чисел и возвращает массив этих чисел в отсортированном порядке от наименьшего к наибольшему.
bubbleSort должен быть функцией.
- bubbleSort должен возвращать отсортированный массив (от наименьшего к наибольшему).
- bubbleSort должен возвращать массив, который не изменился, за исключением порядка.
- bubbleSort не должен использовать встроенный метод .sort ().
Решение
function bubbleSort(array) {
// Only change code below this line
return array;
// Only change code above this line
}
bubbleSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]);
Нам дан массив, и решение хочет, чтобы мы переставили данный массив так, чтобы он начинался с наименьшего к наибольшему.
Так, например, мы можем перебирать массив и сравнивать числа, если данное число больше, оно перемещается к следующему, а его место заменяется меньшим числом.
Решение 1
function bubbleSort(array) {
for(let i=0;i<array.length -1 ;i++){
for(let j=0;j<array.length -1 - i; j++){
if(array[j]> array[j+1]){
const bSort=array[j];
array[j]=array[j+1];
array[j+1]=bSort;
}}}
return array;
}
console.log(bubbleSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]));
На нашей консоли мы отсортировали массив, как показано ниже.
[ 1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643 ]
На что обратить внимание
Наше решение - это чистая функция или нет? Чистая функция не должна изменять или изменять предоставленные параметры.
Наша функция, если мы выходим из системы параметров, которые являются массивом, мы обнаруживаем, что она изменяет массив и не заставляет его вести себя как чистая функция.
Чтобы решить эту проблему, мы можем сделать неглубокую копию параметров, которая представляет собой массив, как показано ниже.
function bubbleSort(array) {
const ShallowArray = array.slice();
for(let i=0;i<ShallowArray.length -1 ;i++){
for(let j=0;j<ShallowArray.length -1 - i; j++){
if(ShallowArray[j]> ShallowArray[j+1]){
const bSort=ShallowArray[j];
ShallowArray[j]=ShallowArray[j+1];
ShallowArray[j+1]=bSort;
}}}
return ShallowArray;
}
Метод slice () возвращает выбранные элементы в массиве как новый объект массива.
Теперь, если мы console.log предоставили параметр, мы заметим, что наш массив не изменился.
//our sorted array [ 1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643 ] //our parameter array [ 1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92 ]
Теперь наша функция ведет себя как чистая функция. Тем, кто любит функциональное программирование, это пригодится.
Это первая статья еженедельной серии об алгоритмах и проблемах структуры данных. Проверьте следующее испытание.
Если у вас есть лучшее решение этой проблемы, дайте мне знать в разделе комментариев.
Спасибо, что дочитали эту статью до сих пор. Если вы нашли это полезным, пожалуйста, поделитесь.
Дополнительная литература:
Больше контента на plainenglish.io
