Привет, друзья!

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

Сегодня мы поговорим об алгоритмах сортировки.

Код, представленный в этой и других статьях серии, можно найти в этом репозитории.

Интересно? Тогда прошу под кат.

• Первая часть
• Вторая часть
• Третья часть
• Четвертая часть
• Пятая часть
• Шестая часть
• Седьмая часть

❯ Сортировка

• Как работают сортировки

❯ Сортировка пузырьком

Описание

• Википедия
• YouTube
• Визуализация

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

Сложность

Реализация

Начнем с реализации суперкласса сортировки:

// algorithms/sorting/sort.js
import Comparator from '../../utils/comparator'

export default class Sort {
  constructor(originalCallbacks) {
    // Коллбэки сортировки
    this.callbacks = Sort.initSortingCallbacks(originalCallbacks)
    // Функция сравнения элементов
    this.comparator = new Comparator(this.callbacks.compareCallback)
  }

  // Коллбэки сортировки
  static initSortingCallbacks(originalCallbacks) {
    const callbacks = originalCallbacks || {}
    const stubCallback = () => {}

    // Вызывается при сравнении элементов
    callbacks.compareCallback = callbacks.compareCallback || undefined
    // Вызывается при посещении элемента
    callbacks.visitingCallback = callbacks.visitingCallback || stubCallback

    return callbacks
  }

  // Метод сортировки реализуется подклассом
  sort() {
    throw new Error('Метод сортировки не реализован')
  }
}

Напомню, как выглядит класс Comparator:

// utils/comparator.js
export default class Comparator {
  constructor(fn) {
    this.compare = fn || Comparator.defaultCompare
  }

  // Дефолтная функция сравнения узлов
  static defaultCompare(a, b) {
    if (a === b) {
      return 0
    }
    return a < b ? -1 : 1
  }

  // Проверка на равенство
  equal(a, b) {
    return this.compare(a, b) === 0
  }

  // Меньше чем
  lessThan(a, b) {
    return this.compare(a, b) < 0
  }

  // Больше чем
  greaterThan(a, b) {
    return this.compare(a, b) > 0
  }

  // Меньше или равно
  lessThanOrEqual(a, b) {
    return this.lessThan(a, b) || this.equal(a, b)
  }

  // Больше или равно
  greaterThanOrEqual(a, b) {
    return this.greaterThan(a, b) || this.equal(a, b)
  }

  // Инверсия сравнения
  reverse() {
    const original = this.compare
    this.compare = (a, b) => original(b, a)
  }
}

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

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

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

    // Перебираем все элементы массива, начиная со второго
    for (let i = 1; i < _arr.length; i++) {
      swapped = false

      this.callbacks.visitingCallback(_arr[i])

      // Обратите внимание, что здесь мы двигаемся до `i`
      for (let j = 0; j < _arr.length - i; j++) {
        this.callbacks.visitingCallback(_arr[j])

        // Меняем элементы местами, если они расположены в неправильном порядке
        if (this.comparator.lessThan(_arr[j + 1], _arr[j])) {
          ;[_arr[j], _arr[j + 1]] = [_arr[j + 1], _arr[j]]

          // Обновляем индикатор
          swapped = true
        }
      }

      // Это означает, что массив отсортирован
      if (!swapped) {
        return _arr
      }
    }

    return _arr
  }
}

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

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

// algorithms/sorting/sort-tester.js
export const sortedArr = [
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
]
export const reverseArr = [
  20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
]
export const notSortedArr = [
  15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19,
]
export const equalArr = [
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
]
export const negativeArr = [-1, 0, 5, -10, 20, 13, -7, 3, 2, -3]
export const negativeArrSorted = [-10, -7, -3, -1, 0, 2, 3, 5, 13, 20]

export class SortTester {
  // Проверяет корректность сортировки
  // с помощью переданного метода (класса) сортировки
  static testSort(SortingClass) {
    const sorter = new SortingClass()

    expect(sorter.sort([])).toEqual([])
    expect(sorter.sort([1])).toEqual([1])
    expect(sorter.sort([1, 2])).toEqual([1, 2])
    expect(sorter.sort([2, 1])).toEqual([1, 2])
    expect(sorter.sort([3, 4, 2, 1, 0, 0, 4, 3, 4, 2])).toEqual([
      0, 0, 1, 2, 2, 3, 3, 4, 4, 4,
    ])
    expect(sorter.sort(sortedArr)).toEqual(sortedArr)
    expect(sorter.sort(reverseArr)).toEqual(sortedArr)
    expect(sorter.sort(notSortedArr)).toEqual(sortedArr)
    expect(sorter.sort(equalArr)).toEqual(equalArr)
  }

