Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Алгоритмы сортировки Основы алгоритмов и структур данных

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

Для всех примеров используется сортировка по возрастанию, структура данных - массив.

Сортировка выбором

Находится минимальный элемент и добавляется в новый массив.

const findMinIndex = (arr) => {
  let minIndex = 0;
  for (let i = 0; i < arr.length; i += 1) {
    const element = arr[i];
    const minElement = arr[minIndex];
    if (element < minElement) {
      minIndex = i;
    }
  }
  return minIndex;
};

const selectionSort = (arr) => {
  const result = []; // создаём новый массив
  while (arr.length !== 0) { // проходимся по массиву
    const minIndex = findMinIndex(arr); // находим индекс минимального элемента
    result.push(arr[minIndex]); // добавляем минимальный элемент в результирующий массив
    arr.splice(minIndex, 1) // удаляем минимальный элемент по индексу
    // если не удалить, то при каждой итерации минимальный элемент будет один и тот же
  }
  return result;
};

console.log(selectionSort([4, 5, 0, 1])); // [0, 1, 4, 5]

Сортировка слиянием

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

// слияние двух отсортированных массивов
const mergeArrays = (leftArr, rightArr) => {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    const leftElement = leftArr[leftIndex];
    const rightElement = rightArr[rightIndex];
    if (leftElement < rightElement) {
      result.push(leftElement);
      leftIndex += 1;
    } else {
      result.push(rightElement);
      rightIndex += 1;
    }
  }
  return result.concat(leftArr.slice(leftIndex)).concat(rightArr.slice(rightIndex));
};

const mergeSort = (arr) => {
  if (arr.length <= 1) { // Если длина меньше или равна 1, то массив отсортирован
    return arr;
  }

  // Разделяем на два массива
  const middleIndex = Math.floor(arr.length / 2);
  const left = arr.slice(0, middleIndex);
  const right = arr.slice(middleIndex, arr.length);

  // Рекурсивно сортируем два массива
  const leftSorted = mergeSort(left);
  const rightSorted = mergeSort(right);

  // Выполняем слияние двух отсортированных массивов
  return mergeArrays(leftSorted, rightSorted);
};

console.log(mergeSort([4, 5, 0, 1])); // [0, 1, 4, 5]

Сортировка слиянием имеет рекурсивную структуру и требует написания большего количества кода. Для рекурсивного алгоритма необходим базовый случай, это "если длина массива меньше или равна 1", то завершаем рекурсию. Массив из одного элемента априори отсортирован. Без базового случая рекурсия не завершится никогда. Для лучшего понимания алгоритма проиллюстрируем его:

[4, 5, 0, 1]; Разбиваем на два массива
[4, 5] [0, 1]; Каждый тоже разбиваем на две части
[4] [5] [0] [1]; По итогу имеем отсортированные массивы
Для каждой пары проводим слияние
[4, 5] [0, 1];
[0, 1, 4, 5];

Эффективность

Сравним сортировки на примере массива [3, 2, 1, 0]. Для сортировки выбором на первой итерации, чтобы найти 0, надо проделать 4 операции. Для нахождения 1 - 3 операции, 2 - 2 операции, 3 - 1 операции. В итоге получим 4 + 3 + 2 + 1 = 10 операций. Сортировка слиянием:

[3, 2] [1, 0]; 1 уровень стека вызовов функции
[3] [2] [1] [0]; 2 уровень
[2, 3] [0, 1]; Происходит слияние, 2 операции
[0, 1, 2, 3]; Обходим массив [0, 1] два раза, массив [2, 3] сразу сливаем. Ещё плюс 2 операции

2 уровня + 2 + 2 = 6 Операций

Получаем, что сортировка слиянием работает быстрее. Это не так заметно на массиве размером в 4 элемента. Для размера в 10 элементов сортировка слиянием займет около 30 операций. Сортировка выбором почти 100.

Мы не упомянули, что в сортировке слиянием создаются промежуточные массивы. И это занимает место в памяти компьютера.

По итогу:

  • Сортировка выбором - легче реализуется, расходует меньше памяти компьютера, работает медленнее.
  • Сортировка слиянием - труднее реализуется, расходует память компьютера, работает быстрее.

Сортировки можно совмещать в одну. Так сделано в движке V8 JavaScript. Если элементов меньше 10, то используется сортировка вставками, иначе быстрая сортировка.


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

  1. Array.prototype.splice

Аватары экспертов Хекслета

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

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

Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.

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

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
900
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 130 курсов, 2000+ часов теории
  • 900 практических заданий в браузере
  • 360 000 студентов
Даю согласие на обработку персональных данных, соглашаюсь с «Политикой конфиденциальности» и «Условиями оказания услуг»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Даю согласие на обработку персональных данных, соглашаюсь с «Политикой конфиденциальности» и «Условиями оказания услуг»