Метод вставки с прямым включением можно улучшить, если отыскивать место для вставляемой записи в упорядоченной подтаблице с помощью метода бинарного (дихотомического, двоичного, логарифмического) поиска. Эта модификация метода вставки названа вставкой с бинарным включением.
Рассмотрим j ‑й шаг сортировки (j =2, 3, ..., n ). Если K [ j ]>= K [ j -1] , то упорядоченность не нарушилась и следует перейти к R [ j +1]– ой записи. Если же K [ j ]< K [ j -1] , то R [ j ] запоминается в рабочей переменной (Rab = R [ j ]) и для нее ищется место в упорядоченной части таблицы – в подтаблице. Обозначим нижнюю границу индекса этой подтаблицы через ng , верхнюю - через vg (первоначально ng =1. vg =j-1 ).
Согласно бинарному поиску ключ K [ j ] рассматриваемой записи R [ j ] должен сначала сравниться с ключом K [ i ] записи R [ i ] , находящейся в середине упорядоченной подтаблицы (i=(ng+vg) div 2) . Если K [ j ]> K [ i ], то отбрасывается (то есть больше не рассматривается) левая часть подтаблицы- записи с меньшими ключами (ng = i +1) . Если K [ j ]< K [ i ] , то отбрасывается правая часть подтаблицы - записи с большими ключами (vg = i -1). В оставшейся части подтаблицы поиск продолжается. Процесс деления частей подтаблицы пополам продолжается до тех пор, пока не возникнет одна из следующих ситуаций:
1) K [ j ]= K [ i ] , следовательно, (i+1) -я позиция является местом для рассматриваемой записи. Сдвинем записи R [ i +1], R [ i +2], …, R [ j -1] на одну позицию вправо и освободим тем самым место для вставки (R [ i +1]= Rab ).
2) K [ j ]<> K [ i ] и ng > vg – ключи не совпали, а длина последней подтаблицы равна 1. В этом случае местом для вставки является позиция ng , поэтому записи R [ ng ], R [ ng +1], … , R [ j -1] должны быть сдвинуты на одну позицию вправо (R [ ng ]= Rab ) .
Алгоритм бинарного поиска подробно описан в разделе "Дихотомический поиск по совпадению".
Рассмотрим на примере j -й шаг сортировки (определяется место записи с ключом, равным 9; j =7, K [ j ]=9 ):
Среднее число сравнений для данного метода составляет n log 2 (n) .
Метод двухпутевой вставки
Метод двухпутевой вставки является модификацией метода вставки с прямым включением; он позволяет улучшить характеристики сортировки.
Для реализации этого метода необходим дополнительный объем памяти, равный объему, занимаемому таблицей, подлежащей сортировке (назовем его зоной вывода T ). На первом шаге сортировки в середину зоны вывода (позиция m=(n div 2)+1 ) помещается первая запись таблицы R. Остальные позиции Т пока пусты. На последующих шагах сортировки ключ очередной записи R [ j ] (j =2, 3, …, n ) сравнивается с ключом записи T [ m ] и, в зависимости от результатов сравнения, место для R [ j ] отыскивается в Т слева или справа от T [ m ] методом вставки. При этом должны запоминаться номера самого левого (l ) и самого правого (r ) внесенных в зону вывода элементов. Конечные значения l и r равны 1 и n соответственно.
В алгоритме должны быть учтены также следующие ситуации:
ключ записи R[j] меньше ключа записи T[m] , но l=1 ;
ключ записи R[j] больше ключа записи T[m] , но r=n .
В этих случаях для вставки записи R [ j ] необходимо осуществлять сдвиг записей подтаблицы вместе с записью T [ m ] вправо или влево (используется метод вставки с прямым включением).
Рассмотрим пример сортировки с использованием этого метода.
Пусть исходная последовательность ключей таблицы имеет вид:
24, 1, 28, 7, 25, 3, 6, 18, 8 (n =9, m =(n div 2)+ 1=5)
|
Номер шага |
Зона вывода |
|||||||||
Сортировка методом прямого включения, так же как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.
Сортировка методом прямого включения, как и все описанные выше, производится по шагам. На k - м шаге считается, что часть массива, содержащая первые k-1 элементов, уже упорядочена, то есть
а ≤ а ≤ ... ≤ a .
Далее необходимо взять k - й элемент и подобрать для него такое место в отсортированной части массива, чтобы после его вставки упорядоченность не нарушалась, то есть надо найти такое j (1 ≤ j ≤ k -1), что а [j] ≤ a[k] < a. Затем вставить элемент а [k] на найденное место.
С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг.
Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из 10 элементов по возрастанию методом прямого включения
1 - й шаг
13 6 8 11 3 1 5 9 15 7 Рассматриваем часть массива из одного эле-
мента (13). Нужно вставить в нее второй
элемент массива (6) так, чтобы упорядочен-
ность сохранилась. Так как 6 < 13, вставляем
6 на первое место. Отсортированная часть
массива содержит два элемента (6 13).
3 - й шаг
6 8 13 11 3 1 5 9 15 7 Следующий элемент - 11. Он записывается в упорядоченную часть массива на третье место, так как 11 > 8 , но 11 < 13.
5 - шаг
3 6 8 11 13 1 5 9 15 7 По той же причине 1 записываем на первое
6 - шаг
1 3 6 8 11 13 5 9 15 7 Так как 5 > 3, но 5 < 6 то место 5 в упоря-
Доченной части - третье.
7 - шаг
1 3 5 6 8 11 13 9 15 7 Место числа 9 - шестое.
8 - шаг
1 3 5 6 8 9 11 13 15 7 Определяем место для предпоследнего
Элемента 15. Оказывается, что этот эле-
мент массива уже находится на своем месте.
9 - шаг
1 3 5 6 8 9 11 13 15 7 Осталось подобрать подходящее место для
Последнего элемента (7).
1 3 5 6 7 8 9 11 13 15 Массив отсортирован полностью.
Сейчас можно коротко описать фрагмент алгоритма сортировки методом прямого включения:
For k: = 2 To n Do
{ так как начинам сортировку с поиска подходящего места для a, i изменяется от 2 до n }
‘вставить x на подходящее место в a , ..., a[k] ‘
Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента x. Поступим следующим образом: будем просматривать элементы, расположенные левее x (то есть те, которые уже упорядочены), двигаясь к началу массива. Нужно просматривать элементы a[ j ] , j изменяется от k-1 до 1. Такой просмотр должен закончиться при выполнении одного из следующих условий:
· найден элемент a[j] < x, что говорит о необходимости вставки x между a и a[j].
· достигнут левый конец упорядоченной части массива, следовательно, нужно вставить x на первое место.
До тех пор, пока одно из этих условий не выполнится, будем смещать просматриваемые элементы на первую позицию вправо, в результате чего в отсортированной части будет освобождено место под x.
Программа сортировки методом прямого включения:
program n3; { Сортировка по убыванию }
type ar=array of integer;
procedure sorting3(var a:ar);
var i,j,x,k:integer;
for k:=2 to n do
x:=a[k]; j:=k-1;
while (j>0)and(x>=a[j]) do
writeln("Введите исходный массив:");
for i:=1 to n do read(a[i]);
writeln("Отсортированный массив:");
for i:=1 to n do write(a[i]," ");
Необходимые определения и классификация сортировок.
Сортировка. Необходимые определения и классификация сортировок. Сортировки прямого включения и выбора. Их эффективность
Сортировка – это расположение данных в памяти в регулярном виде по их ключам. Так что при обработке данных важно знать информационное поле данных и размещение их в машине. Поэтому различают внутреннюю (сортировка в оперативной памяти) и внешнюю сортировки (сортировка во внешней памяти). Регулярность расположения элементов – это возрастание (убывание) значения ключа от начала к концу в массиве.
Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того чтобы их уменьшить, используют метод сортировки таблицы адресов . Этот метод применяют в таблице адресов ключей . Производят перестановку указателей, т.е. Сам массив не перемещается. При сортировке могут встретиться и одинаковые ключи. В этом случае одинаковые ключи желательно расположить после сортировки в том же порядке, что и в исходном файле. Этот принцип используется для устойчивой сортировки .
Эффективность сортировки можно рассматривать с нескольких критериев:
1) время, затрачиваемое на сортировку;
2) объем оперативной памяти, требуемой для сортировки;
3) время, затраченное программистом на написание программы.
Время, затраченное на сортировку, пропорционально количеству сравнений при выполнении сортировки и количеству перемещений элементов.
Считается, что порядок числа сравнения при сортировке может находиться в пределах от о(nlogn) до о(n 2) , где о(n) - идеальный и недостижимый случай.
Методы сортировки можно классифицировать примерно так:
1) строгие (прямые) методы (их эффективность примерно одинакова):
· прямого включения ;
· прямого выбора ;
· прямого обмена ;
2) улучшенные методы .
В жизни принцип данной сортировки присутствует при раскладывании пасьянсов, уборки квартиры, когда необходимо расположить кучу смешанных вещей в должном порядке и т.д. Очень естественный способ сортировки был применён и к упорядочиванию данных.
Элементы мысленно делятся на уже готовую последовательность a 1 ,...,a i-1 и исходную последовательность. В готовой последовательности элементы располагаются в заданном порядке (по убыванию или по возрастанию). А в исходной последовательности располагаются элементы, которые и нужно отсортировать. При каждом шаге элементы исходной последовательности уменьшаются на единицу, а готовая увеличивается на единицу. Это происходит из-за того, что из исходной последовательности извлекается i- й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место среди элементов готовой последовательности.
Рассмотрим пример сортировки методом прямого включения на последовательности элементов: 10, 3, 11, 8, 2, 15, 44, 9 (табл. 11.1). Необходимо её отсортировать по возрастанию.
Сначала готовая последовательность не имеет элементов. На первом шаге первый элемент исходной последовательности – это 10, становится первым элементом готовой последовательности. Далее второй шаг: элемент 3 из исходной последовательности помещается в готовую. Это происходит так. Если элемент больше 10, то он остаётся на своём месте, а если меньше, то 10 сдвигается на единицу вправо и на её место ставится элемент. Так как 3<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10, то 11 остаётся на месте. Исходная последовательность теперь равна: 8, 2, 15, 44, 9. Последующие шаги производятся аналогичным образом.
Таблица 11.1
Принцип работы сортировки прямым включением
Число шагов в данной сортировке (табл. 11.1) равно числу элементов в сортируемой последовательности, т.е. 8 шагов = 8 элементов.
Существуют два способа реализации данного метода – это без барьера (рис. 11.1) и с барьером (рис. 11.2).
Сортировка - это расположение данных в памяти в регулярном виде по выбранному параметру. Регулярность рассматривают как возрастание (убывание) значения параметра от начала к концу массива данных.
При обработке данных важно знать информационное поле данных и размещение их в машине.
Различают внутреннюю и внешнюю сортировку:
Внутренняя сортировка - сортировка в оперативной памяти;
Внешняя сортировка - сортировка во внешней памяти.
Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того, чтобы их уменьшить, сортировку производят в таблице адресов ключей , то есть делают перестановку указателей, а сам массив не перемещается. Это - метод сортировки таблицы адресов.
При сортировке могут встретиться одинаковые ключи. В этом случае желательно после сортировки расположить одинаковые ключи в том же порядке, что и в исходном файле. Это - устойчивая сортировка .
Мы будем рассматривать только сортировки, не использующие дополнительную оперативную память. Такие сортировки называются «на том же месте» .
Эффективность сортировки можно рассматривать по нескольким критериям:
Время, затрачиваемое на сортировку;
Объем оперативной памяти, требуемой для сортировки;
Время, затраченное программистом на написание программы.
Выделяем первый критерий. Эквивалентом затраченного на сортировку времени можно считать количество сравнений и количество перемещений при выполнении сортировки.
Порядок числа сравнений и перемещений при сортировке лежит в пределах
От О (n log n) до О (n 2);
О (n) - идеальный и недостижимый случай.
Различают следующие методы сортировки:
Строгие (прямые) методы;
Улучшенные методы.
Строгие методы:
Метод прямого включения;
Метод прямого выбора;
Метод прямого обмена.
Эффективность строгих методов примерно одинакова.
Сортировка методом прямого включения
Элементы мысленно делятся на уже готовую последовательность a 1 ,...,a i-1 и исходную последовательность.
При каждом шаге, начиная с i = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.
Суть алгоритма такова:
for i = 2 to n
X = a(i)
Находим место среди а(1)…а(i) для включения х
next i
Есть два алгоритма сортировки методом прямого включения. Первый - без барьера
Алгоритм сортировки методом прямого включения без барьера
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
Эффективность алгоритма прямого включения
Число сравнений ключей Ci при i- м просеивании самое большее равно i-1, самое меньшее - 1; если предположить, что все перестановки из N ключей равновероятны, то среднее число сравнений = i/2. Число же пересылок Mi=Ci+3 (включая барьер). Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки - когда они первоначально расположены в обратном порядке. В некотором смысле сортировка с помощью включения демонстрирует истинно естественное поведение. Ясно, что приведенный алгоритм описывает процесс устойчивой сортировки: порядок элементов с равными ключами при нем остается неизменным.
Количество сравнений в худшем случае, когда массив отсортирован противоположным образом, С max = n(n - 1)/2, т. е. - О (n 2). Количество перестановок M max = C max + 3(n-1), т.е. - О (n 2). Если же массив уже отсортирован, то число сравнений и перестановок минимально: C min = n-1; M min = =3(n-1).
Сортировка с помощью прямого обмена (пузырьковая сортировка)
В данном разделе описан метод, где обмен местами двух элементов представляет собой характернейшую особенность процесса. Изложенный ниже алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы.
Мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу (см. иллюстрацию на рисунке ниже).
C min = n - 1, порядок О(n),
а перемещения вообще отсутствуют
Сравнительный анализ прямых методов сортировок показывает, что обменная "сортировка" в классическом виде представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора. Если же в нее внесены приведенные выше усовершенствования, то для достаточно упорядоченных массивов пузырьковая сортировка даже имеет преимущество.
Такой метод широко известен под именем "пузырьковая сортировка".
Алгоритм метода прямого обмена
for j = n to i step -1
if a(j) < a(j - 1) then
В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не просматривать элементы, а значит проводить сравнения, затрачивая на это время, можно ввести флажок fl , который остается в значении false , если при очередном проходе не будет произведено ни одного обмена. На нижеприведенном алгоритме добавления отмечены жирным шрифтом.
fl = true
if fl = false then return
fl = false
for j = n to i step -1
if a(j) < a(j - 1) then
fl = true
Улучшением пузырькового метода является шейкерная сортировка, где после каждого прохода меняют направление во внутреннем цикле.
Эффективность алгоритма сортировки прямым обменом
Число сравнений C max = n(n-1)/2 , порядок О(n 2).
Число перемещений М max =3C max =3n(n-1)/2, порядок О(n 2).
Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений
Метод: Метод косвенного измерения влажности веществ, основанный на зависимости диэлектрической проницаемости этих веществ от их влажности. Источник: РМГ 75 2004: Государственная система обеспечения еди …
КРОВЬ - КРОВЬ, жидкость, заполняющая артерии, вены и капиляры организма и состоящая из прозрачной бледножелтоват. цвета плаз мы и взвешенных в ней форменных элементов: красных кровяных телец, или эритроцитов, белых, или лейкоцитов, и кровяных бляшек, или … Большая медицинская энциклопедия
Недвижимость - (Real estate) Определение недвижимости, виды недвижимости, аренда и продажа недвижимости Информация о понятии недвижимость, виды недвижимости, аренда и продажа недвижимости, налогообложение и страхование Содержание - это вид имущества,… … Энциклопедия инвестора
У этого термина существуют и другие значения, см. C. См. также: Си (язык программирования) C++ Семантика: мультипарадигмальный: объектно ориентированное, обобщённое, процедурное, метапрограммирование Тип исполнения: компилируемый Появился в … Википедия
ОЦЕНКА СТОИМОСТИ НЕМАТЕРИАЛЬНЫХ АКТИВОВ - (англ. intangible assets appraisal) – определение стоимости объема прав предприятия на определенную группу объектов, не имеющих материально вещественного содержания и приносящих предприятию доход в течение периода, оговоренного национальным… … Финансово-кредитный энциклопедический словарь
ШКОЛА общеобразовательная - уч. воспитат. учреждение, базовый элемент образоват. системы. В этом качестве Ш. предмет исследования разл. дисциплин: пед., ист., демографич., социология, и др. Только в педагогике проблематика Ш. занимает вполне самостоят. место. Изученность… … Российская педагогическая энциклопедия
время - 3.3.4 время tE (time tE): время нагрева начальным пусковым переменным током IА обмотки ротора или статора от температуры, достигаемой в номинальном режиме работы, до допустимой температуры при максимальной температуре окружающей среды. Источник … Словарь-справочник терминов нормативно-технической документации
ГОСТ Р МЭК 60204-1-2007: Безопасность машин. Электрооборудование машин и механизмов. Часть 1. Общие требования - Терминология ГОСТ Р МЭК 60204 1 2007: Безопасность машин. Электрооборудование машин и механизмов. Часть 1. Общие требования оригинал документа: TN систем питания Испытания по методу 1 в соответствии с 18.2.2 могут быть проведены для каждой цепи… … Словарь-справочник терминов нормативно-технической документации
автоматический - 3.3.1 автоматический пробоотборник (automatic sampler): Устройство, используемое для извлечения представительной пробы жидкости, протекающей по трубопроводу. Примечание Автоматический пробоотборник обычно состоит из зонда (щупа), экстрактора… … Словарь-справочник терминов нормативно-технической документации
напряжение - 3.10 напряжение: Отношение растягивающего усилия к площади поперечного сечения звена при его номинальных размерах.
