Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

В 1959 году Д. Шеллом было предложено усовершенствование сортировки с помощью метода прямого включения. Иллюстрация его сортировки с шагом, равным 4, представлена на рис. 6.5.

 

 

 

Сначала отдельно группируются и в группах сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. В нашем примере 8 элементов, и каждая группа состоит из двух элементов, то есть 1-й и 5-й элементы, 2-й и 6-й, 3-й и 7-й и, наконец, 4-й и 8-й элементы. После четверной сортировки элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на 2 позиции - и вновь сортируются. Это называется двойной сортировкой. И, наконец, на третьем проходе идет обычная или одинарная сортировка.

На первый взгляд можно засомневаться: если необходимо несколько процессов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако, на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок.

Ясно, что такой метод в результате дает упорядоченный массив, и, конечно, сразу же видно, что каждый проход от предыдущих только выигрывает. Также очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу.

Приводимый алгоритм основан на методе прямой вставки без барьера (с условным переходом), и не ориентирован на некую определенную последовательность расстояний, хотя в нем для конкретности заданы шаги 5, 3 и 1.

При использовании метода с барьером каждая из сортировок нуждается в постановке своего собственного барьера, поэтому приходится расширять массив с [0..N] до [-h1..N].

Введем обозначения

h[1..t] - массив размеров шагов

a[1..n] - сортируемый массив

k - шаг сортировки

x - значение вставляемого элемента

 

Алгоритм сортировки Шелла:

 

const t = 3

     h(1) = 7

     h(2) = 3

     h(3) = 1

for m = 1 to t

k = h(m)

for i = 1 + k to n

x = a(i)

for j = i - k to 1 step -k

if x < a(j) then

              a( j+k) = a(j)

             else goto L

 endif

next j

L: a(j+k) = x

 next i

next m

return

 

Не доказано, какие расстояния дают наилучший результат, но они не должны быть множителями один другого. Д. Кнут предлагает такую последовательность шагов h (в обратном порядке): 1, 3, 7, 15, 31, …  . То есть:  h_m = 2 h_{m -1} + 1, а количество шагов t = ( log ₂ n ) - 1.

При такой организации алгоритма его эффективность имеет порядок O ( n ^1,2 ).

 

Контрольные вопросы

1. Что такое сортировка?

2. Назовите основные методы сортировки.

3. Какие методы сортировки относятся к строгим?

4. Какие методы сортировки относятся к улучшенным?

5. Какая сортировка называется устойчивой?

6. В чем состоит суть метода прямого включения?

7. В чем состоит суть метода прямого выбора?

8. В чем состоит суть метода прямого обмена?

9. Назовите разницу между этими тремя методами.

10. Какой метод сортировки является самым эффективным?

11. К какому из основных методов относится метод Шелла?

 

 

ПРЕОБРАЗОВАНИЕ КЛЮЧЕЙ (РАССТАНОВКА)

 

Метод расстановок (хеширования) направлен на быстрое решение задачи о местоположении элемента в структуре данных. В методе расстановок данные организованы как обычный массив. Поэтому Н - отображение, преобразующее ключи в индексы массива, отсюда и появилось название «преобразование ключей», обычно даваемое этому методу. Следует заметить, что нет никакой нужды обращаться к каким-либо процедурам динамического размещения, ведь массив — это один из основных, статических объектов. Метод преобразования ключей часто используется для таких задач, где можно с успехом воспользоваться и деревьями.

Основная трудность, связанная с преобразованием ключей, заключается в том, что множество возможных значений значительно шире множества допустимых адресов памяти (индексов массива). Возьмем в качестве примера имена, включающие до 16 букв и представляющие собой ключи, идентифицирующие отдельные индивиды из множества в тысячу персон. Следовательно, мы имеем дело с 26¹⁶ возможными ключами, которые нужно отобразить в 10³ возмож­ных индексов. Поэтому функция Н будет функцией класса «много значений в одно значение». Если дан некоторый ключ k, то первый шаг операции поиска — вычисление связанного с ним индекса h = H(k), а второй (совершенно необходимый) — проверка, действительно ли h идентифицирует в массиве (таблице) Т элемент с ключом k.

 

7.1. Выбор функции преобразования

 

Само собой разумеется, что любая хорошая функция преобразования должна как можно равномернее распределять ключи по всему диапазону значений индекса. Если это требование удовлетворяется, то других ограничений уже нет, и даже хорошо, если преобразование будет выглядеть как совершенно слу­чайное. Такая особенность объясняет несколько ненаучное название этого метода — «перемалывание» (хеширование), т. е. дробление аргумента, превращение его в какое-то «месиво». Функция же Н будет называться «функцией расстановки». Ясно, что Н должно вычисляться достаточно эффективно, т. е. состоять из очень небольшого числа основных ариф­метических операций.

Представим себе, что есть функция преобразования ORD(k), обозначающая порядковый номер ключа k в множестве всех возможных ключей. Кроме того, будем считать, что индекс массива i лежит в диапазоне 0 ... N — 1, где N — размер массива. В этом случае ясно, что нужно выбрать следующую функцию:

 

H(k) = ORD(k) MOD N

 

