Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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

Листинг 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).

Следует отметить, что алгоритм простых вставок выгодно использовать для файлов небольшого размера. Кроме этого, он пригоден для сортировки больших файлов, но с малым числом инверсий.

 

<== предыдущая лекция | следующая лекция ==>
Ар­гу­мен­ты в под­твер­жде­ние | Растырған: академ.проф. С.С.Алмухамбетов

mylektsii.ru - Мои Лекции - 2015-2019 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал