Алгоритм сортировки 2

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

  • Разделите массив на два подмассива: отсортированный и несортированный подмассив (аналогично сортировке по выбору)
  • На каждой итерации удалите первый элемент из несортированного подмассива и вставьте его в правильную позицию (в зависимости от того, следует ли сортировать по возрастанию или по убыванию) в отсортированном подмассиве.
  • Итерировать до тех пор, пока не будет удален последний элемент несортированного массива

Давайте посмотрим на пример, чтобы четко понять шаги. Предположим, что сортируемый массив (8, 4, 6, 3, 1, 9, 5)

Первоначально отсортированный подмассив состоит только из первого элемента, а несортированный подмассив состоит из остальных элементов в массиве, как показано на рисунке выше. Мы выбираем первый элемент несортированного подмассива, который равен 4, и мы должны вставить его в правильную позицию в отсортированном подмассиве. Начиная с 4 ‹8, мы сдвигаем 8 вправо на одну ячейку и вставляем 4. Теперь 4 был удален из несортированного подмассива и стал частью отсортированного подмассива. Затем мы выбираем 6, и поскольку 6 меньше 8 и больше 4, мы перемещаем только 8 вправо на одну ячейку и вставляем 6. Затем мы выбираем 3 и 3 меньше 4, 6 и 8. Следовательно, мы сдвигаем все 4, 6 и 8 вправо на одну ячейку и вставляем 3. Мы продолжаем этот процесс до тех пор, пока последний элемент (который равен 5) не будет удален из несортированного подмассива.

Реализация на C

Анализ вставочной сортировки

  • Сортировка вставкой - это алгоритм на месте, что означает, что ему не требуется дополнительное пространство памяти для выполнения сортировки.
  • Оптимальная временная сложность сортировки вставкой - O (n). Когда массив уже отсортирован (что является лучшим случаем), сортировка вставкой должна выполнять только одно сравнение на каждой итерации (см. Рисунок ниже) и, следовательно, O (n).

  • Наихудшая сложность - O (n²). Когда массив сортируется в обратном порядке (что является наихудшим случаем), мы должны выполнить i число сравнений за i ᵗʰ итерацию. (см. рисунок ниже).

Общее количество сравнений, которое необходимо выполнить, составляет 1 + 2 + 3 +…. + (n-1), что равно n (n-1) / 2, следовательно, O (n²).

  • Из-за квадратичной временной сложности наихудшего случая сортировка вставкой была бы неэффективной для сортировки большого количества элементов. Однако, как и при сортировке по выбору, вставка будет удобна, когда доступное свободное пространство памяти ограничено из-за возможности сортировки на месте.
  • Существуют разные варианты сортировки вставок. В этой статье представлена ​​базовая версия. Один из вариантов - использовать двоичный поиск, чтобы найти правильную позицию для вставки элементов (в отличие от линейного поиска, который используется в версии, представленной в этой статье). Это улучшило бы сложность наихудшего случая до O (n log (n)).

Сортировка вставкой против сортировки по выбору

  • После i итераций в сортировке выбора первые элементы i в массиве будут самыми маленькими элементами i в массиве, и они будут в отсортированный порядок. Однако после i итераций в сортировке вставкой будут отсортированы только первые элементы i (см. Рисунок ниже).

  • Оба алгоритма сортировки имеют одинаковую временную сложность наихудшего случая, равную O (n²). Однако наилучшая временная сложность сортировки вставкой - O (n), а сортировки выбора - O (n²).
  • Оба являются алгоритмами сортировки на месте и, следовательно, имеют пространственную сложность O (1).

Надеюсь, эта статья окажется для вас полезной!