Skip to main content

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

Описание

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



Сложность

ЛучшееСреднееХудшееПамятьСтабильность
nn^2n^21Да

Реализация

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