  // Проверяет корректность сортировки отрицательных чисел
  static testNegativeNumbersSort(SortingClass) {
    const sorter = new SortingClass()
    expect(sorter.sort(negativeArr)).toEqual(negativeArrSorted)
  }

  // Проверяет корректность сортировки
  // с помощью кастомной функции сравнения элементов
  static testSortWithCustomComparator(SortingClass) {
    const callbacks = {
      compareCallback: (a, b) => {
        if (a.length === b.length) {
          return 0
        }
        return a.length < b.length ? -1 : 1
      },
    }

    const sorter = new SortingClass(callbacks)

    expect(sorter.sort([''])).toEqual([''])
    expect(sorter.sort(['a'])).toEqual(['a'])
    expect(sorter.sort(['aa', 'a'])).toEqual(['a', 'aa'])
    expect(sorter.sort(['aa', 'q', 'bbbb', 'ccc'])).toEqual([
      'q',
      'aa',
      'ccc',
      'bbbb',
    ])
    expect(sorter.sort(['aa', 'aa'])).toEqual(['aa', 'aa'])
  }

  // Проверяет стабильность сортировки
  static testSortStability(SortingClass) {
    const callbacks = {
      compareCallback: (a, b) => {
        if (a.length === b.length) {
          return 0
        }
        return a.length < b.length ? -1 : 1
      },
    }

    const sorter = new SortingClass(callbacks)

    expect(sorter.sort(['bb', 'aa', 'c'])).toEqual(['c', 'bb', 'aa'])
    expect(sorter.sort(['aa', 'q', 'a', 'bbbb', 'ccc'])).toEqual([
      'q',
      'a',
      'aa',
      'ccc',
      'bbbb',
    ])
  }

  // Проверяет временную сложность сортировки
  static testAlgorithmTimeComplexity(
    SortingClass,
    arrayToBeSorted,
    numberOfVisits,
  ) {
    const visitingCallback = jest.fn()
    const callbacks = { visitingCallback }
    const sorter = new SortingClass(callbacks)

    sorter.sort(arrayToBeSorted)

    expect(visitingCallback).toHaveBeenCalledTimes(numberOfVisits)
  }
}

Тестируем пузырьковую сортировку:

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

// Константы временной сложности
const SORTED_ARRAY_VISITING_COUNT = 20
const NOT_SORTED_ARRAY_VISITING_COUNT = 189
const REVERSE_SORTED_ARRAY_VISITING_COUNT = 209
const EQUAL_ARRAY_VISITING_COUNT = 20

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

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

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

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

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

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

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

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

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

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

Результат:

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

Описание

• Википедия
• YouTube
• Визуализация

Сортировка выбором (selection sort) — это простой алгоритм сортировки, который состоит из следующих шагов:

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

Сложность

Реализация

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

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

    // Перебираем все элементы массива
    for (let i = 0; i < _arr.length - 1; i++) {
      // Индекс минимального элемента
      let minIndex = i

      this.callbacks.visitingCallback(_arr[i])

      // Обратите внимание, что здесь мы двигаемся от `i + 1`
      for (let j = i + 1; j < _arr.length; j++) {
        this.callbacks.visitingCallback(_arr[j])

        if (this.comparator.lessThan(_arr[j], _arr[minIndex])) {
          minIndex = j
        }
      }

      // Если обнаружен новый минимальный элемент,
      // меняем на него текущий элемент
      if (minIndex !== i) {
        ;[_arr[i], _arr[minIndex]] = [_arr[minIndex], _arr[i]]
      }
    }

    return _arr
  }
}

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

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

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

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

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

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

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

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

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

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

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

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

Результат:

❯ Сортировка вставками

Описание

• Википедия
• YouTube
• Визуализация

Сортировка вставками (insertion sort) — это простой алгоритм сортировки, в котором элементы списка просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.

Сложность

