Структура данных и основные алгоритмы. Спиричева Н.Р.

Алгоритмы и структуры данных для начинающих: сложность алгоритмов

Структура данных и основные алгоритмы. Спиричева Н.Р.

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

Конечно, вы наверняка пользовались списком или стеком, но знаете ли вы, как они работают? Если нет, то вы не можете быть уверены, что принимаете правильные решения относительно того, какой алгоритм использовать.

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

Также смотрите другие материалы этой серии: бинарное дерево, стеки и очереди, динамический массив, связный список, сортировка и множества.

Если не хочется копаться и разбираться, но есть потребность быстро понять основы оценки сложности, идите сюда.

Асимптотический анализ

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

Сколько времени потребуется на обработку массива из десяти элементов? Тысячи? Десяти миллионов? Если алгоритм обрабатывает тысячу элементов за пять миллисекунд, что случится, если мы передадим в него миллион? Будет ли он выполняться пять минут или пять лет? Не стоит ли выяснить это раньше заказчика?

Все решают мелочи!

Порядок роста

Порядок роста описывает то, как сложность алгоритма растет с увеличением размера входных данных. Чаще всего он представлен в виде O-нотации (от нем.

«Ordnung» — порядок) : O(f(x)), где f(x) — формула, выражающая сложность алгоритма. В формуле может присутствовать переменная n, представляющая размер входных данных.

Ниже приводится список наиболее часто встречающихся порядков роста, но он ни в коем случае не полный.

Константный — O(1)

Порядок роста O(1) означает, что вычислительная сложность алгоритма не зависит от размера входных данных. Следует помнить, однако, что единица в формуле не значит, что алгоритм выполняется за одну операцию или требует очень мало времени. Он может потребовать и микросекунду, и год. Важно то, что это время не зависит от входных данных.

public int GetCount(int[] items){ return items.Length;}

Линейный — O(n)

Порядок роста O(n) означает, что сложность алгоритма линейно растет с увеличением входного массива. Если линейный алгоритм обрабатывает один элемент пять миллисекунд, то мы можем ожидать, что тысячу элементов он обработает за пять секунд.

Такие алгоритмы легко узнать по наличию цикла по каждому элементу входного массива.

public long GetSum(int[] items){ long sum = 0; foreach (int i in items) { sum += i; } return sum;}

Логарифмический – O( log n)

Порядок роста O( log n) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива. (Прим. пер.

: в анализе алгоритмов по умолчанию используется логарифм по основанию 2). Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность.

Метод Contains бинарного дерева поиска (binary search tree) также имеет порядок роста O(log n).

Линеарифметический — O(n·log n)

Линеарифметический (или линейно-логарифмический) алгоритм имеет порядок роста O(n·log n). Некоторые алгоритмы типа «разделяй и властвуй» попадают в эту категорию. В следующих частях мы увидим два таких примера — сортировка слиянием и быстрая сортировка.

Квадратичный — O(n 2)

Время работы алгоритма с порядком роста O(n 2) зависит от квадрата размера входного массива. Несмотря на то, что такой ситуации иногда не избежать, квадратичная сложность — повод пересмотреть используемые алгоритмы или структуры данных. Проблема в том, что они плохо масштабируются.

Например, если массив из тысячи элементов потребует
1 000 000 операций, массив из миллиона элементов потребует 1 000 000 000 000 операций. Если одна операция требует миллисекунду для выполнения, квадратичный алгоритм будет обрабатывать миллион элементов 32 года.

Даже если он будет в сто раз быстрее, работа займет 84 дня.

Мы увидим пример алгоритма с квадратичной сложностью, когда будем изучать пузырьковую сортировку.

Наилучший, средний и наихудший случаи

Что мы имеем в виду, когда говорим, что порядок роста сложности алгоритма — O(n)? Это усредненный случай? Или наихудший? А может быть, наилучший?

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

К примеру, мы увидим примеры алгоритмов, которые в среднем имеют порядок роста O(1), но периодически могут становиться O(n) (например, ArrayList.add).

