Вычислительная сложность алгоритма

Листинг 1. Алгоритм сортировки простыми вставками

template < typename T>

void SortInsert(T * k, int n) {

T temp;

int j;

for (int i = 1; i < n; ++i) { // n – 1

temp = k[i]; // n – 1

for (int j = i - 1; j > -1 & & k[j] > temp; --j)

k[j + 1] = k[j];

k[j + 1] = temp; // n – 1

}

}

Вычислительная сложность алгоритма

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

Минимальная вычислительная сложность алгоритма соответствует сортировке изначально упорядоченной последовательности и определяется величиной O (n). Максимальная вычислительная сложность O (n 2) получается в случае сортировки последовательности, упорядоченной в противоположном порядке.

Устойчивость алгоритма обеспечивается проверкой условия k[j] > temp (см. листинг 1), в результате чего k (j) разместится в конце серии равных ему элементов отсортированной части массива, то есть взаимное расположение равных элементов после выполнения сортировки не изменится. В случае проверки условия k[j] > = temp алгоритм будет неустойчив.

Модификации алгоритма

1. Время работы алгоритма можно несколько сократить, если размещать элементы в массиве, начиная с k (1). В элемент k (0) (вместо temp) заносится текущая вставляемая запись k (i). При вставке элемента в цикле по j отпадает необходимость проверки условия j > -1. Такая модификация алгоритма носит название метода барьеров.

2. Вычислительную сложность сортировки вставками можно также уменьшить, используя двоичный поиск для нахождения нужной позиции для k (i) в отсортированной части массива k (0), k (1),..., k (i - 1). Сравним k (i) с записью, расположенной в середине отсортированной части; если k (i) меньше, то позиция для k (i), очевидно, находится в левой её половине; если больше, то в правой. Производим аналогичные действия с выбранной половиной отсортированной части массива и так до тех пор, пока её размер не станет равным 1, в этом случае позиция найдена. Это сокращает число сравнений с O (n2) до O (n log n). Однако даже если позиция p для k (i) найдена за O (log n) шагов, каждый из элементов k (p + 1), k (p + 2),..., k (i - 1) должен быть сдвинут на одну позицию вправо. Эта операция, выполняемая n раз, требует O (n 2) перемещений. Таким образом, двоичный поиск не позволяет уменьшить порядок зависимости вычислительной сложности от n.

3. Еще один приём, позволяющий сократить время работы алгоритма простых вставок, заключается в следующем. Можно располагать отсортированную часть массива не в начале, а в середине массива, и двигать записи в ту сторону, где их меньше (в описанном выше

алгоритме записи сдвигались всегда вправо). Это позволяет сэкономить примерно половину времени работы. Такая модификация алгоритма сортировки простыми вставками называется двухпутевыми вставками.