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

Реализация алгоритма ПрВст

Алгоритм ПрВст

Сортировка простыми вставками

Самый простой способ сортировки^{2В названиях алгоритмов мы будем следовать Кнуту.}, который приходит в голову, - это упорядочение данных по мере их поступления. В этом случае при вводе каждого нового значения можно опираться на тот факт, что все предыдущие элементы уже образуют отсортированную последовательность.

1. Первый элемент записать "не раздумывая".

2. Пока не закончится последовательность вводимых данных, для каждого нового ее элемента выполнять следующие действия:

- начав с конца уже существующей упорядоченной последовательности, все ее элементы, которые больше, чем вновь вводимый элемент, сдвинуть на 1 шаг назад;

- записать новый элемент на освободившееся место.

При этом, разумеется, можно прочитать все вводимые элементы одновременно, записать их в массив, а потом "воображать", что каждый очередной элемент был введен только что. На суть и структуру алгоритма это не повлияет.

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

Для того чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний 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;

Дата добавления: 2014-01-03