Сортировка массивов — JS: Массивы

Сортировка массивов — базовая алгоритмическая задача, которую нередко спрашивают на собеседованиях. Однако в реальном коде массивы сортируют, используя уже готовые функции стандартной библиотеки. В JavaScript сортировка выполняется с помощью метода sort() массивов:

const numbers = [8, 3, 10];
// sort изменяет массив!
numbers.sort((a, b) => a - b); // сортировка по возрастанию
console.log(numbers); // => [3, 8, 10]

// В обратную сторону можно через reverse() выполненный после sort()
// Тоже изменяет массив
numbers.reverse();
console.log(numbers); // => [10, 8, 3]

Тогда для чего задают подобные вопросы? Обычно собеседующий хочет узнать следующее:

1. Насколько кандидат вообще в курсе о существовании алгоритмов
2. Способен ли он программировать (составлять программу сам, думая своей головой)
3. Как работает его алгоритмическое мышление

Знание алгоритмов действительно влияет на то, как мы думаем и насколько быстро соображаем. И хотя невозможно знать все алгоритмы, нужно хотя бы иметь представление о самых ключевых и в идеале уметь их реализовывать. В нашем списке рекомендуемых книг есть как минимум одна книга, полностью посвященная алгоритмам.

Кроме того, Роберт Мартин в своей книге "Идеальный программист" рассказывает о подходе Ката — понятии, взятом из боевых искусств:

Принцип изучения боевого искусства на основе ката состоит в том, что повторяя ката многие тысячи раз, практик боевого искусства приучает свое тело к определенного рода движениям, выводя их на бессознательный уровень. Таким образом, попадая в боевую ситуацию, тело работает "само" на основе рефлексов, вложенных многократным повторением ката. Также считается, что ката обладают медитативным воздействием.

Роберт Мартин рекомендует время от времени решать классические алгоритмические задачки для поддержания формы. Эта тема стала настолько популярной, что если загуглить javascript github kata, то вы увидите множество репозиториев с подобными задачками.

Сортировка

Способов сортировать массив достаточно много. Самый популярный для обучения — пузырьковая сортировка (bubble sort).

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на свое место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырек в воде. Отсюда и название алгоритма).

// Функция изменяет входящий массив coll
const bubbleSort = (coll) => {
  let stepsCount = coll.length - 1;
  // Объявляем переменную swapped, значение которой показывает,
  // был ли совершен обмен элементов во время перебора массива
  let swapped;
  // do..while цикл. Работает почти идентично while
  // Разница в проверке. Тут она делается не до выполнения тела, а после.
  // Такой цикл полезен там, где надо выполнить тело хотя бы раз в любом случае.
  do {
    swapped = false;
    // Перебираем массив и меняем местами элементы, если предыдущий
    // больше, чем следующий
    for (let i = 0; i < stepsCount; i += 1) {
      if (coll[i] > coll[i + 1]) {
        // temp – временная константа для хранения текущего элемента
        const temp = coll[i];
        coll[i] = coll[i + 1];
        coll[i + 1] = temp;
        // Если сработал if и была совершена перестановка,
        // присваиваем swapped значение true
        swapped = true;
      }
    }
    // Уменьшаем счетчик на 1, т.к. самый большой элемент уже находится
    // в конце массива
    stepsCount -= 1;
  } while (swapped); // продолжаем, пока swapped === true

  return coll;
};

console.log(bubbleSort([3, 2, 10, -2, 0])); // => [ -2, 0, 2, 3, 10 ]

https://repl.it/@hexlet/js-arrays-sorting-bubble

Весь код этой функции делится на два уровня:

1. Внутренний цикл for, который проходит по массиву от начала до конца, меняя элементы попарно, если нужно сортировать
2. Внешний цикл do...while, который определяет, когда нужно остановиться. Обратите внимание, что в худшем случае этот цикл выполнится coll.length раз, что совпадает с теоретическим худшим случаем этого алгоритма, при котором самый большой или маленький элемент находятся в противоположных концах массива от сортированного варианта

Пузырьковая сортировка – самый простой и интуитивно понятный алгоритм сортировки. Очень полезно уметь реализовывать по памяти. Попробуйте сделать это на собственном компьютере, не подсматривая в теорию.

Дополнительные материалы

1. Сортировка средствами JavaScript
2. Цикл do...while
3. Визуализация алгоритмов сортировок

---

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

• Статья «Как учиться и справляться с негативными мыслями»
• Статья «Ловушки обучения»
• Статья «Сложные простые задачи по программированию»
• Урок «Как эффективно учиться на Хекслете»
• Вебинар «Как самостоятельно учиться»