Алгоритм сортировки методом прямого включения без барьера

for i = 2 to n

x = a(i)

for j = i - 1 downto 1

if x < a(j)

then a(j + 1 ) = a(j)

else go to L

endif

next j

L: a(j + 1 ) = x

next i

return

Недостатком приведенного алгоритма является нарушение технологии структурного программирования, при которой нежелательно применять безусловные переходы. Если же внутренний цикл организовать как цикл while, то необходима постановка «барьера», без которого при отрицательных значениях ключей происходит потеря значимости и «зависание» компьютера.

Алгоритм сортировки методом прямого включения с барьером

for i = 2 to n

x = a(i)

a (0) = x { a (0) - барьер}

j = i - 1

while x < a(j) do

a(j + 1 ) = a(j)

j = j - 1

endwhile

a(j + 1 ) = x

next i

return

Эффективность

Минимальные оценки числа сравнений Cmin и перемещений Mmin встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки Сmax и Mmax - когда они первоначально расположены в обратном порядке.

Количество сравнений в худшем случае, когда массив отсортирован противоположным образом,
Сmax = n(n - 1)/2, то есть порядок
О (n 2). Количество перестановок
Mmax = Cmax + 3(n -1), то есть порядок
О (n 2). Если же массив уже отсортирован, то число сравнений и перестановок минимально: Cmin = n -1; Mmin = 3(n -1).

6. Понятие списковой структуры. Стек.

К полустатическим структурам данных относят стеки, деки и очереди.

Списки

Это набор связанных элементов данных, которые в общем случае могут быть разного типа.

Пример списка:

Е₁, Е₂,......... Е_n,... n > 1 и не зафиксировано.

Количество элементов списка может меняться в процес­се выполнения программы. Различают 2 вида списков:

1) Несвязные

2) Связные

В несвязных списках связь между элементами данных выражена неявно. В связных списках в элемент данных заносится указатель связи с последующим или предыдущим эле­ментом списка.

Стеки, деки и очереди - это несвязные списки. Кроме того, они относятся к последовательным спискам, в которых не­явная связь отображается их последовательностью.

Стеки

Очередь вида LIFO (Last In First Out - Последним при­шел, первым ушел), при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее по­следним, называется стеком. Это одна из наиболее употреб­ляемых структур данных, которая оказывается весьма удобной при решении различных задач.

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

Графически стек можно представить следующим образом:

Рис. 2.12

Первый элемент заносится вниз стека. Выборка из стека осуществляется с вершины, поэтому стек является структу­рой с ограниченным доступом

Операции, производимые над стеками:

1. Занесение элемента в стек.

Push(S,x),

где S - идентификатор стека, x - заносимый элемент.

2. Выборка элемента из стека.

Pop(S)

3. Определение пустоты стека.

Empty(S)

4. Прочтение элемента без его выборки из стека.

StackTop(S)

5. Определение переполнения стека (для полустатических структур)

Full(S)

i = указатель вершины

Push(S,x)

i = i+1

S(i) = x

return

Pop(S)

x = S(i)

i = i -1

return

Empty(S)

if i = 0

then “пусто”

Stop

return

endif

Full(S)

if i = maxS

then “переполнение”

Stop

return

endif

StackTop(S)

x = S(i)

return

Pop(S)

if i = 0 then “пусто”

Stop

return

endif

X = S(i)

i = i -1

return

Empty(S)

if i = 0 then empty = true

else empty = false

endif

return

Pop(S)

Empty(S)

if empty = true

then “пусто”

Stop

return

endif

x = S(i)

i = i -1

return

Push(S,i)

if i = maxS

then “переполнение”

Stop

return

endif

i = i+1

S(i) = x

return