Реализация

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

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

    // Перебираем все элементы массива, начиная со второго
    for (let i = 1; i < _arr.length; i++) {
      this.callbacks.visitingCallback(_arr[i])

      let currentIndex = i

      // Цикл выполняется до тех пор,
      // пока у нас имеется предыдущий элемент и
      // текущий элемент меньше предыдущего
      // (левый элемент больше правого)
      while (
        _arr[currentIndex - 1] !== undefined &&
        this.comparator.lessThan(_arr[currentIndex], _arr[currentIndex - 1])
      ) {
        this.callbacks.visitingCallback(_arr[currentIndex - 1])
        // Меняем элементы местами
        ;[_arr[currentIndex - 1], _arr[currentIndex]] = [
          _arr[currentIndex],
          _arr[currentIndex - 1],
        ]

        // Двигаемся влево
        currentIndex--
      }
    }

    return _arr
  }
}

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

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

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

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

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

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

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

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

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

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

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

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

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

Результат:

❯ Сортировка кучей

Описание

• Википедия
• YouTube
• Визуализация

Сортировка кучей (пирамидальная сортировка) (heap sort) — это алгоритм сортировки, который является своего рода улучшением сортировки выбором. Сначала список делится на отсортированную и неотсортированную части. Затем неотсортированная часть уменьшается за счет извлечения наибольшего элемента и его перемещения в отсортированную часть. Улучшением является то, что для нахождения наибольшего элемента используется не линейный поиск, а структура данных "Куча" (см. часть 2, раздел 6).

Сложность

Реализация

// algorithms/sorting/heap-sort.js
import Sort from './sort'
import MinHeap from '../../data-structures/heap/min-heap'

export default class HeapSort extends Sort {
  sort(arr) {
    const _arr = []
    // Создаем минимальную кучу
    const minHeap = new MinHeap(this.callbacks.compareCallback)

    // Добавляем элементы массива в кучу
    for (const item of arr) {
      this.callbacks.visitingCallback(item)

      minHeap.add(item)
    }

    // Теперь у нас есть куча, в которой минимальный элемент всегда находится на самом верху.
    // Извлекаем минимальные элементы по одному для формирования отсортированного массива
    while (!minHeap.isEmpty()) {
      const item = minHeap.poll()

      this.callbacks.visitingCallback(item)

      _arr.push(item)
    }

    return _arr
  }
}

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

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

// Константы временной сложности.
// Обратите внимание, что мы не учитываем время реструктуризации кучи,
// поэтому в реальности числа будут бОльшими
const SORTED_ARRAY_VISITING_COUNT = 40
const NOT_SORTED_ARRAY_VISITING_COUNT = 40
const REVERSE_SORTED_ARRAY_VISITING_COUNT = 40
const EQUAL_ARRAY_VISITING_COUNT = 40

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

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

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

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

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

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

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

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

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

Результат:

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

Описание

• Википедия
• YouTube
• Визуализация

Сортировка слиянием (merge sort) — это алгоритм сортировки, который является хорошим примером использования принципа "разделяй и властвуй". Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, полученные решения комбинируются в финальный результат.

Сортировка слиянием выполняется в три этапа:

1. Сортируемый массив разбивается на две примерно одинаковые части.
2. Каждая часть сортируется отдельно, например, тем же самым алгоритмом.
3. Два упорядоченных массива соединяются в один.

Есть несколько нюансов:

1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив единичной длины можно считать отсортированным).
2. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два отсортированных по возрастанию подмассива. Тогда:
   
   • слияние двух подмассивов в результирующий массив. На каждом шаге мы берем меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива, из которого был взят элемент, увеличиваются на 1
   • добавление остатка. Когда один из подмассивов закончился, все оставшиеся элементы другого подмассива добавляются в результирующий массив

Сложность

Реализация

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

export default class MergeSort extends Sort {
  // Сортирует массив методом слияния
  sort(arr) {
    this.callbacks.visitingCallback(null)

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

    // Делим массив пополам
    const middleIndex = Math.floor(arr.length / 2)
    const leftArray = arr.slice(0, middleIndex)
    const rightArray = arr.slice(middleIndex, arr.length)

    // Сортируем половины
    const leftSortedArray = this.sort(leftArray)
    const rightSortedArray = this.sort(rightArray)

    // Объединяем отсортированные половины в один массив
    return this.mergeSortedArrays(leftSortedArray, rightSortedArray)
  }

