Метод прямых вставок с барьером (ПрВстБар)

Дата добавления: 2014-11-27; просмотров: 595; Нарушение авторских прав

Для того чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний var) и будем записывать в нее поочередно каждый вставляемый элемент (сравните строки {*} и {**} в приведенных вариантах программы). В тех случаях, когда вставляемое значение окажется меньше, чем a[1], компонента a[0] будет работать как "барьер", не дающий индексу j выйти за нижнюю границу массива. Кроме того, компонента a[0] может заменить собою и дополнительную переменную х:

for i:= 2 to N do if a[i-1]>a[i] then begin a[0]:= a[i]; {*} j:= i-1; while a[j]>a[0] do {**} begin a[j+1]:= a[j]; j:= j-1; end; a[j+1]:= a[0]; end;

Эффективность алгоритма ПрВстБар

Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная последовательность данных. Тогда алгоритм ПрВстБар совершит N-1 сравнение и 0 пересылок данных.

В худшем же случае - когда входная последовательность упорядочена "наоборот" - сравнений будет уже (N+1)*N/2, а пересылок (N-1)*(N+3). Таким образом, этот алгоритм имеет сложность ~N² (читается "порядка эн квадрат") по обоим параметрам.

Пример сортировки

Предположим, что нужно отсортировать следующий набор чисел:

5 3 4 3 6 2 1

Выполняя алгоритм ПрВстБар, мы получим такие результаты (подчеркнута уже отсортированная часть массива, полужирным выделена сдвигаемая последовательность, а квадратиком выделен вставляемый элемент):

Состояние массива Сдвиги Сравнения Пересылки данных0 шаг: 5343621 1 шаг: 5343621 1 1+1³⁾ 1+2⁴⁾2 шаг: 3543621 1 1+1 1+23 шаг: 3453621 2 2+1 2+24 шаг: 3345621 0 1 05 шаг: 3345621 5 5+1 5+26 шаг: 2334561 6 6+1 6+2Результат: 1233456 15 20 25

<== предыдущая лекция	\|	следующая лекция ==>
Простые сортировки	\|	Алгоритм УлШелл