В этом случае мы будем указывать, что алгоритм работает в среднем за константное время, и объяснять случаи, когда сложность возрастает.

Самое важное здесь то, что O(n) означает, что алгоритм потребует не болееn шагов.

Что мы измеряем?

При измерении сложности алгоритмов и структур данных мы обычно говорим о двух вещах: количество операций, требуемых для завершения работы (вычислительная сложность), и объем ресурсов, в частности, памяти, который необходим алгоритму (пространственная сложность).

Алгоритм, который выполняется в десять раз быстрее, но использует в десять раз больше места, может вполне подходить для серверной машины с большим объемом памяти. Но на встроенных системах, где количество памяти ограничено, такой алгоритм использовать нельзя.

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

Операции, количество которых мы будем измерять, включают в себя:

  • сравнения («больше», «меньше», «равно»);
  • присваивания;
  • выделение памяти.

То, какие операции мы учитываем, обычно ясно из контекста.

К примеру, при описании алгоритма поиска элемента в структуре данных мы почти наверняка имеем в виду операции сравнения. Поиск — это преимущественно процесс чтения, так что нет смысла делать присваивания или выделение памяти.

Когда мы говорим о сортировке, мы можем учитывать как сравнения, так и выделения и присваивания. В таких случаях мы будем явно указывать, какие операции мы рассматриваем.

Продолжение следует

На этом мы заканчиваем знакомство с анализом сложности алгоритмов. В следующий раз мы рассмотрим первую структуру данных — связный список.

Перевод статьи «Algorithms and Data Structures»

Источник: https://tproger.ru/translations/algorithms-and-data-structures/

Структуры данных для самых маленьких

Структура данных и основные алгоритмы. Спиричева Н.Р.

James Kyle как-то раз взял и написал пост про структуры данных, добавив их реализацию на JavaScript. А я взял и перевёл.

Дисклеймер: в посте много ascii-графики. Не стоит его читать с мобильного устройства — вас разочарует форматирование текста.

Сегодня мы узнаем всё о структурах данных. «Оооооой как интересно…», да? Да уж, не самая сочная тема на сей день, однако крайне важная. Не для того, чтобы сдавать курсы наподобие CS101, а чтобы лучше разбираться в программировании. Знание структур данных поможет вам:

  • Управлять сложностью своих программ, делая их доступней для понимания.
  • Создавать высокопроизводительные программы, эффективно работающие с памятью.

Я считаю, что первое важнее. Правильная структура данных может кардинально упростить код, устраняя запутанную логику. Второй пункт тоже важен. Когда учитываются производительность или память программы, правильный выбор структуры данных значительно сказывается на работе. Чтобы познакомиться со структурами данных, мы реализуем некоторые из них. Не беспокойтесь, код будет лаконичен. На самом деле, тут больше комментариев, а кода между ними — раз, два и обчёлся.

============================================================================,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'============================================================================

Что такое структуры данных?

По сути, это способы хранить и организовывать данные, чтобы эффективней решать различные задачи. Данные можно представить по-разному. В зависимости от того, что это за данные и что вы собираетесь с ними делать, одно представление подойдёт лучше других. Чтобы понять, почему так происходит, сперва поговорим об алгоритмах.

/*** ===================================================================== ***\ * * * ,—,—. ,—,—. * * ,———-. | | | | | | _____ * * |`———-'| | | | | | | | | ,——. * * | | | | | | | | ,—.

| o o | |`——'| * * | | ,| +-|-+ | | +-|-+ |` | | |_____| | | * * | | ,:==| | |###|======|###| | |====#==#====#=,, | | * * | | || `| +—+ | | +—+ |' ,,=#==#====O=« ,| | * * | | || | | | | | | «=#==#====#=====|| | * * `———-' || | | | | | | |__| `| | * * | | «=| |===« `—,',—` `—,',—` /||\ `——' * ** \_/ \_/ / / \ \ / / \ \ //||\\ |_| |_| **\*** ===================================================================== ***/