Для нее характерно равномерное отображение зна­чений ключа на весь диапазон изменения индексов, поэтому ее кладут в основу большинства преобразо­ваний ключей. Кроме того, при N, равном степени двух, эта функция эффективно вычисляется. Однако если ключ представляет собой последовательность букв, то именно от такой функции и следует отказаться. Дело в том, что в этом случае допущение о равновероятности всех ключей ошибочно. В резуль­тате слова, отличающиеся только несколькими сим­волами, с большой вероятностью будут отображаться в один и тот же индекс, что приведет к очень неравномерному распределению. Поэтому на практике ре­комендуется в качестве N брать простое число. Следствием такого выбора будет необходимость использования полной операции деления, которую уже нельзя заменить выделением нескольких двоичных цифр.

 

Алгоритм

 

Если обнаруживается, что строка таблицы, соответствующая заданному ключу, не содержит желаемого элемента, то, значит, произошел конфликт, т. е. два элемента имеют такие ключи, которые отобра­жаются в один и тот же индекс. В этой ситуации нужна вторая попытка с индексом, вполне опреде­ленным образом получаемым из того же заданного ключа. Существует несколько методов формирования вторичного индекса. Очевидный прием — связывать вместе все строки с идентичным первичным индексом H(k). Превращая их в связанный список. Такой прием называется прямым связыванием (direct chaining). Элементы получающегося списка могут либо поме­щаться в основную таблицу, либо нет; в этом случае память, где они размещаются, обычно называется областью переполнения. Недостаток такого приема в том, что нужно следить за такими вторичными списками и в каждой строке отводить место для ссылки (или индекса) на соответствующий список конфликтующих элементов.

Другой прием разрешения конфликтов состоит в том, что мы совсем отказываемся от ссылок и вместо этого просматриваем другие строки той же таб­лицы — до тех пор, пока не обнаружим желаемый элемент или же пустую строку. В последнем случае мы считаем, что указанного ключа в таблице нет. Такой прием называется открытой адресацией. Естественно, что во второй попытке последователь­ность индексов должна быть всегда одной и той же для любого заданного ключа. В этом случае алгоритм просмотра строится по такой схеме:

 

h = H(k)

i = 0

repeat

if T(h) = k 

then элемент найден

else if T(h) = free

then элемента в таблице нет

else {конфликт}

i := i + 1

h := H(k) + G(i)

endif

endif

until либо найден, либо нет в таблице (либо она полна)

 

Предлагались самые разные функции G(i) для разрешения конфликтов. Приведенный в работе Морриса (1968) обзор стимулировал активную деятельность в этом направлении. Самый простой прием — посмотреть следующую строку таблицы (будем считать ее круговой), и так до тех пор, пока либо будет найден элемент с указанным клю­чом, либо встретится пустая строка. Следовательно, в этом случае G(i)==i, а индексы h_i, употребляемые при последующих попытках, таковы:

 

h₀ := H(k)

h_i := (h_i + i) MOD N,    i = 1 … N - 1

 

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

 

h₀ := H(k)

h_i := (h_i + i²) MOD N,    i > 0

 

Если воспользоваться рекуррентными соотношениями для h_i = i² и d_i = 2i + l при h₀ = 0 и d₀ = l, то при вычислении очередного индекса можно обойтись без операции возведения в квадрат.

 

h_i+1 = h_i + d_i

d_i+1 = d_i + 2 (i > 0)

 

Такой прием называется квадратичными пробами, существенно, что он позволяет избежать группирова­ния, присущего линейным пробам, не приводя прак­тически к дополнительным вычислениям. Небольшой же его недостаток заключается в том, что при поиске пробуются не все строки таблицы, т. е. при включе­нии элемента может не найтись свободного места, хотя на самом деле оно есть. Если размер N — про­стое число, то при квадратичных пробах просматри­вается по крайней мере половина таблицы. Такое утверждение можно вывести из следующих рассуж­дений. Если i-я и j-я пробы приводят к одной и той же строке таблицы, то справедливо равенство

 

i² MOD N = j² MOD N

 

или

 

( i² – j² ) = 0 ( MOD N )

 

Разлагая разность на два множителя, получаем

 

( i + j )( i - j ) = 0 ( MOD N )

 

Поскольку i ¹ j, то либо i, либо j должны быть больше N/2, чтобы было справедливо равенство i + j = cN, где с — некоторое целое число. На практике упомянутый недостаток не столь существен, так как N/2 вторичных попыток при разрешении конфликтов встречаются очень редко, главным образом в тех случаях, когда таблица почти заполнена.

 

 

Контрольные вопросы

 

1. Для чего предназначен метод расстановок ?

2. От чего зависит положение элемента в массива в методе расстановок ?

3. Какую функцию возможно использовать в качестве хэш-функции:

4. Что называется конфликтом ?

5. Какой из методов является методом разрешения конфликтов.

6. Какой из методов разрешения конфликтов позволяет более равномерно распределить элементы по массиву.

7. Почему невозможно применять в качестве H(k) функцию Trunc(sqrt(k⁵- i*tan(k))) MOD N ?

 

 

 

 

часть 2.
практикум по сруктурам и алгоритмам обработки данных в эвм