  // Объединяет два отсортированных массива
  mergeSortedArrays(leftArray, rightArray) {
    const _arr = []

    // Используем указатели для исключения элементов, добавленных в массив
    let leftIndex = 0
    let rightIndex = 0

    while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
      let minItem = null

      // Находим минимальный элемент подмассивов
      if (
        this.comparator.lessThanOrEqual(
          leftArray[leftIndex],
          rightArray[rightIndex],
        )
      ) {
        minItem = leftArray[leftIndex]
        // Двигаемся вправо
        leftIndex += 1
      } else {
        minItem = rightArray[rightIndex]
        // Двигаемся влево
        rightIndex += 1
      }

      // Добавляем минимальный элемент в отсортированный массив
      _arr.push(minItem)

      this.callbacks.visitingCallback(minItem)
    }

    // Добавляем оставшиеся элементы в результирующий массив
    return _arr
      .concat(leftArray.slice(leftIndex))
      .concat(rightArray.slice(rightIndex))
  }
}

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

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

// Константы временной сложности
const SORTED_ARRAY_VISITING_COUNT = 79
const NOT_SORTED_ARRAY_VISITING_COUNT = 102
const REVERSE_SORTED_ARRAY_VISITING_COUNT = 87
const EQUAL_ARRAY_VISITING_COUNT = 79

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

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

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

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

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

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

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

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

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

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

Результат:

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

Описание

• Википедия
• YouTube
• Грокаем алгоритмы
• Визуализация

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

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

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

Сложность

Реализация

// 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

Результат:

❯ Сортировка Шелла

Описание

• Википедия
• YouTube
• Визуализация
• Для смеха

Сортировка Шелла (Shell sort) — это алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определенном расстоянии друг от друга.

При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть обычной сортировкой вставками).

Хотя сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

• отсутствие потребности в памяти под стек
• отсутствие деградации при неудачных наборах данных: быстрая сортировка легко деградирует до O(n^2), что хуже, чем худшее гарантированное время для сортировки Шелла

Принцип работы

Нужно отсортировать список [ 35, 33, 42, 10, 14, 19, 27, 44 ]. Берем d = 4 (d — это интервал). Разбиваем массив на пары элементов {35, 14}, {33, 19}, {42, 27} и {10, 44}.

Сравниваем пары элементов и меняем их местами при необходимости. Новый массив выглядит так:

Берем d = 2, получаем пары {14, 27, 35, 42} и {19, 10, 33, 44}.

Сравниваем пары элементов и меняем их местами при необходимости. Новый массив выглядит так:

Берем d = 1 и упорядочиваем элементы массива с помощью сортировки вставками:

Сложность

Реализация

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

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

    // Определяем шаг - половина массива
    let step = Math.floor(_arr.length / 2)

    // До тех пор, пока шаг больше нуля
    while (step > 0) {
      // Сравниваем все пары элементов
      for (let i = 0; i < _arr.length - step; i++) {
        let currentIndex = i
        let gapShiftedIndex = i + step

        while (currentIndex >= 0) {
          this.callbacks.visitingCallback(_arr[currentIndex])

          // Сравниваем и меняем элементы местами при необходимости
          if (
            this.comparator.lessThan(_arr[gapShiftedIndex], _arr[currentIndex])
          ) {
            const tmp = _arr[currentIndex]

            _arr[currentIndex] = _arr[gapShiftedIndex]

            _arr[gapShiftedIndex] = tmp
          }

          gapShiftedIndex = currentIndex
          currentIndex -= step
        }
      }

      // Уменьшаем шаг в 2 раза
      step = Math.floor(step / 2)
    }

    return _arr
  }
}

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

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

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

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

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

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

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

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

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

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

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

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

Результат:

❯ Сортировка подсчетом

Описание

• Википедия
• YouTube
• Визуализация

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

Алгоритм

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

1. На втором шаге мы считаем, сколько элементов массива A меньше или равны текущему индексу. Ci — количество элементов, меньших или равных i:

1. На третьем шаге мы помещаем элементы массива A в правильную позицию с помощью массива C. Для хранения отсортированных элементов используется массив B:

Сложность

Реализация

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

export default class CountingSort extends Sort {
  sort(arr, smallestItem, biggestItem) {
    // Инициализируем наименьшее и наибольшее числа
    // для построения массива сегментов (buckets) позже
    let _smallestItem = smallestItem || 0
    let _biggestItem = biggestItem || 0

    if (!smallestItem || !biggestItem) {
      arr.forEach((item) => {
        this.callbacks.visitingCallback(item)

        // Определяем наибольший элемент
        if (this.comparator.greaterThan(item, _biggestItem)) {
          _biggestItem = item
        }

        // Определяем наименьший элемент
        if (this.comparator.lessThan(item, _smallestItem)) {
          _smallestItem = item
        }
      })
    }

    // Инициализируем массив сегментов, который будет содержать
    // количество вхождений (частоту) элементов `arr`
    const buckets = new Array(_biggestItem - _smallestItem + 1).fill(0)
    arr.forEach((item) => {
      this.callbacks.visitingCallback(item)

      buckets[item - _smallestItem]++
    })

    // Добавляем предыдущие частоты к текущей для каждого числа в сегменте,
    // чтобы определить, сколько чисел меньше текущего должно стоять
    // слева от него
    for (let i = 1; i < buckets.length; i++) {
      buckets[i] += buckets[i - 1]
    }

    // Сдвигаем частоты вправо, чтобы они показывали правильные числа.
    // Если мы этого не сделаем, то `buckets[5]`, например, покажет, сколько
    // элементов, меньших 5, нужно поместить слева от 5 в отсортированном массиве,
    // ВКЛЮЧАЯ 5. После сдвига 5 будет исключено
    buckets.pop()
    buckets.unshift(0)

    // Формируем отсортированный массив
    const sortedArr = new Array(arr.length).fill(null)
    arr.forEach((item) => {
      this.callbacks.visitingCallback(item)

      // Получаем позицию элемента в отсортированном массиве
      const sortedPosition = buckets[item - _smallestItem]
      // Добавляем элемент на правильную позицию в отсортированном массиве
      sortedArr[sortedPosition] = item
      // Увеличиваем позицию текущего элемента в сегменте для будущих правильных размещений
      buckets[item - _smallestItem]++
    })

    return sortedArr
  }
}

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

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

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

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

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

  it('должен принимать максимальное/минимальное целые числа для ускорения сортировки', () => {
    const visitingCallback = jest.fn()
    const sorter = new CountingSort({ visitingCallback })

    // Определяем наибольшее число
    const biggestElement = Math.max(...notSortedArr)

    // Определяем наименьшее число
    const smallestElement = Math.min(...notSortedArr)

    const sortedArray = sorter.sort(
      notSortedArr,
      smallestElement,
      biggestElement,
    )

    expect(sortedArray).toEqual(sortedArr)
    // Обычно `visitingCallback()` вызывается 60 раз, но в данном случае
    // он должен быть вызван только 40 раз
    expect(visitingCallback).toHaveBeenCalledTimes(40)
  })

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

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

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

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

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

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

Результат:

❯ Поразрядная сортировка

Описание

• Википедия
• YouTube
• Визуализация

Поразрядная сортировка (radix sort) — это алгоритм сортировки, который выполняется за линейное время и предназначен для сортировки целых чисел, записанных цифрами. Однако поскольку в памяти компьютера любая информация представлена целыми числами, алгоритм пригоден для сортировки любых объектов, запись которых можно поделить на "разряды", например, строки и другие данные, которые можно преобразовать в набор байтов.

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

Выравнивать сравниваемые записи относительно друг друга можно в разную сторону, поэтому на практике существуют два варианта этой сортировки. Для чисел они называются в терминах значимости разрядов числа, и получается так: можно выровнять записи чисел в сторону менее значащих цифр (по правой стороне, в сторону единиц — LSD от least significant digit) или более значащих цифр (по левой стороне, со стороны более значащих разрядов — MSD от most significant digit).

При LSD-сортировке получается порядок, уместный для чисел. Например: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. Здесь значения сначала сортируются по единицам, затем по десяткам, сохраняя упорядоченность по единицам внутри десятков, затем по сотням, сохраняя упорядоченность по десяткам и единицам внутри сотен, и т.д.

При MSD-сортировке получается алфавитный порядок, который уместен для сортировки строк. Например "b, c, d, e, f, g, h, i, j, ba" отсортируется как "b, ba, c, d, e, f, g, h, i, j". Если MSD применить к числам, то получится алфавитный, а не числовой порядок: 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Сложность