Алгоритмы

Алгоритм — такое хитроумное название для последовательности совершаемых действий. Структуры данных реализованы с помощью алгоритмов, алгоритмы — с помощью структур данных. Всё состоит из структур данных и алгоритмов, вплоть до уровня, на котором бегают микроскопические человечки с перфокартами и заставляют компьютер работать.

(Ну да, у Интела в услужении микроскопические люди. Поднимайся, народ!) Любая данная задача реализуется бесконечным количеством способов. Как следствие, для решения распространённых задач изобрели множество различных алгоритмов.

Например, для сортировки неупорядоченного множества элементов существует до смешного большое количество алгоритмов: Сортировка вставками, Сортировка выбором, Сортировка слиянием, Сортировка пузырьком, Cортировка кучи, Быстрая сортировка, Сортировка Шелла, Сортировка Тима, Блочная сортировка, Поразрядная сортировка… Некоторые из них значительно быстрее остальных.

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

Для сравнения производительности алгоритмов используется грубое измерение средней производительности и производительности в худшем случае, для обозначения которых используется термин «О» большое.

/*** ===================================================================== ***\ * a b d * * a b O(N2) d * * O(N!) a b O(N log N) d c * * a b d c * * a b d c O(N) * * a b d c * * a b d c * * a b d c * * ab c O(1) * * e e e e ec d e e e e e e e e * * ba c d * * ba c d f f f f f f f * ** cadf f d f f f f f O(log N) **\*** ===================================================================== ***/

О большое

«О» большое — обозначение способа приблизительной оценки производительности алгоритмов для относительного сравнения.

О большое — заимствованное информатикой математические обозначение, определяющее, как алгоритмы соотносятся с передаваемым им некоторым количеством N данных.

О большое характеризует две основные величины:

Оценка времени выполнения — общее количество операций, которое алгоритм проведёт на данном множестве данных.

Оценка объёма — общее количество памяти, требующееся алгоритму для обработки данного множества данных.

Оценки делаются независимо друг от друга: одни алгоритмы могут производить меньше операций, чем другие, занимая при этом больше памяти. Определив свои требования, вы сможете выбрать соответствующий алгоритм. Вот некоторые распространённые значения О большого: Имя Нотация Что вы скажете, припрись они к вам на вечеринку—————————————————————————-Константная O(1) ОХРЕНЕННО!!Логарифмическая O(log N) КРУТО!Линейная O(N) НОРМАС.Линейно-логарифмическая O(N log N) БЛИИИН…Полиномиальная O(N 2) ОТСТОЙЭкспоненциальная O(2 N) ОТВРАТИТЕЛЬНОФакториальная O(N!) ТВОЮЖМАТЬ Чтобы дать представление, о каких порядках чисел мы говорим, давайте взглянем, что это будут за значения в зависимости от N. N = 5 10 20 30————————————————————————O(1) 1 1 1 1O(log N) 2.3219… 3.3219… 4.3219… 4.9068…O(N) 5 10 20 30O(N log N) 11.609… 33.219… 84.638… 147.204…O(N 2) 25 100 400 900O(2 N) 32 1024 1,048,576 1,073,741,824O(N!) 120 3,628,800 2,432,902,0… 265,252,859,812,191,058,636,308,480,000,000 Как видите, даже при относительно небольших числах можно сделать *дофига* дополнительной работы. Структуры данных позволяют производить 4 основных типа действий: доступ, поиск, вставку и удаление. Замечу, что структуры данных могут быть хороши в одном из действий, но плохи в другом. Доступ Поиск Вставка Удаление———————————————————————— Массив O(1) O(N) O(N) O(N) Связный список O(N) O(N) O(1) O(1)Двоичное дерево поиска O(log N) O(log N) O(log N) O(log N) Или даже… Доступ Поиск Вставка Удаление———————————————————————— Массив ОХРЕНЕННО НОРМАС НОРМАС НОРМАС Связный список НОРМАС НОРМАС ОХРЕНЕННО ОХРЕНЕННОДвоичное дерево поиска КРУТО КРУТО КРУТО КРУТО Кроме того, некоторые действия имеют разную «среднюю» производительность и производительность в «самом худшем случае». Идеальной структуры данных не существует. Вы выбираете самую подходящую, основываясь на данных и на том, как они будут обрабатываться. Чтобы сделать правильный выбор, важно знать различные распространённые структуры данных.

/*** ===================================================================== ***\ * _.-.. * * ,'9 )\)`-.,.—. * * `-.| `. * * \, , \) * * `. )._\ (\ * * |// `-,// * * ]|| //» * ** hjw «» «» **\*** ===================================================================== ***/

Память

Компьютерная память — довольно скучная штука. Это группа упорядоченных слотов, в которых хранится информация. Чтобы получить к ней доступ, вы должны знать её адрес в памяти. Фрагмент памяти можно представить так:

Значения: |1001|0110|1000|0100|0101|1010|0010|0001|1101|1011… Адреса: 0 1 2 3 4 5 6 7 8 9 …

Если вы задумывались, почему в языках программирования отсчёт начинается с 0 — потому, что так работает память. Чтобы прочитать первый фрагмент памяти, вы читаете с 0 до 1, второй — с 1 до 2. Адреса этих фрагментов соответственно равны 0 и 1. Конечно же, в компьютере больше памяти, чем показано в примере, однако её устройство продолжает принцип рассмотренного шаблона. Просторы памяти — как Дикий Запад. Каждая работающая на компьютере программа хранится внутри одной и той же *физической* структуры данных. Использование памяти — сложная задача, и для удобной работы с ней существуют дополнительные уровни абстракции. Абстракции имеют два дополнительных назначения: — Сохраняют данные в памяти таким образом, чтобы с ними было эффективно и/или быстро работать. — Сохраняют данные в памяти так, чтобы их было проще использовать.

/*** ===================================================================== ***\ * * _______________________ * * ()=(_______________________)=() * * * * | | * * | ~ ~~~~~~~~~~~~~ | * * * * * | | * * * | ~ ~~~~~~~~~~~~~ | * * * | | * * | ~ ~~~~~~~~~~~~~ | * * * * | | * * * |_____________________| * * * * ()=(_______________________)=() * ** **\*** ===================================================================== ***/

Списки

Для начала реализуем список, чтобы показать сложности взаимодействия между памятью и структурой данных. Список — представление пронумерованной последовательности значений, где одно и то же значение может присутствовать сколько угодно раз. Начнём с пустого блока памяти, представленного обычным JavaScript-массивом. Также нам понадобится хранить значение длины списка. Заметьте, что мы хотим хранить длину отдельно, поскольку в реальности у «памяти» нет значения length, которое можно было бы взять и прочитать. class List { constructor() { this.memory = []; this.length = 0; } //…} Первым делом нужно получать данные из списка. Обычный список позволяет очень быстро получить доступ к памяти, поскольку вы уже знаете нужный адрес. Сложность операции доступа в список — O(1) — «ОХРЕНЕННО!!» get(address) { return this.memory[address];} У списков есть порядковые номера, поэтому можно вставлять значения в начало, середину и конец. Мы сфокусируемся на добавлении и удалении значений в начало или конец списка. Для этого понадобятся 4 метода:

  • Push — Добавить значение в конец.
  • Pop — Удалить значение из конца.
  • Unshift — Добавить значение в начало.
  • Shift — Удалить значение из начала.

Источник: https://habr.com/p/310794/

Н р спиричева структуры данных лекции 6

Структура данных и основные алгоритмы. Спиричева Н.Р.

Н. Р. Спиричева СТРУКТУРЫ ДАННЫХ

Лекции 6 -7: Основные алгоритмы обработки статических структур Лектор: Спиричева Наталия Рахматулловна

Структуры данных и алгоритмы Целью лекции является приобретение студентами следующих компетенций: ü знать основные алгоритмы сортировок массивов и их характеристики ü знать основные операции логического уровня над статическими структурами данных

Структуры данных и алгоритмы Основные темы лекции: Ø Ø Ø Поиск Сортировка Прямой доступ и хеширование

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

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

Порядком алгоритма называется функция O(N), позволяющая оценить зависимость времени выполнения алгоритма от объема перерабатываемых данных (N — количество элементов в массиве или таблице).

Большинство алгоритмов с точки зрения порядка сводятся к трем основным типам: степенные — O(Na); линейные — O(N); логарифмические — O(loga(N)).

Поиск Последовательный или линейный поиск Простейший метод поиска элемента — последовательный просмотр каждого элемента набора, который продолжается до тех пор, пока не будет найден желаемый элемент. Для последовательного поиска в среднем требуется (N+1)/2 сравнений. Таким образом, порядок алгоритма — линейный — O(N).

Поиск Бинарный поиск Метод бинарного поиска выполняется в заведомо упорядоченной последовательности элементов. Записи в таблицу заносятся в лексикографическом (символьные ключи) или численно (числовые ключи) возрастающем порядке. Для того чтобы найти нужную запись в таблице, в худшем случае требуется log 2(N) сравнений.

Статические структуры данных Сортировка

Операции логического уровня над статическими структурами. Сортировка Классификация алгоритмов сортировки: 1). Стратегия выборки. 2). Стратегия включения. 3). Стратегия распределения. 4). Стратегия слияния.

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

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

