Индуктивное доказательство подсчета сортировки?

Question

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

for i = 1 to k
    C[i] = 0

for j = 1 to n
   C[A[j]] = C[A[i]] + 1

for i = 2 to k
   C[i] = C[i] + C[i-1]

for j=n to 1
   B[C[A[j]]] = A[j]
   C[A[j]]--

Я предполагаю, что доказательство начнется с базового случая, когда массив имеет только один элемент

базовый случай из n = 1, несортированный массив A [1] = a1, отсортированный массив B [1] = a1

Индуктивный шаг: ???Я не уверен, как справиться с этим типом индуктивного доказательства.

Answer 1

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

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

Наши базовые случаи также могут быть пустыми массивами и массивами первого размера.Любой алгоритм сортировки на них тривиально стабилен.

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

Индуктивный шаг - сложныйчасть.Рассмотрим массив размером k + 1.Этот массив имеет самый большой, последний элемент (из элементов, которые являются самыми большими по критериям сортировки, есть один, который появляется последним в массиве).Рассмотрим массив размера k, полученный путем удаления этого элемента из массива размера k + 1 и смещения элементов, появляющихся справа от него влево, чтобы заполнить пробел.По предположению индукции счетная сортировка устойчива на этом массиве размера k.Чтобы доказать, что сортировка подсчета стабильна на массиве элементов размера k + 1, мы должны поэтому показать только то, что сортировка подсчета не может поместить самый большой, последний элемент перед любыми элементами того же размера.Чтобы убедиться, что это правда, обратите внимание, что при построении выходного массива B j принимает значения n, n-1,…, 1 в порядке убывания, то есть всех элементов с тем же значением, что и у нашего самого большого последнего элемента,это достигнет нашего элемента первым.Из-за этого гарантированно размещать этот элемент дальше вправо в B, чем любой другой элемент с таким же значением, поскольку C [A [j]] уменьшается, а не увеличивается в цикле, строящем B.