Реализация

Приступаем к реализации алгоритма:

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

// `charCode` (кодовая единица UTF-16) (a = 97, b = 98 и т.д.) позволяет
// привязывать символы к группам от 0 до 25 (в английском алфавите 26 букв)
const BASE_CHAR_CODE = 97
// 0-9
const NUMBER_OF_POSSIBLE_DIGITS = 10
// a-z
const ENGLISH_ALPHABET_LENGTH = 26

export default class RadixSort extends Sort {
  sort(arr) {
    // Все элементы массива должны иметь одинаковый тип
    const isArrayOfNumbers = this.isArrayOfNumbers(arr)

    // Копируем оригинальный массив во избежание его модификации
    // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/structuredClone
    let sortedArr = structuredClone(arr)
    // Определяем нужное количество итераций
    const numPasses = this.determineNumPasses(sortedArr)

    // Формируем сегменты
    for (let i = 0; i < numPasses; i++) {
      const buckets = isArrayOfNumbers
        ? this.placeItemsInNumBucket(sortedArr, i)
        : this.placeItemsInCharBucket(sortedArr, i, numPasses)

      // Распаковываем сегменты
      sortedArr = buckets.flat()
    }

    return sortedArr
  }
}

Метод isArrayOfNumbers определяет тип элементов массива (числа или строки), а метод determineNumPasses — необходимое количество итераций:

// Количество итераций определяется длиной самого длинного элемента массива.
// Для целых чисел - это `log10(num)`, для строк - длина строки
determineNumPasses(arr) {
  if (this.isArrayOfNumbers(arr)) {
    return Math.floor(Math.log10(Math.max(...arr))) + 1
    // return Math.max(...arr.map((i) => i.toString().length))
  }

  return Math.max(...arr.map((i) => i.length))
}

isArrayOfNumbers(arr) {
  return Number.isInteger(arr[0])
}

Метод формирования числового сегмента:

placeItemsInNumBucket(arr, index) {
  // Это используется ниже для определения группы,
  // к которой принадлежит число
  const modded = 10 ** (index + 1)
  const divided = 10 ** index
  const buckets = this.createBuckets(NUMBER_OF_POSSIBLE_DIGITS)

  arr.forEach((item) => {
    this.callbacks.visitingCallback(item)

    if (item < divided) {
      buckets[0].push(item)
    } else {
      // Допустим, у нас есть элемент `1052` и текущий индекс `1` (начиная с `0`). Это означает,
      // что мы хотим использовать `5` как группу. `modded` будет равняться `10 ** (1 + 1)`
      // или `100`. Поэтому мы берем `1052 % 100 (52)`, делим на `10 (5.2)` и округляем до `5`
      const currentDigit = Math.floor((item % modded) / divided)
      buckets[currentDigit].push(item)
    }
  })

  return buckets
}

Метод создания сегмента:

createBuckets(size) {
  return new Array(size).fill().map(() => [])
}

Методы формирования строкового сегмента и получения кодовой единицы символа:

placeItemsInCharBucket(arr, index, numPasses) {
  const buckets = this.createBuckets(ENGLISH_ALPHABET_LENGTH)

  arr.forEach((item) => {
    this.callbacks.visitingCallback(item)
    const currentBucket = this.getCharCodeOfItemAtIndex(
      item,
      index,
      numPasses,
    )
    buckets[currentBucket].push(item)
  })

  return buckets
}

getCharCodeOfItemAtIndex(item, index, numPasses) {
  // Помещаем элемент в последнюю группу,
  // если он не готов к упорядочиванию
  if (numPasses - index > item.length) {
    return ENGLISH_ALPHABET_LENGTH - 1
  }

  // Если каждый символ упорядочен, используем первый символ для определения группы,
  // иначе, перебираем символы в обратном порядке
  const charPos = index > item.length - 1 ? 0 : item.length - index - 1

  // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt
  return item.toLowerCase().charCodeAt(charPos) - BASE_CHAR_CODE
}

import Sort from './sort'

// `charCode` (кодовая единица UTF-16) (a = 97, b = 98 и т.д.) позволяет
// привязывать символы к группам от 0 до 25 (в английском алфавите 26 букв)
const BASE_CHAR_CODE = 97
// 0-9
const NUMBER_OF_POSSIBLE_DIGITS = 10
// a-z
const ENGLISH_ALPHABET_LENGTH = 26

