Рассылка закрыта
При закрытии подписчики были переданы в рассылку "RFpro.ru: Программирование на языке Pascal" на которую и рекомендуем вам подписаться.
Вы можете найти рассылки сходной тематики в Каталоге рассылок.
Сортировка вставкой
| Информационный Канал Subscribe.Ru |
| Подисчиков: 90 | |
| Выпуск номер: 6 | |
|
Сегодня в выпуске: 1. ) Сортировка вставкой 1. )Сортировка вставкойСортировка вставкой является последней из класса простых алгоритмов сортировки. При сортировке вставкой сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум элементам. Затем делается вставка четвертого элемента в список из трех элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены. Например, для массива "dcab" сортировка вставкой будет проходить следующим образом: - исходное состояние: d c a b;- первый проход: c d a b; - второй проход: a c d b; - третий проход: a b c d. Ниже приводится алгоритм сортировки вставкой: { сортировка вставкой } procedure Inser(var item: DataArray; count:integer); var i, l: integer; x: DataItem; begin for i := 2 to count do begin x := item[i]; j := i-1; while (x begin item[j+1] := item[j]; j := j-1; end; item[j+1] := x; end; end; { конец сортировки вставкой } В отличие от сортировки пузырьковым методом и сортировки вы- бором число операций сравнения для сортировки вставкой зависит от исходной упорядоченности массива элементов. Если исходный массив уже упорядочен, то число операций сравнения равно n-1. Если массив упорядочен в обратном порядке, то число операций сравнения равно 1/2 (n**2 +n)-1,давая в среднем значение 1/4 (n**2+n-2). Число операций обмена будет следующим: - для лучшего случая: 2 (n-1);- в среднем: 1/4 (n**2+9n-10); - для худшего случая: 1/2 (n**2+3n-4). Таким образом, число операций обмена для худшего случая бу- дет столь же большим, как и для сортировок пузырьковым методом и сортировок выбором. Число операций обмена для среднего случая будет лишь на немного меньше. Однако сортировка вставкой имеет два преимущества. Во-первых, она обладает естественным поведением, т. е. она выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направле- нии. Это делает сортировку вставкой полезной для упорядочения почти отсортированных массивов. Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов сортируется с использованием двух ключей, то после завершения сортировки встав- кой он по-прежнему будет упорядочен по двум ключам. Несмотря на то, что число сравнений может быть довольно не- большим для определенных наборов данных, постоянные сдвиги масси- ва требуют выполнения большого числа операций пересылок. Однако, сортировка вставкой имеет естественное поведение, требуя наимень- шее число операций обмена для почти упорядоченного списка и наи- большее число операций обмена, когда массив упорядочен в обратном направлении. |
| http://subscribe.ru/
E-mail: ask@subscribe.ru |
Отписаться
Убрать рекламу |
| В избранное | ||
