рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Еще одна модификация пузырьковой сортировки носит название

Реферат Курсовая Конспект

Выберите учебное заведение

Еще одна модификация пузырьковой сортировки носит название

Еще одна модификация пузырьковой сортировки носит название - раздел Образование, СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Шейкер-Сортировки. Суть Ее Состоит В Том, Что Направления Пр...

шейкер-сортировки. Суть ее состоит в том, что направления прос-

мотров чередуются: за просмотром от начала к концу следует прос-

мотр от конца к началу входного множества. При просмотре в прямом

направлении запись с самым большим ключом ставится на свое место

в последовательности, при просмотре в обратном направлении - за-

пись с самым маленьким. Этот алгоритм весьма эффективен для задач

восстановления упорядоченности, когда исходная последовательность

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

нениям. Упорядоченность в последовательности с одиночным измене-

нием будет гарантированно восстановлена всего за два прохода.

СОРТИРОВКА ШЕЛЛА. Это еще одна модификация пузырьковой сор-

тировки. Здесь выполняется сравнение ключей, отстоящих один от

другого на некотором расстоянии d. Исходный размер d обычно выби-

рается соизмеримым с половиной общего размера сортируемой после-

довательности. Выполняется пузырьковая сортировка с интервалом

сравнения d. Затем величина d уменьшается вдвое и вновь выполня-

ется пузырьковая сортировка, далее d уменьшается еще вдвое и т.д.

Последняя пузырьковая сортировка выполняется при d=1. Качествен-

ный порядок сортировки Шелла остается O(N^2), среднее же число

сравнений, определенное эмпирическим путем - log2(N)^2*N. Ускоре-

ние достигается за счет того, что выявленные "не на месте" эле-

менты при d>1, быстрее "всплывают" на свои места.

Пример 3.10 иллюстрирует сортировку Шелла.

{===== Программный пример 3.10 =====}

Procedure Sort( var a : seq);

Var d, i, t : integer;

k : boolean; { признак перестановки }

begin d:=N div 2; { начальное значение интервала }

while d>0 do begin { цикл с уменьшением интервала до 1 }

k:=true; { пузырьковая сортировка с интервалом d }

while k do { цикл, пока есть перестановки }

begin k:=false; i:=1;

for i:=1 to N-d do {сравнение эл-тов на интервале d}

begin if a[i]>a[i+d] then

begin t:=a[i]; a[i]:=a[i+d]; a[i+d]:=t; {перестановка}

k:=true; { признак перестановки }

end; { if ... } end; { for ... } end; { while k }

d:=d div 2; { уменьшение интервала }

end; { while d>0 } end;

Результаты трассировки программного примера 3.10 представле-

ны в таблице 3.7.

Таблица 3.7

┌─────────┬───┬─────────────────────────────────────────────────┐

│ шаг │ d │ содержимое массива a │

├─────────┼───┼─────────────────────────────────────────────────┤

│исходный │ │ 76 22 4 17 13 49 4 18 32 40 96 57 77 20 1 52 │

│ 1 │ 8 │ 32 22 4 17 13 20 1 18 76 40 96 57 77 49 4 52 │

│ 2 │ 8 │ 32 22 4 17 13 20 1 18 76 40 96 57 77 49 4 52 │

│ 3 │ 4 │ 13 20 1 17 32 22 4 18 76 40 4 52 77 49 96 57 │

│ 4 │ 4 │ 13 20 1 17 32 22 4 18 76 40 4 52 77 49 96 57 │

│ 5 │ 2 │ 1 17 13 20 4 18 32 22 4 40 76 49 77 52 96 57 │

│ 6 │ 2 │ 1 17 4 18 13 20 4 22 32 40 76 49 77 52 96 57 │

│ 7 │ 2 │ 1 17 4 18 4 20 13 22 32 40 76 49 77 52 96 57 │

│ 8 │ 2 │ 1 17 4 18 4 20 13 22 32 40 76 49 77 52 96 57 │

│ 9 │ 1 │ 1 4 17 4 18 13 20 22 32 40 49 76 52 77 57 96 │

│ 10 │ 1 │ 1 4 4 17 13 18 20 22 32 40 49 52 76 57 77 96 │

│ 11 │ 1 │ 1 4 4 13 17 18 20 22 32 40 49 52 57 76 77 96 │

│ 12 │ 1 │ 1 4 4 13 17 18 20 22 32 40 49 52 57 76 77 96 │

│результат│ │ 1 4 4 13 17 18 20 22 32 40 49 52 57 76 77 96 │

└─────────┴───┴─────────────────────────────────────────────────┘

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

Массивы Логическая структура фиксированным набором элементов... Операции... Важнейшая операция физического уровня над массивом доступ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Еще одна модификация пузырьковой сортировки носит название

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Статические структуры относятся к разряду непримитивных структур, которые, фактически, представляют собой структурирован- ное множество примитивных, базовых, структур. Например, в

Векторы
ЛОГИЧЕСКАЯ СТРУКТУРА. Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа ти- па. Каждый элемент вектора имеет уникальный в рамках

Логическая структура
Массив - такая структура данных, которая характеризуется: - фиксированным набором элементов одного и того же типа; - каждый элемент имеет уникальный набор значений индексов;

Физическая структура
Физическая структура - это размещение элементов массива в памяти ЭВМ. Для случая двумерного массива, состоящего из (k1-n1+1) строк и (k2-n2+1) столбцов физическая структура предс-

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

Специальные массивы
На практике встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших раз

МАССИВЫ С МАТЕМАТИЧЕСКИМ ОПИСАНИЕМ МЕСТОПОЛОЖЕНИЯ НЕФОНОВЫХ
ЭЛЕМЕНТОВ. К данному типу массивов относятся массивы, у которых местоположения элементов со значениями отличными от фонового, мо- гут быть математически описаны,

ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ ПОСЛЕДОВАТЕЛЬНОГО
РАЗМЕЩЕНИЯ. Один из основных способов хранения подобных разрежен- ных матриц заключается в запоминании ненулевых элементов в одно- мерном массиве и идентификации

ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ СВЯЗАННЫХ СТРУКТУР.
Методы последовательного размещения для представления разреженных матриц обычно позволяют быстрее выполнять операции над матрицами и более эффективно использовать память, чем мето

Множества
ЛОГИЧЕСКАЯ СТРУКТУРА. Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все зн

Числовые множества
Стандартный числовой тип, который может быть базовым для формирования множества - тип byte. Множество хранится в памяти как показано в таблице 3.3. Таблица 3.3 &

Множество из элементов перечислимого типа
Множество, базовым типом которого есть перечислимый тип, хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти занимает место, которое зависит

Множество от интервального типа
Множество, базовым типом которого есть интервальный тип, хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти занимает место, которое зависит

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

Таблицы
Когда речь шла о записях, было отмечено, что полями записи могут быть интегрированные структуры данных - векторы, массивы, другие записи. Аналогично и элементами векторов и массив

Структурами. Поиск
В этом и следующих разделах представлен ряд алгоритмов поис- ка данных и сортировок, выполняемых на статических структурах данных, так как это характерные операции логического уро

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

Бинарный поиск
Другим относительно простым методом доступа к элементу явля- ется метод бинарного (дихотомического, двоичного) поиска, который выполняется в заведомо упорядоченной последовательно

Структурами. Сортировка
Для самого общего случая сформулируем задачу сортировки та- ким образом: имеется некоторое неупорядоченное входное множество ключей и должны получить выходное множество тех же клю

Сортировки выборкой
СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Данный метод реализует практи- чески "дословно" сформулированную выше стратегию выборки. Порядок алгоритма простой выборки

Сортировки включением
СОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ. Этот метод - "дословная" реа- лизации стратегии включения. Порядок алгоритма сортировки просты- ми вставками - O(N^2), ес

Сортировки распределением.
ПОРАЗРЯДНАЯ ЦИФРОВАЯ СОРТИРОВКА.Алгоритм требует представ- ления ключей сортируемой последовательности в виде чисел в неко- торой системе счисления P. Число прохо

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

Таблицы со справочниками
Одним из способов устранения этого недостатка является метод справочников. Основная таблица содержит записи в произвольном по- рядке. В дополнение к основной строится справочная и

Хешированные таблицы и функции хеширования
Как отмечалось выше, в каждой реальной таблице фактическое множество ключей является лишь небольшим подмножеством множества всех теоретически возможных ключей. Поскольку память яв