Сортировка Методы сортировки разделяют на две категории: сортировка массивов и сортировка файлов. Эти два класса часто называют внутренней и внешней сортировкой, потому что массивы располагаются в оперативной памяти ЭВМ; для этой памяти характерен быстрый произвольный доступ, а файлы хранятся в более медленной, но более вместительной внешней памяти.

Пузырьковая сортировка вставками При такой сортировке входное и выходное множества находятся в одной последовательности, причем выходное — в начальной ее части.

В исходном состоянии можно считать, что первый элемент последовательности уже принадлежит упорядоченному выходному множеству, остальная часть последовательности — неупорядоченное входное. Первый элемент входного множества примыкает к концу выходного множества.

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

Затем выполняется просмотр выходного множества от конца к началу с перестановкой соседних элементов, которые не соответствуют критерию упорядоченности.

Просмотр прекращается, когда прекращаются перестановки. Это приводит к тому, что последний элемент выходного множества «выплывает» на свое место в множестве.

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

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

Изначально готовая последовательность содержит первый элемент массива. Процесс сортировки простыми включениями показан на примере восьми случайно взятых чисел Количество сравнений элементов зависит от исходного порядка элементов массива.

Недостаток метода — большое число пересылок элементов.

Сортировка простым обменом (метод пузырька) Идея этого метода отражена в его названии. Самые легкие элементы массива «всплывают» наверх, самые «тяжелые» — тонут. Алгоритмически это можно реализовать следующим образом.

Будем просматривать весь массив «снизу вверх» и менять стоящие рядом элементы в том случае, если «нижний» элемент меньше, чем «верхний». Таким образом, вытолкнем наверх самый «легкий” элемент всего массива. Теперь повторим всю операцию для оставшихся неотсортированных элементов (т. е. для тех, которые лежат «ниже» первого).

Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности.

Сортировка простым выбором Суть метода: выбирается наименьший элемент массива и меняется местами с первым элементом.

Эти операции повторяются с оставшимися элементами, кроме первого элемента, затем кроме первого и второго элементов массива, пока не останется только один элемент – наименьший.

Этот метод продемонстрирован на восьми элементах: Число сравнений элементов не зависит от исходного порядка элементов массива.

Сортировка упорядоченным двоичным деревом Алгоритм складывается из построения упорядоченного двоичного дерева и последующего обхода.

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

Порядок алгоритма — O(N*log 2 N)), но в конкретных случаях все зависит от упорядоченности исходной последовательности, которая влияет на степень сбалансированности дерева и в конечном счете — на эффективность поиска.

Турнирная сортировка Этот метод сортировки получил свое название из-за сходства с кубковой системой проведения спортивных соревнований: участники соревнований разбиваются на пары, в которых разыгрывается первый тур; из победителей первого тура составляются пары для розыгрыша второго тура и т. д. Алгоритм сортировки состоит из двух этапов. На первом этапе строится дерево, аналогичное схеме розыгрыша кубка.

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

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

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

Основание системы счисления P может быть любым, в частном случае 2 или 10. Для системы счисления с основанием P требуется P групп.

Быстрая сортировка хоара Данный алгоритм относится к распределительным и обеспечивает показатели эффективности O(N*log 2(N)) даже при наихудшем исходном распределении.

Используются два индекса — l и r — с начальными значениями 1 и N соответственно. Ключ K[l] сравнивается с ключом K[r]. Если ключи удовлетворяют критерию упорядоченности, то индекс r уменьшается на 1 и производится следующее сравнение ключей.

Если ключи не удовлетворяют критерию, то записи R[l] и R[r] меняются местами.

Данный алгоритм относится к распределительным и обеспечивает показатели эффективности O(N*log 2(N)) даже при наихудшем исходном распределении. Используются два индекса — l и r — с начальными значениями 1 и N соответственно.

Ключ K[l] сравнивается с ключом K[r]. Если ключи удовлетворяют критерию упорядоченности, то индекс r уменьшается на 1 и производится следующее сравнение ключей.

Если ключи не удовлетворяют критерию, то записи R[l] и R[r] меняются местами.

Сортировка слиянием Алгоритмы сортировки слиянием, как правило, имеют порядок O(N*log 2(N)), но отличаются от других алгоритмов большей сложностью и требуют большого числа пересылок. Алгоритмы слияния применяются в основном, как составная часть внешней сортировки.

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

На первом проходе каждые два соседних одноэлементных множества сливаются в одно двухэлементное упорядоченное множество. На втором проходе двухэлементные множества сливаются в 4 -элементные упорядоченные множества, и т. д.

В конце концов получается одно большое упорядоченное множество.

Сортировка бинарными включениями (модифицированная сортировка простыми включениями) Готовая последовательность, в которую нужно включить новый элемент массива, уже упорядочена.

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

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

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

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

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

Шейкер-сортировка Модифицированный алгоритм сортировки простым обменом. Вопервых, т. к. метод «пузырька» асимметричен, то просмотр и обмены удобно осуществлять поочередно с разных концов.

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

Недостаток: не изменилось число обменов элементов.

Сортировка включениями с убывающим приращением (сортировка Шелла) Некоторое усовершенствование сортировки простыми включениями было предложено Д. Л. Шеллом в 1959 году.

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

Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

Рассмотрим пример, представленный на рисунке. На первом проходе отдельно группируются и сортируются все элементы, отстоящие друг от друга на четыре позиции. Этот процесс называется 4 сортировкой. В примере из восьми элементов каждая группа содержит ровно два элемента.

После этого элементы вновь объединяются в группы с элементами, отстоящими друг от друга на две позиции, и сортируются заново. Этот процесс называется 2 сортировкой. Наконец, на третьем проходе все элементы сортируются обычной сортировкой, или 1 -сортировкой. Приращения не должны быть кратны другу.

Это позволяет избежать явления, где каждый проход сортировки объединяет две цепочки, которые ранее никак не взаимодействовали

Сортировка с помощью дерева Сортировка сводится к разбиению массива на пары и выбору меньшего среди них, последующему разбиению и выбору. Таким образом строим дерево выбора: 44 55 12 42 94 18 06 67 / 44 12 18 06 / 12 06 / 06

На следующем шаге мы поднимаемся по ветви наименьшего элемента, заменяя его на элемент из противоположного узла вышестоящего уровня, или удаляем его, если он крайний. 44 55 12 42 94 18 __ 67 / 44 12 18 __ / 12 __ / __ 44 55 12 42 94 18 67 / 44 12 18 67 / 12 18 / 12 Повторив последний шаг несколько раз , дерево пропадает.

Пирамидальная сортировка Пирамида – двоичное дерево с упорядоченными листьями (корень дерева – наименьший элемент). Пирамиду можно представить в виде массива. Первый элемент пирамиды является наименьшим. Массив, расположенный в виде бинарного дерева

Просеивание – построение новой пирамиды: помещение нового элемента в вершину дерева, далее он перемещается ( «просеивается» ) по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх.

Например, возьмём исходную пирамиду, показанную на рисунке «а» , и расширим эту пирамиду «влево» , добавив элемент h 1=44. Значение 44 сначала меняется местами с 06, затем с 12, и так формируется дерево, показанное на рисунке «б» .

а) пирамида из семи элементов; б) просеивание элемента 44 через пирамиду.

Способ построения пирамиды, предложенный Р. У. Флойдом: пусть дан массив h 1, …hn, тогда элементы hn/2+1…hn уже образуют пирамиду. Эти элементы составляют последовательность, которую можно рассматривать как нижний ряд соответствующего двоичного дерева. Пирамида расширяется влево: на каждом шаге добавляется новый элемент и при помощи просеивания помещается на соответствующее место.

67 X 1. . Xn 06 h 1 / / 42 12 h 2 h 3 / / / 55 94 18 44 h 4 h 5 h 6 h 7 h 1 (наименьшее число) записывается в отсортированный массив, X записывается в h 1 и просеивается. Это повторяется, пока не закончатся свободные элементы.

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

На место элемента из нижнего уровня записывается последний по счету элемент.

Пример пирамидальной сортировки:

Быстрая сортировка (метод хоора) Этот метод разработан К. Хоором в 1962 году. Суть метода заключается в том, чтобы выбрать случайным образом какой-то элемент, просмотреть массив, двигаясь слева направо, пока не будет найден элемент, больший выбранного. Затем просмотреть его справа налево, пока не будет найден элемент, меньший выбранного.

После этого поменять эти элементы местами и продолжить «просмотр с обменом» , пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую – с меньшими элементами, чем выбранный, и правую – с большими элементами. Разделив массив, нужно сделать то же самое с обеими полученными частями, затем с частями этих частей и т. д.

, пока каждая часть не будет содержать только один элемент.

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

ЦИФРОВАЯ РАСПРЕДЕЛЯЮЩАЯ СОРТИРОВКА Применяется для упорядочивания n-ричных чисел. Идея: просматривая записи последовательно, распределяем их на группы с одинаковой последней цифрой. После этого группы снова объединяются в один массив в порядке возрастания последних цифр.

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

На рисунке показано, как осуществляется такая сортировка для трехзначных чисел.

Сортировка последовательных файлов Простое слияние Слияние означает объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент.

Слияние — намного более простая операция, чем сортировка; она используется в качестве вспомогательной в более сложном процессе последовательной сортировки. Метод сортировки простым слиянием состоит в следующем: 1. Последовательность а разбивается на две половины b и с. 2.

Последовательности b и с сливаются при помощи объединения отдельных элементов в упорядоченные пары. 3. Полученной последовательности присваивается имя а, и повторяются шаги 1 и 2; упорядоченные пары сливаются в упорядоченные четверки. 4.

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

В качестве примера рассмотрим последовательность: 44 55 12 42 94 18 06 67 На первом шаге разбиение дает последовательности: 44 55 12 42 94 18 06 67 Слияние отдельных компонент (которые являются упорядоченными последовательностями длины 1) в упорядоченные пары дает: 44 94 / 18 55 / 06 12 / 42 67 Новое разбиение пополам и слияние упорядоченных пар дают: 06 12 44 94 / 18 42 55 67 Третье разбиение и слияние приводят к нужному результату: 06 12 18 42 44 55 67 94

Естественное слияние Исходная последовательность элементов задана в виде файла с, который в конце работы должен содержать результат сортировки. Каждый проход состоит из фазы распределения, которая распределяет упорядоченные подпоследовательности поровну из с в а и b, и фазы слияния, которая сливает упорядоченные подпоследовательности из а и b в с.

