Skip to main content

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

Описание

Быстрая сортировка (сортировка Хоара) (quick sort) - это алгоритм сортировки, который является существенным улучшением алгоритма сортировки с помощью прямого обмена (например, сортировки пузырьком). Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы.

Общая идея алгоритма состоит в следующем:

  1. Выбираем из массива так называемый опорный (pivot) элемент. Это может быть любой элемент массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность.
  2. Сравниваем все остальные элементы с опорным и переставляем их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: "элементы меньшие опорного", "равные" и "большие".
  3. Для отрезков меньшего и большего подмассивов выполняем рекурсивно ту же последовательность операций, если длина подмассива больше 1.

Сложность

ЛучшееСреднееХудшееПамятьСтабильность
n log(n)n log(n)n^2log(n)Нет

Реализация

// algorithms/sorting/quick-sort.js
import Sort from './sort'

export default class QuickSort extends Sort {
  sort(arr) {
    // Копируем оригинальный массив во избежание его модификации
    // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/structuredClone
    const _arr = structuredClone(arr)

    // Если массив пустой или содержит только один элемент,
    // возвращаем его, поскольку он уже отсортирован
    if (_arr.length <= 1) {
      return _arr
    }

    const leftArr = []
    const rightArr = []

    // Берем первый элемент массива в качестве опорного
    const pivot = _arr.shift()
    const centerArr = [pivot]

    // Распределяем все элементы массива между левым, центральным и правым подмассивами
    while (_arr.length) {
      const currentItem = _arr.shift()

      this.callbacks.visitingCallback(currentItem)

      if (this.comparator.equal(currentItem, pivot)) {
        centerArr.push(currentItem)
      } else if (this.comparator.lessThan(currentItem, pivot)) {
        leftArr.push(currentItem)
      } else {
        rightArr.push(currentItem)
      }
    }

    // Сортируем левый и правый подмассивы
    const leftArraySorted = this.sort(leftArr)
    const rightArraySorted = this.sort(rightArr)

    // Объединяем массивы слева направо
    return leftArraySorted.concat(centerArr, rightArraySorted)
  }
}

Тестирование

// algorithms/sorting/__tests__/quick-sort.test.js
import QuickSort from '../quick-sort'
import {
  equalArr,
  notSortedArr,
  reverseArr,
  sortedArr,
  SortTester,
} from '../sort-tester'

// Константы временной сложности
const SORTED_ARRAY_VISITING_COUNT = 190
const NOT_SORTED_ARRAY_VISITING_COUNT = 62
const REVERSE_SORTED_ARRAY_VISITING_COUNT = 190
const EQUAL_ARRAY_VISITING_COUNT = 19

describe('QuickSort', () => {
  it('должен отсортировать массив', () => {
    SortTester.testSort(QuickSort)
  })

  it('должен отсортировать массив с помощью кастомной функции сравнения', () => {
    SortTester.testSortWithCustomComparator(QuickSort)
  })

  it('должен выполнить стабильную сортировку', () => {
    SortTester.testSortStability(QuickSort)
  })

  it('должен отсортировать отрицательные числа', () => {
    SortTester.testNegativeNumbersSort(QuickSort)
  })

  it('должен посетить массив одинаковых элементов указанное количество раз', () => {
    SortTester.testAlgorithmTimeComplexity(
      QuickSort,
      equalArr,
      EQUAL_ARRAY_VISITING_COUNT,
    )
  })

  it('должен посетить отсортированный массив указанное количество раз', () => {
    SortTester.testAlgorithmTimeComplexity(
      QuickSort,
      sortedArr,
      SORTED_ARRAY_VISITING_COUNT,
    )
  })

  it('должен посетить неотсортированный массив указанное количество раз', () => {
    SortTester.testAlgorithmTimeComplexity(
      QuickSort,
      notSortedArr,
      NOT_SORTED_ARRAY_VISITING_COUNT,
    )
  })

  it('должен посетить инвертированный отсортированный массив указанное количество раз', () => {
    SortTester.testAlgorithmTimeComplexity(
      QuickSort,
      reverseArr,
      REVERSE_SORTED_ARRAY_VISITING_COUNT,
    )
  })
})

Запускаем тесты:

npm run test ./algorithms/sorting/__tests__/quick-sort