пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Сортировка. Сортировка методом бинарных включений

Идея метода сходна с сортировкой прямыми включениями.Часть последовательности до испытуемого (i-ого) элемента ("готовая" часть) делится пополам и i-ый элемент сравнивается с элементом, стоящим на середине, после чего границы поиска уменьшаются в два раза. Получившийся полуинтервал делится пополам, и процесс повторяется до тех пор, пока не будет определено место включения i-ого элемента. Затем происходит сдвиг вправо на одну позицию тех элементов, которые расположены от места включения до i-ого элемента, освобождая таким образом позицию для i-ого элемента.

Текстовый алгоритм:

1.Начало.

2.Выполнить цикл, пока имеет значение от 2 до с шагом = 1

а) X = A(i), l = 1, r = i-1

б) Если l > r, то:

1) выполнить цикл, пока j имеет значение от (i-1) до l с шагом = -1

телоцикла: A(j + 1) = A(j)

2) присвоить A(l) = Xиначе:

1) присвоить m = (l + r) \ 2

2) если X<A(m), то r = m – 1 иначе l = m + 1

3) перейти к пункту б).  3.Конец.


17.06.2016; 16:34
хиты: 143
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь