Алгоритм сортировки простыми вставками является непосредственной реализацией идеи сортировки вставками-
Работа добавлена на сайт samzan.net:
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 алгоритм будет неустойчив.
Модификации алгоритма
- 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(nlog n). Однако даже если позиция p для k(i) найдена за O(log n) шагов, каждый из элементов k(p + 1), k(p + 2), ..., k(i - 1) должен быть сдвинут на одну позицию вправо. Эта операция, выполняемая n раз, требует O(n2) перемещений. Таким образом, двоичный поиск не позволяет уменьшить порядок зависимости вычислительной сложности от n.
- 3. Еще один приём, позволяющий сократить время работы алгоритма простых вставок, заключается в следующем. Можно располагать отсортированную часть массива не в начале, а в середине массива, и двигать записи в ту сторону, где их меньше (в описанном выше
алгоритме записи сдвигались всегда вправо). Это позволяет сэкономить примерно половину времени работы. Такая модификация алгоритма сортировки простыми вставками называется двухпутевыми вставками.
- 4. Алгоритм сортировки простыми вставками можно применить к данным, хранящимся в виде линейного связного двунаправленного списка. В этом случае число сравнений остается прежним, а число присваиваний сокращается, поскольку вставка элемента в отсортированную часть списка не требует поэлементного сдвига, а осуществляется путем изменения значений указателей.
- 5. Алгоритм сортировки простыми вставками можно применить к данным, хранящимся в виде линейного связного однонаправленного списка. В этом случае каждый элемент сортируемого списка вставляется во вновь создаваемый упорядоченный однонаправленный список. Число сравнений – прежнее, а число присваиваний определяется величиной O(n).
Следует отметить, что алгоритм простых вставок выгодно использовать для файлов небольшого размера. Кроме этого, он пригоден для сортировки больших файлов, но с малым числом инверсий.
2. Закономерности наследственности 2
3. Основы психометрии
4. освободительного восстания
5. Стиль государственного управления, его элементы и свойства.html
6. пол. Вполне закономерно что такой подход в корне меняет понимание этой проблемы и способствует появлению пр
7. Реферат- Путешествие по горному Крыму
8. Рестрикция по главному комплексу гистосовместимости в чувствительности к туберкулезу
9. Вопросы местного значения и полномочия органов местного самоуправления города Екатеринбург
10. РЕФЕРАТ дисертації на здобуття наукового ступеня кандидата технічних наук7
11. Открытость российской экономики растущая степень ее интеграции в систему мировой торговли требуют
12. Применение статистических методов в управлении финансами финансово-промышленной группы
13. Лабораторная работа ИССЛЕДОВАНИЕ МЕТОДОВ ОБЕСПЕЧЕНИЯ ЗАДАННОЙ ТОЧНОСТИ ПРИ СБОРКЕ ЭЛЕКТРОННОЙ АППАРА
14. Аракчеев Алексей Андреевич.html
15. на тему- Поговорим подробнее о роде и числе имен существительных и прилагательных Упорова Олеся Юрьевна
16. Программирование системы уравнений
17. Автоматизированные системы управления Разработка элементов информационной системы средства
18. Основные психические процессы человека Основные психические процессы человека
19. тема льготы инвестиционный климат на федеральном и региональном уровнях наличие заинтересованных в иннова
20. Понятие международного экологического права. Международные экологические правоотношения