export default class RadixSort extends Sort {
  sort(arr) {
    // Все элементы массива должны иметь одинаковый тип
    const isArrayOfNumbers = this.isArrayOfNumbers(arr)

    // Копируем оригинальный массив во избежание его модификации
    // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/structuredClone
    let sortedArr = structuredClone(arr)
    // Определяем нужное количество итераций
    const numPasses = this.determineNumPasses(sortedArr)

    // Формируем сегменты
    for (let i = 0; i < numPasses; i++) {
      const buckets = isArrayOfNumbers
        ? this.placeItemsInNumBucket(sortedArr, i)
        : this.placeItemsInCharBucket(sortedArr, i, numPasses)

      // Распаковываем сегменты
      sortedArr = buckets.flat()
    }

    return sortedArr
  }

  placeItemsInNumBucket(arr, index) {
    // Это используется ниже для определения группы,
    // к которой принадлежит число
    const modded = 10 ** (index + 1)
    const divided = 10 ** index
    const buckets = this.createBuckets(NUMBER_OF_POSSIBLE_DIGITS)

    arr.forEach((item) => {
      this.callbacks.visitingCallback(item)

      if (item < divided) {
        buckets[0].push(item)
      } else {
        // Допустим, у нас есть элемент `1052` и текущий индекс `1` (начиная с `0`). Это означает,
        // что мы хотим использовать `5` как группу. `modded` будет равняться `10 ** (1 + 1)`
        // или `100`. Поэтому мы берем `1052 % 100 (52)`, делим на `10 (5.2)` и округляем до `5`
        const currentDigit = Math.floor((item % modded) / divided)
        buckets[currentDigit].push(item)
      }
    })

    return buckets
  }

  placeItemsInCharBucket(arr, index, numPasses) {
    const buckets = this.createBuckets(ENGLISH_ALPHABET_LENGTH)

    arr.forEach((item) => {
      this.callbacks.visitingCallback(item)
      const currentBucket = this.getCharCodeOfItemAtIndex(
        item,
        index,
        numPasses,
      )
      buckets[currentBucket].push(item)
    })

    return buckets
  }

  getCharCodeOfItemAtIndex(item, index, numPasses) {
    // Помещаем элемент в последнюю группу,
    // если он не готов к упорядочиванию
    if (numPasses - index > item.length) {
      return ENGLISH_ALPHABET_LENGTH - 1
    }

    // Если каждый символ упорядочен, используем первый символ для определения группы,
    // иначе, перебираем символы в обратном порядке
    const charPos = index > item.length - 1 ? 0 : item.length - index - 1

    // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt
    return item.toLowerCase().charCodeAt(charPos) - BASE_CHAR_CODE
  }

  // Количество итераций определяется длиной самого длинного элемента массива.
  // Для целых чисел - это `log10(num)`, для строк - длина строки
  determineNumPasses(arr) {
    if (this.isArrayOfNumbers(arr)) {
      return Math.floor(Math.log10(Math.max(...arr))) + 1
      // return Math.max(...arr.map((i) => i.toString().length))
    }

    return Math.max(...arr.map((i) => i.length))
  }

  isArrayOfNumbers(arr) {
    return Number.isInteger(arr[0])
  }

  createBuckets(size) {
    return new Array(size).fill().map(() => [])
  }
}

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

// algorithms/sorting/__tests__/radix-sort.test.js
import RadixSort from '../radix-sort'
import { SortTester } from '../sort-tester'

// Константы временной сложности
const ARRAY_OF_STRINGS_VISIT_COUNT = 24
const ARRAY_OF_INTEGERS_VISIT_COUNT = 77

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

  it('должен посетить массив строк `n (количество строк) x m (длина самой длинной строки)` раз', () => {
    SortTester.testAlgorithmTimeComplexity(
      RadixSort,
      ['zzz', 'bb', 'a', 'rr', 'rrb', 'rrba'],
      ARRAY_OF_STRINGS_VISIT_COUNT,
    )
  })

  it('должен посетить массив целых чисел `n (количество чисел) x m (длина самого длинного числа)` раз', () => {
    SortTester.testAlgorithmTimeComplexity(
      RadixSort,
      [3, 1, 75, 32, 884, 523, 4343456, 232, 123, 656, 343],
      ARRAY_OF_INTEGERS_VISIT_COUNT,
    )
  })
})

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

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