Этот процесс показан на рисунке:

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

Многофазная сортировка Этот метод был изобретён Р. Л. Гилстадом. В каждый момент элементы сливаются из нескольких файлов в один. Как только один из входных файлов окажется исчерпанным, он становится выходным файлом для слияния из того файла, который ещё не исчерпан, и из тех, которые до этого были входными.

Рассмотрим пример, изображенный на рисунке. Вначале два входных файла f 1, f 2 содержат соответственно 13 и 8 упорядоченных подпоследовательностей.

На первом «проходе» 8 подпоследовательностей сливаются с f 1 и f 2 в f 3, на втором «проходе» оставшиеся 5 подпоследовательностей сливаются с f 3 и f 1 в f 2 и т. д.

В конце работы в файле f 1 содержится отсортированная последовательность. Достоинство: более эффективен, чем сбалансированная сортировка.

Анализ алгоритмов Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочивание элементов нужно выполнять на том же месте. Таки образом, выбирая метод сортировки, руководствуются критерием эффективности. Удобная мера эффективности получается при подсчете числа необходимых сравнений и (или) пересылок элементов.

Рассмотрим наглядный пример исследования алгоритма на основе сортировки выбором: Пусть нам дан одномерный массив с цифрами 1 2 3 4 5 a 1 a 2 a 3 a 4 a 5 Рассмотрим несколько вариантов сортировок : 1.

Все элементы упорядочены (лучший случай) Сравниваем элементы с первым начиная со второго : А 2>A 1 A 2: =a 2; 12345 шаг 1 действий 4 A 3>a 2 A 3: =a 3; 12345 A 4>a 3 A 4: =a 4; 12345 A 5>a 4 A 5: =a 5; 12345 Итого шаг 1 действий 4.

Сортировка не требуется.

3. Все элементы находятся не на своём месте (худший случай) 5 4 3 2 1 A 2

Статические структуры данных Тема 9: Прямой доступ и хеширование

Сортировка справочных таблиц 1.

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

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

В этом случае мы должны иметь некоторую функцию, обеспечивающую отображение точки из пространства ключей в точку в пространстве записей, т. е. преобразование ключа в адрес записи: r = H(k), где — r адрес записи, k — ключ.

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

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

К функции хеширования в общем случае предъявляются следующие требования: Øона должна обеспечивать равномерное распределение отображений фактических ключей по пространству записей; Øона должна порождать как можно меньше коллизий для данного фактического множества записей; Øона не должна отображать какую-либо связь между значениями ключей в связь между значениями адресов; Øона должна быть простой и быстрой для вычисления.

Простейшей функцией хеширования является деление по модулю числового значения ключа на размер пространства записи. Результат интерпретируется как адрес записи. Функция середины квадрата.

Значение ключа преобразуется в число, это число затем возводится в квадрат, из него выбираются несколько средних цифр и интерпретируются как адрес записи. Функция свертки. Цифровое представление ключа разбивается на части, каждая из которых имеет длину, равную длине требуемого адреса.

Над частями производятся какие-то арифметические или поразрядные логические операции, результат которых интерпретируется как адрес. Функция преобразования системы счисления. Ключ, записанный как число в некоторой системе счисления P, интерпретируется как число в системе счисления Q>P.

Обычно выбирают Q = P+1. Это число переводится из системы Q обратно в систему P, приводится к размеру пространства записей и интерпретируется как адрес.

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

КОНТРОЛЬНЫЕ ВОПРОСЫ 1. Какие наиболее распространенные операции логического уровня над статическими структурами? 2. Перечислите основные стратегии алгоритмов сортировки статических структур? 3. Какие из алгоритмов сортировки подходят под стратегию слияния? 4. Какие из алгоритмов сортировки реализуют под стратегию выборки?

Источник: https://present5.com/n-r-spiricheva-struktury-dannyx-lekcii-6/

Biz-books
Добавить комментарий