1

Каково количество упомянутых ранее упорядоченных элементов в массиве при сортировке вставкой?

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

Сколько раннее упорядоченных элементов?

2
  • переформулируйте вопрос. На каком шаге или когда? После окончания сортировки - все. Сколько на предыдущем шаге - ну зависит от номера шага
    – pavel
    Commented 12 янв. 2018 в 7:24
  • Сколько уже просмотрено - столько уже ранее упорядоченных. На i-том шаге алгоритма будет i ранее упорядоченных элементов. Commented 12 янв. 2018 в 7:58

1 ответ 1

2

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

Так понятнее? :)

Смотрите - когда вы вставляете k-й элемент, предыдущие уже стоят в порядке. Сколько этих предыдущих? Правильно, k-1...

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.