Результат:

❯ Блочная сортировка

Описание

• Википедия
• YouTube
• Визуализация

Блочная сортировка (bucket sort) — это алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем выполнения.

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

Преимущества: относится к классу быстрых алгоритмов с линейным временем выполнения O(n) (на удачных входных данных).

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

Принцип работы

Алгоритм работает следующим образом:

1. Инициализация массива пустых buckets.
2. Перебор элементов исходного массива, помещение каждого в его bucket.
3. Сортировка непустых блоков.
4. Объединение блоков в массив слева направо.

Распределение элементов массива по блокам:

Сортировка элементов внутри блоков:

Сложность

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

В худшем случае временная сложность алгоритма составляет O(n^2), если для сортировки блоков используется сортировка вставками, которая часто для этого применяется, поскольку ожидается, что блок содержит мало элементов из исходного массива. В худшем случае все элементы исходного массива помещаются в один блок.

Если худшее время выполнения промежуточной сортировки составляет O(n * log(n)), то худшее время блочной сортировки также будет составлять O(n * log(n)).

В среднем, когда элементы исходного массива относительно равномерно распределены, может быть доказано, что блочная сортировка в среднем выполняется за O(n + k), где k — количество блоков.

Реализация

// algorithms/sorting/bucket-sort.js
import RadixSort from './radix-sort'

const sorter = new RadixSort()

export default function bucketSort(arr, bucketSize = 1) {
  // Создаем блоки
  const buckets = new Array(bucketSize).fill().map(() => [])

  // Находим минимальное значение
  const minValue = Math.min(...arr)
  // Настрой максимальное значение
  const maxValue = Math.max(...arr)

  // Определяем размер блока
  const _bucketSize = Math.ceil(Math.max(1, (maxValue - minValue) / bucketSize))

  // Распределяем элементы исходного массива по группам
  for (const item of arr) {
    const index = Math.floor((item - minValue) / _bucketSize)

    // Крайний случай для максимального значения
    if (index === bucketSize) {
      buckets[bucketSize - 1].push(item)
    } else {
      buckets[index].push(item)
    }
  }

  // Сортируем блоки
  for (let i = 0; i < buckets.length; i += 1) {
    // Используем поразрядную сортировку. Это может дать среднюю
    // временную сложность `O(n + k)` для сортировки одного блока
    // (где `k` - количество цифр самого длинного числа)
    buckets[i] = sorter.sort(buckets[i])
  }

  // Объединяем отсортированные блоки в один массив
  const sortedArr = buckets.flat()

  return sortedArr
}

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

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

describe('BucketSort', () => {
  it('должен отсортировать массивы чисел с разным количеством блоков', () => {
    expect(BucketSort(notSortedArr, 4)).toEqual(sortedArr)
    expect(BucketSort(equalArr, 4)).toEqual(equalArr)
    expect(BucketSort(reverseArr, 4)).toEqual(sortedArr)
    expect(BucketSort(sortedArr, 4)).toEqual(sortedArr)

    expect(BucketSort(notSortedArr, 10)).toEqual(sortedArr)
    expect(BucketSort(equalArr, 10)).toEqual(equalArr)
    expect(BucketSort(reverseArr, 10)).toEqual(sortedArr)
    expect(BucketSort(sortedArr, 10)).toEqual(sortedArr)

    expect(BucketSort(notSortedArr, 50)).toEqual(sortedArr)
    expect(BucketSort(equalArr, 50)).toEqual(equalArr)
    expect(BucketSort(reverseArr, 50)).toEqual(sortedArr)
    expect(BucketSort(sortedArr, 50)).toEqual(sortedArr)
  })

  it('должен отсортировать массивы чисел с одной группой', () => {
    expect(BucketSort(notSortedArr)).toEqual(sortedArr)
    expect(BucketSort(equalArr)).toEqual(equalArr)
    expect(BucketSort(reverseArr)).toEqual(sortedArr)
    expect(BucketSort(sortedArr)).toEqual(sortedArr)
  })
})

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

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

Результат:

На сегодня это все, друзья. Увидимся в следующей части.

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