Как работает быстрая сортировка

Как работает быстрая сортировка

Ей уже 60 лет, но она до сих пор работает быстро

Это статья о реализации одного из алгоритмов сортировки. Эти алгоритмы считаются классикой информатики: разработчиков могут спросить об этих алгоритмах на собеседовании, а сами алгоритмы помогают ощутить силу автоматики и алгоритмов. Сегодня пощупаем один из таких алгоритмов.

Ранее в статьях мы рассказали про два вида сортировки:

Эти сортировки относятся к простым видам алгоритмов — надёжным, но неоптимальным по скорости и затратам памяти. Гораздо чаще вместо них используют быструю сортировку или алгоритмы на её основе — про это и будем сегодня говорить.

В чём идея быстрой сортировки

Когда в 1960 году Тони Хоар придумывал этот алгоритм, ему нужно было отсортировать данные на магнитной ленте за один проход, чтобы не перематывать плёнку много раз. Для этого он взял за основу классическую пузырьковую сортировку и преобразовал её так:

  1. На очередном шаге выбирается опорный элемент — им может быть любой элемент массива.
  2. Все остальные элементы массива сравниваются с опорным и те, которые меньше него, ставятся слева от него, а которые больше или равны — справа.
  3. Для двух получившихся блоков массива (меньше опорного, и больше либо равны опорному) производится точно такая же операция — выделяется опорный элемент и всё идёт точно так же, пока в блоке не останется один элемент.

Вот как это выглядит, если представить массив в виде графика:

Синяя линия — это значение опорного элемента, а серый блок показывает, какую часть массива сортирует алгоритм
Синяя линия — это значение опорного элемента, а серый блок показывает, какую часть массива сортирует алгоритм

Особенности алгоритма

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

Но несмотря на такой возможный расход памяти, у быстрой сортировки есть много плюсов:

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

Выбор опорного элемента

Правильный выбор опорного элемента может сильно повысить эффективность быстрой сортировки. В зависимости от реализации алгоритма есть разные способы выбора:

  • Первый элемент — в первых версиях быстрой сортировки Хоар выбирал опорным первый элемент массива. Именно так он смог обрабатывать всю магнитную ленту за один проход.
  • Средний элемент — тот, который физически стоит посередине массива.
  • Медианный элемент — элемент, значение которого находится посередине между всеми значениями в массиве

Есть ещё много других техник выбора — они применяются, когда программист точно знает, с какими массивами придётся работать: немного упорядоченными или когда всё вразнобой.

Быстрая сортировка на JavaScript

Запустите этот код в консоли браузера, чтобы посмотреть, как алгоритм шаг за шагом приводит массив в нормальный вид:

// исходный массив 
var arr = [3,14,1,7,9,8,11,6,4,2]

// рекурсивная функция быстрой сортировки
// на вход получает массив, который нужно отсортировать
function quickSort(arr) {
  // если длина массива меньше двух (в нём один элемент или нет их вообще)
  // то возвращаем массив как есть, без обработки
  if (arr.length < 2) return arr;
  // берём первый элемент массива как опорный
  let pivot = arr[0];
  // будущие левые и правые части массива
  const left = [];
  const right = [];
  // перебираем весь массив по порядку
  for (let i = 1; i < arr.length; i++) {
    // если опорный элемент больше текущего
    if (pivot > arr[i]) {
      // то добавляем текущий элемент в левую часть
      left.push(arr[i]);
    // в противном случае
    } else {
      // добавляем текущий элемент в правую часть
      right.push(arr[i]);
    }

    // выводим текущее состояние массива в консоль 
    // это необязательный шаг, он здесь для наглядности 
    console.log(arr);
  }
  // отправляем на рекурсивную обработку левую и правую части массива
  // и возвращаем результат в виде двух склеенных массивов
  return quickSort(left).concat(pivot, quickSort(right));
}

// запускаем сортировку
quickSort(arr);

Что дальше

На этом мы закончим с обменными сортировками — впереди нас ждут интересные сортировки выбором, слиянием и даже сортировки без сравнений. Подпишитесь, чтобы не пропустить ни одной из них.

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Алина Грызлова

Веб-разработка — это новый чёрный
На базе веб-технологий делают всё — от сложного софта до высокобюджетных игр. Изучите технологии и начните карьеру в ИТ. Старт бесплатно. Попробуйте, вдруг вам понравится.
Изучить
Веб-разработка — это новый чёрный
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Моделируем игру в рулетку на Python
Моделируем игру в рулетку на Python

И строим наглядные графики.

easy
Олды здесь: как сверстать веб-страницу на таблицах
Олды здесь: как сверстать веб-страницу на таблицах

Для этого нужна простая советская...

easy
ReferenceError: math is not defined — что это означает

Противная и неочевидная ошибка, которую очень легко исправить.

medium
Телеграм-бот для учёбы

Собираем за 10 минут.

medium
Генератор лабиринтов
Генератор лабиринтов

Рисуем лабиринты любого размера.

hard
Генератор паролей
Превращаем генератор паролей в настоящую программу

Настало время настоящего программирования — собираем приложение из исходников.

hard
Конец ретроградному Меркурию! Пишем собственный гороскоп на Python

Наш гороскоп точен и прост! Сбросим иго астрологов!

medium
Как поменять размер чего угодно на странице
Как поменять размер чего угодно на странице

Проект с использованием слайдера в JQuery UI

medium
Собираем змейку на Arduino

Это будет самая необычная змейка, в которую вы играли.

hard
Делаем собственный таймер для спорта
Делаем собственный таймер для спорта

Без рекламы и встроенных покупок.

hard
medium