Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
24.
Алгоритм сортировки простыми вставками является непосредственной реализацией идеи сортировки вставками: очередная запись вставляется среди ранее отсортированных записей [2, 5 10, 19, 26, 31, 43]
К этому шагу первые i записей исходного массива уже отсортированы и на рисунке помечены серым цветом. Запись k(i) необходимо вставить на соответствующую позицию в отсортированной части массива. С этой целью значение k(i) сохраняется во вспомогательной переменной temp. Затем последовательно сравниваются k(j), j = i – 1, …, 0, со значением temp до тех пор, пока k(j) > temp, при этом каждый раз значение k(j) присваивается записи k(j + 1). В результате находится такое p, что k(p) ≤ temp, либо значение temp меньше любого из k(j) (в этом случае p = – 1). Шаг алгоритма завершается размещением значения записи temp в элемент массива k(p + 1).
Реализация на языке С++ алгоритма сортировки простыми вставками на примере n записей типа T, хранящихся в массиве k, представлена в листинге 1. Комментарии в правой части листинга содержат число выполнения соответствующей строки алгоритма и поясняют оценку его вычислительной сложности. В формулах через ui обозначено число записей k(j), j = 0, 1, ..., i – 1, которые больше записи k(i), то есть составляют с ней инверсию.
Листинг 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(n2) получается в случае сортировки последовательности, упорядоченной в противоположном порядке.
Устойчивость алгоритма обеспечивается проверкой условия k[j] > temp (см. листинг 1), в результате чего k(j) разместится в конце серии равных ему элементов отсортированной части массива, то есть взаимное расположение равных элементов после выполнения сортировки не изменится. В случае проверки условия k[j] >= temp алгоритм будет неустойчив.
Модификации алгоритма
алгоритме записи сдвигались всегда вправо). Это позволяет сэкономить примерно половину времени работы. Такая модификация алгоритма сортировки простыми вставками называется двухпутевыми вставками.
Следует отметить, что алгоритм простых вставок выгодно использовать для файлов небольшого размера. Кроме этого, он пригоден для сортировки больших файлов, но с малым числом инверсий.