Как называется сортировка, происходящая в оперативной памяти?

Обновлено: 21.11.2024

Внешняя сортировка — это сортировка файла на диске. Внутренняя сортировка относится к сортировке массива данных, который находится в оперативной памяти. Основная задача внешней сортировки — свести к минимуму доступ к диску, поскольку чтение блока диска занимает примерно в миллион раз больше времени, чем доступ к элементу в ОЗУ. Сортировка во внешней памяти обычно требуется, когда данные настолько велики, что не помещаются в основную память, например, огромные базы данных, файловые системы, графические приложения, в которых объемные 3D-модели, приложения для распознавания образов и машинного обучения и т. д.

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

Диски с большой емкостью часто разрабатываются таким образом, чтобы максимальная производительность достигалась при последовательном доступе к блокам. Большинство методов внешней сортировки используют следующую общую стратегию. Сделайте первый проход по сортируемому файлу, разбив его на блоки размером с память и отсортируйте эти блоки. Затем объедините отсортированные блоки вместе, при необходимости сделав несколько проходов по файлу, последовательно создавая отсортированные блоки большего размера, пока не будет отсортирован весь файл. Этот подход называется сортировкой слиянием во внешней памяти и используется с 1950-х годов. Обратите внимание, что этот метод не использует тот факт, что ключи являются целыми числами. По крайней мере, мы могли бы отсортировать блоки во внутренней памяти, используя сортировку по основанию, чтобы сделать эту реализацию быстрее (поскольку в этом назначении ключами являются целые числа). Вот еще материал по алгоритмам внешней памяти для сортировки от Джеффа Эриксона. (1.1.1 B-деревья — вариант деревьев ab) и от Питера Сандерса. Вы также можете посмотреть главу "Методы сортировки специального назначения" в книге Роберта Седжвика "Алгоритмы в C++"/"Алгоритмы в Java"

В этом задании вы будете сортировать файл с записями фиксированного размера, хранящимися в файле на диске, используя заданный объем основной памяти. Обратите внимание, что когда вы работаете с массивными наборами данных, вам нужно позаботиться о том, как работает ваш диск. Хорошей идеей является чтение фрагментов данных с диска за раз, а не случайный доступ к диску. Входные данные для вашего кода будут исчисляться гигабайтами, поэтому вы должны убедиться, что ваша программа может обрабатывать данные размером более 4 ГБ. Файлы, на которых я буду запускать программу, будут огромными. Тестовая машина будет иметь два процессора, поэтому, если вам нужно больше мощности процессора, вам следует подумать об использовании потоков posix.

Где получить помощь?

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

Что реализовать?

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

Требования к пространству: Ваша программа не должна использовать более чем в два раза больше места, чем размер входного файла в любой момент времени. Например, если размер входного файла составляет 100 ГБ, код не может создавать временные файлы размером 300 ГБ. Максимальный объем дискового пространства, который может использовать код, составляет 200 ГБ в любой момент времени. Вы можете уничтожить входной файл при создании выходного файла, если это вам поможет.

Оценка

Я должен иметь возможность запускать его на Linux (Redhat) + двухпроцессорные системы Intel Xeon (с включенной гиперпоточностью) (на случай, если вы решите использовать что-то низкоуровневое в коде для повышения скорости). Поскольку в системе более 1 процессора (на самом деле 4 с включенной гиперпоточностью), при желании вы также можете использовать потоки posix для сортировки большего количества данных внутренней памяти с помощью потоков. Диск, на котором будет тестироваться ваша программа, будет состоять из 4 дисков Western Digital 74, 10000 об/мин, которые параллельно эмулируются, чтобы вести себя как 1 диск (с использованием RAID 0 с картами 3ware). Таким образом, последовательный доступ к этому диску невероятно быстр.

Убедитесь, что ваша программа не занимает больше памяти, чем разрешено. Вы можете отслеживать это с помощью команды «top» в Linux (или с помощью диспетчера задач Windows), и вы должны помнить об этом при разработке своего алгоритма и кода.Если ваш код не сортируется правильно, вы можете получить ноль во всей домашней работе, даже если вы очень быстры и у вас есть хорошая документация. Так что правильность должна быть вашим главным приоритетом. Убедитесь, что вы хорошо документируете свой код и алгоритм. Ожидается, что документация по алгоритму будет в формате HTML и размещена на вашей веб-странице с домашним заданием. В конце я свяжу все домашние задания класса на этой странице.

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

Что сдавать и когда?

Заархивируйте все файлы в один файл. (Нет файлов данных в файле tar). Сделайте домашнюю страницу для домашней работы, где у вас будет документация в HTML, загружаемый код (tar-файл, gzip/bzipped/zip). Опишите свой алгоритм на домашней странице домашнего задания. Когда закончите, пришлите мне ссылку на домашнюю страницу домашнего задания.

Ваш tar-файл должен содержать make-файл для создания исполняемого файла, который мне нужно запустить. У него должен быть файл README, который говорит мне, как запускать код в моем входном файле. Например, если мой входной файл - "input.dat" с 5000 0000 записей, каждая запись имеет размер 100 байт, размер ключа - 8 байт, и я хочу, чтобы он отсортировался в порядке возрастания, и максимальный объем памяти, который может ваш код использовать в любой момент времени во время запуска составляет 32 МБ, я должен иметь возможность запускать его вот так

(здесь 1 означает порядок возрастания). Я объявлю в классе способ подачи. Все, что вам нужно будет отправить, это файл project.tar, который должен состоять из make-файла, который должен скомпилировать вашу программу extsort и вашу документацию с использованием doxygen. Документация doxygen должна находиться в каталоге doc/.

Крайний срок подачи домашнего задания II – 10:00 25 апреля.

Небольшой FAQ?

  1. Я хочу сделать домашнее задание, что мне нужно сделать?
    Сначала вам нужно внимательно прочитать эту веб-страницу. Затем отправьте ТА электронное письмо с вашим идентификатором (и идентификатором вашего партнера). Не забудьте посетить чтение в эту среду.
  2. Можем ли мы делать домашнее задание в группах?
    Да! Но размер группы не может превышать 2 человек. Если вы хотите сделать это в группе, отправьте мне электронное письмо с именем и идентификаторами вас и вашего партнера.
  3. Можно ли использовать do it в Windows?
    Да! Но только до тех пор, пока ваш код компилируется в Linux без проблем. Вы можете использовать cygwin в Windows, чтобы убедиться, что ваш код совместим с Linux. Желательно, чтобы этот проект выполнялся в системе Unix/Linux.
  4. Какие языки программирования разрешены?
    (C/C++/Java/Python)! Пока я могу использовать приведенные выше команды для запуска вашего кода на моей машине. Если вы хотите, чтобы я использовал другой язык для реализации проекта, пришлите мне письмо, и я добавлю его в список. Помните, что критерием оценки будет скорость (поэтому вам действительно следует воздержаться от сканирования таких языков, как Java и Python, для этого проекта).
  5. Могу ли я выводить сжатые данные?
    Нет. Входные данные не сжаты, а выходные данные должны быть просто перестановкой входных данных.
  6. Можем ли мы использовать ассемблер?
    Да, но это немного удивительно, если вам нужно. Мы хотим, чтобы вы хорошо разбирались в алгоритмах, а не в компиляторах. :)
  7. Может ли результат сортировки уничтожить (повторно использовать) входной файл сортировки?
    Да. Сортировка должна создать новый выходной файл и выделить для него место. Но он может удалить старый файл и освободить место, если это необходимо для выполнения задачи.

Небольшой полезный код

Нет гарантии, что следующий код не содержит ошибок! Дайте мне знать, если вы обнаружите какие-либо проблемы или ошибки в нем. Все вопросы по заданию по программированию нужно уточнять у меня после занятий либо в понедельник, либо в среду. Специально пока не проверял ChkSort, сделаю, как время будет. Тем временем, если вы найдете ошибку, дайте мне знать. Исходный код был получен от Microsoft Research для следующего кода.

Теперь мы рассмотрим проблему сортировки коллекций записей, слишком больших для размещения в основной памяти. Поскольку записи должны находиться в периферийной или внешней памяти, такие методы сортировки называются внешними сортировками. Это отличается от внутренних сортировок, которые предполагают, что сортируемые записи хранятся в основной памяти. Сортировка больших коллекций записей занимает центральное место во многих приложениях, таких как обработка платежных ведомостей и других крупных бизнес-баз данных. Как следствие, было разработано множество внешних алгоритмов сортировки. Несколько лет назад разработчики алгоритмов сортировки стремились оптимизировать использование конкретных аппаратных конфигураций, таких как несколько ленточных или дисковых накопителей. Большая часть вычислений сегодня выполняется на персональных компьютерах и рабочих станциях низкого уровня с относительно мощными процессорами, но только с одним или максимум двумя дисковыми накопителями.Представленные здесь методы ориентированы на оптимизацию обработки на одном диске. Этот подход позволяет нам охватить наиболее важные вопросы внешней сортировки, пропуская многие менее важные детали, зависящие от машин.

Если набор записей слишком велик и не помещается в основную память , единственный практичный способ отсортировать его — прочитать некоторые записи с диска, выполнить некоторую перестановку, а затем записать их обратно на диск. Этот процесс повторяется до тех пор, пока файл не будет отсортирован, причем каждая запись может быть прочитана несколько раз. Учитывая высокую стоимость дискового ввода-вывода, неудивительно, что основная цель внешнего алгоритма сортировки — свести к минимуму количество операций чтения или записи информации на диск. Определенный объем дополнительной обработки ЦП можно с выгодой обменять на сокращение доступа к диску.

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

Напоминаем, что сектор — это основная единица ввода-вывода. Другими словами, все операции чтения и записи диска выполняются для одного или нескольких полных секторов. Размер сектора обычно равен степени двойки в диапазоне от 512 до 16 КБ, в зависимости от операционной системы, размера и скорости диска. Размер блока, используемый для внешних алгоритмов сортировки, должен быть равен или кратен размеру сектора.

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

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

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

Второе требование заключается в том, чтобы головка ввода-вывода дисковода оставалась над файлом на протяжении всей последовательной обработки. Этого не произойдет, если будет какая-либо конкуренция за головку ввода-вывода. Например, на многопользовательском компьютере с разделением времени процесс сортировки может конкурировать за головку ввода-вывода с процессами других пользователей. Даже когда процесс сортировки полностью контролируется головкой ввода-вывода, все равно существует вероятность того, что последовательная обработка будет неэффективной. Представьте себе ситуацию, когда вся обработка выполняется на одном диске с типичным расположением одного банка головок чтения/записи, которые перемещаются вместе по стеку пластин. Если процесс сортировки включает в себя чтение из входного файла, чередующееся с записью в выходной файл, то головка ввода-вывода будет постоянно искать между входным и выходным файлами. Точно так же, если два входных файла обрабатываются одновременно (например, во время процесса слияния), то головка ввода-вывода будет постоянно искать между этими двумя файлами.

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

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

После сортировки индексного файла можно изменить порядок записей в исходном файле базы данных. Обычно этого не делают по двум причинам. Во-первых, чтение записей в отсортированном порядке из файла записей требует произвольного доступа к каждой записи. Это может занять значительное время и имеет значение только в том случае, если необходимо просмотреть или обработать всю коллекцию записей в отсортированном порядке (в отличие от поиска выбранных записей). Во-вторых, системы баз данных обычно позволяют выполнять поиск по нескольким ключам. Например, сегодняшняя обработка может быть выполнена в порядке идентификационных номеров. Завтра начальнику может понадобиться информация, отсортированная по зарплате. Таким образом, для полной записи может не быть единого «отсортированного» порядка. Вместо этого часто поддерживается несколько индексных файлов, по одному для каждого ключа сортировки. Эти идеи более подробно рассматриваются в разделе «Индексирование глав».

14. 6.1.1. Простые подходы к внешней сортировке¶

Если ваша операционная система поддерживает виртуальную память, простейшая «внешняя» сортировка – это чтение всего файла в виртуальную память и запуск внутреннего метода сортировки, например быстрой сортировки. Такой подход позволяет диспетчеру виртуальной памяти использовать свой обычный механизм пула буферов для управления доступом к диску. К сожалению, это не всегда может быть жизнеспособным вариантом. Одним из потенциальных недостатков является то, что размер виртуальной памяти обычно ограничен чем-то намного меньшим, чем доступное дисковое пространство. Таким образом, ваш входной файл может не поместиться в виртуальную память. Ограничение виртуальной памяти можно преодолеть, адаптировав метод внутренней сортировки для использования собственного пула буферов.

Более общая проблема с адаптацией алгоритма внутренней сортировки к внешней сортировке заключается в том, что она вряд ли будет столь же эффективной, как разработка нового алгоритма с конкретной целью минимизации дисковых операций ввода-вывода. Рассмотрим простую адаптацию Quicksort для использования пула буферов. Быстрая сортировка начинается с обработки всего массива записей, при этом на первом этапе раздела индексы перемещаются внутрь с двух концов. Это можно эффективно реализовать с помощью пула буферов. Однако следующим шагом является обработка каждого из подмассивов, за которой следует обработка под-подмассивов и так далее. По мере того, как подмассивы становятся меньше, обработка быстро приближается к произвольному доступу к диску. Даже при максимальном использовании буферного пула Quicksort по-прежнему должен читать и записывать каждую запись в среднем \(\log n\) раз. Мы можем сделать намного лучше. Наконец, даже если диспетчер виртуальной памяти может обеспечить хорошую производительность при использовании стандартной быстрой сортировки, это будет происходить за счет использования большого количества рабочей памяти системы, что будет означать, что система не сможет использовать это пространство для другой работы. Более совершенные методы могут сэкономить время и при этом использовать меньше памяти.

Наш подход к внешней сортировке основан на алгоритме Mergesort. Простейшая форма внешней сортировки слиянием выполняет серию последовательных проходов по записям, объединяя все более и более крупные подсписки на каждом проходе. Первый проход объединяет подсписки размера 1 с подсписками размера 2; второй проход объединяет подсписки размера 2 в подсписки размера 4; и так далее. Отсортированный подсписок называется run . Таким образом, каждый проход объединяет пары прогонов для формирования более длинных прогонов. Каждый проход копирует содержимое файла в другой файл. Вот набросок алгоритма.

Нажмите здесь, чтобы просмотреть слайды презентации.

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

  • Вычислительная сложность (наихудшее, среднее и наилучшее поведение) сравнения элементов с точки зрения размера списка (n).Для типичных алгоритмов сортировки хорошим поведением является O(n log n), а плохим — O( n 2 ).
  • Вычислительная сложность свопов (для алгоритмов "на месте").
  • Использование памяти (и использование других ресурсов компьютера). В частности, некоторые алгоритмы сортировки «на месте». Это означает, что им требуется только O(1) или O(log n) памяти помимо сортируемых элементов, и им не нужно создавать вспомогательные места для временного хранения данных, как в других алгоритмах сортировки.
  • Рекурсия. Некоторые алгоритмы являются либо рекурсивными, либо нерекурсивными.
  • Стабильность. Стабильные алгоритмы сортировки поддерживают относительный порядок записей с одинаковыми ключами (т. е. значениями).
  • Независимо от того, являются ли они сравнительными сортировками. При сортировке сравнением данные проверяются только путем сравнения двух элементов с помощью оператора сравнения.
  • Общие методы: вставка, обмен, выбор, слияние и т. д.
  • Адаптируемость. Влияет ли предварительная сортировка входных данных на время выполнения. Известно, что алгоритмы, учитывающие это, являются адаптивными.

Стабильные алгоритмы сортировки поддерживают относительный порядок записей с одинаковыми ключами. Если все ключи разные, то в этом различии нет необходимости. Но если есть одинаковые ключи, то алгоритм сортировки устойчив, если есть две записи (скажем, R и S) с одним и тем же ключом, и R появляется перед S в исходном списке, тогда R всегда будет стоять перед S в отсортированном списке. Когда равные элементы неразличимы, например, с целыми числами или, в более общем случае, с любыми данными, где весь элемент является ключом, стабильность не является проблемой. Однако предположим, что следующие пары чисел должны быть отсортированы по их первому компоненту:

(4, 2) (3, 7) (3, 1) (5, 6)

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

Для распространения ключевого сравнения на другие компоненты требуются дополнительные вычислительные затраты.

Имя Среднее Худший Память Стабильный Метод
Пузырьковая сортировка O(n 2 ) O(n 2 ) O(1) Да Обмен
Сортировка выбором O(n 2 ) O(n 2 ) O(1) Нет Выбор
Сортировка вставками O(n 2 ) O(n 2 ) O(1) Да Вставка
Сортировка слиянием O(n log n) O( n log n) O(n) Да Объединение
Быстрая сортировка O(n log n< /i>) O(n 2 ) O(1) Нет Разбиение на разделы
Heapsort< /td> O(n log n) O(n log n) O(1) Нет Выбор

Пошаговый пример

Предположим, что у нас есть массив "5 1 4 2 8", и мы хотим отсортировать массив от наименьшего числа к наибольшему с помощью пузырьковой сортировки.

Реализация псевдокода

процедура bubbleSort( A : список сортируемых элементов), определенная как:
do
swapped := false
для каждого i от 0 до length(A) - 1 включительно do:
/> if A[i] > A[i+1] then
swap( A[i], A[i+1] )
swapped := true
end if
конец для
при обмене
конец процедуры

Улучшенная альтернативная реализация

процедура bubbleSort( A : список сортируемых элементов ), определенная как:
n := length( A )
сделать
поменялась местами := false
для каждого i в 0 на n - 1 включительно do:
если A[ i ] > A[ i + 1 ] then
swap( A[i ], A[ i + 1 ] )
swapped := true < br /> end if
end for
n := n - 1
while swapped
конец процедуры

Здесь вместо n(n-1) сравнений мы уменьшаем его до (n-1) + (n-2) + . + 1 = n(n-1)/2 сравнения.

Производительность

  • Худшая производительность: O(n 2 )
  • Оптимальная производительность: O(n)
  • Средняя эффективность обращения: O(n 2 )
  • Сложность пространства в наихудшем случае: O(n) общая, O(1) вспомогательная

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

  1. Найти минимальное значение в списке
  2. Поменять его местами со значением в первой позиции.
  3. Повторите описанные выше шаги для остальной части списка (начиная со второй позиции и продвигаясь каждый раз)

Фактически мы делим список на две части: подсписок уже отсортированных элементов и подсписок элементов, которые еще предстоит отсортировать.

Пример. Рассмотрим пример сортировки "64 25 12 22 11".

Реализация алгоритма на языке Java

void selectionSort(int[] a) for (int i = 0; i

Производительность

  • Худшая производительность: O(n 2 )
  • Оптимальная производительность: O(n 2 )
  • Средняя эффективность обращения: O(n 2 )
  • Сложность пространства в наихудшем случае: O(n) общая, O(1) вспомогательная

Сколько сравнений должен выполнить алгоритм? Сколько свопов выполнит алгоритм в худшем случае?

Выбор самого нижнего элемента требует сканирования всех n элементов (для этого требуется n-1 сравнений), а затем замены его на первую позицию. Поиск следующего нижнего элемента требует сканирования всех элементов n-1 и т. д. для (n-1) + (n-2) + . + 2 + 1 (O(n 2 )) сравнений. Для каждого из этих сканирований требуется один обмен для n-1 элементов.

  • Простая реализация
  • Эффективно для небольших наборов данных.
  • Адаптивный, т. е. эффективный для наборов данных, которые уже существенно отсортированы: временная сложность составляет O(n+d), где d — количество инверсий
  • На практике более эффективен, чем большинство других простых квадратичных алгоритмов, таких как сортировка выбором или пузырьковой сортировкой: среднее время выполнения составляет n 2/4, а время выполнения в лучшем случае является линейным
  • Стабильный, т. е. не изменяет относительный порядок элементов с одинаковыми ключами.
  • На месте, т. е. требуется только постоянное количество O(1) дополнительной памяти
  • Онлайн, т. е. может сортировать список по мере его получения.

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

Сортировка обычно выполняется на месте. Результирующий массив после k итераций имеет свойство сортировать первые k+1 записи. В каждой итерации первая оставшаяся запись ввода удаляется, вставляется в результат в правильной позиции, тем самым расширяя результат.

Пример. Рассмотрим пример сортировки "64 25 12 22 11".

Реализация псевдокода:

insertionSort(array A)
begin
for i := 1 to length[A] - 1 do
begin
value := A[i];
j := i - 1;
while j >= 0 and A[j] > value do
begin
A[j + 1] := A[j];
j := j - 1;
конец;
A[j + 1] := значение;
конец;
конец;

  • Худшая производительность: O(n 2 )
  • Оптимальная производительность: O(n)
  • Средняя эффективность обращения: O(n 2 )
  • Сложность пространства в наихудшем случае: O(n) общая, O(1) вспомогательная

Сравнение O(n 2 ) алгоритмов сортировки

Среди простых алгоритмов O(n 2 ) среднего случая сортировка выбором почти всегда превосходит пузырьковую сортировку, но обычно уступает сортировке вставками.

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

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

И сортировка вставками, и сортировка выбором обычно выполняются быстрее для небольших массивов (т. е. менее 10–20 элементов). На практике полезной оптимизацией рекурсивных алгоритмов является переключение на сортировку вставками или сортировку выбором для «достаточно маленьких» подмассивов.

Концептуально сортировка слиянием работает следующим образом:

  1. Если список имеет длину 0 или 1, то он уже отсортирован. В противном случае:
  2. Разделите несортированный список на два подсписка примерно вдвое меньшего размера.
  3. Рекурсивно сортировать каждый подсписок, повторно применяя сортировку слиянием.
  4. Объедините два подсписка обратно в один отсортированный список.

Сортировка слиянием включает в себя две основные идеи по улучшению времени выполнения:

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

Пример: отсортируйте следующие числа 35, 62, 33, 20, 5, 72, 48, 50.

Производительность

  • Производительность в худшем случае: O(n log n)
  • Оптимальная производительность: O(n log n) типично
  • Средняя производительность обращения: O(n log n)
  • Наихудшая пространственная сложность: O(n) общая, O(n) вспомогательная

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

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

= 2 [ 2 T(n/4) + n/2 ] + n

= 4 [ 2 T(n/8) + n/4 ] + 2n

= 2 k T(n/2 k ) + kn

Мы знаем, что T(1) = 1, и это способ закончить вывод выше. В частности, мы хотим, чтобы T(1) отображалось справа от знака =. Это означает, что мы хотим:

n/2 k = 1 ИЛИ n = 2 k ИЛИ log2 n = k
Продолжая предыдущий вывод, мы получаем следующее, поскольку k = log2 n:

= 2k T(n/2k ) + kn

= n + n log2 n [помните, что T(1) = 1]

= O(n log n)

Итак, мы решили рекуррентное соотношение, и его решение — это то, что мы «знали», что оно будет. Чтобы сделать это формальным доказательством, вам нужно будет использовать индукцию, чтобы показать, что O(n log n) является решением данного рекуррентного соотношения, но принцип «подключи и пыхни» Показанный выше метод показывает, как получить решение --- последующую проверку того, что это решение, можно оставить более продвинутому классу алгоритмов.

Быстрая сортировка – это сравнительная сортировка, и в эффективных реализациях она не является стабильной сортировкой.

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

  1. Выберите из списка элемент, который называется основной.
  2. Переупорядочите список так, чтобы все элементы, меньшие опорного, располагались перед опорным, а все элементы, превышающие опорный, располагались после него (равные значения могут идти в любом направлении). После этого разбиения стержень занимает свое конечное положение. Это называется операцией разделения.
  3. Рекурсивно сортировать подсписок меньших элементов и подсписок больших элементов. Базовым случаем рекурсии являются списки нулевого или единичного размера, которые всегда сортируются.

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

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

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

Псевдокод раздела:

private static int partition(int[] data, int first, int n) <
1. Инициализировать значения:
pivot = data[first];
tooBigIndex = первый + 1; // Индекс элемента после поворота
tooSmallIndex = first + n - 1; // Индекс последнего элемента

<р>2. Повторяйте следующее, пока два индекса не пересекутся
2a. пока tooBigIndex еще не вышел за конечный индекс части массива, который мы разбиваем,
и data[tooBigIndex] меньше или равен опорному, переместите tooBigIndex к следующему индексу.

2б. пока data[tooSmallIndex] больше опорного, переместите tooSmallIndex вниз к предыдущему индексу.

2с. если (слишком большой индекс

Выбор хорошего элемента сводки

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

Попробуем алгоритм быстрой сортировки со следующим массивом: 40, 20, 10, 80, 60, 50, 7, 30, 100, 90 и 70.

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

Как это работает?

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

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

Попробуем алгоритм со следующей двоичной кучей, хранящейся в массиве: 45, 27, 42, 21, 23, 22, 35, 19, 4 и 5.

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

2. Критерии эффективности

  • Время работы. Как правило, элементарный алгоритм сортировки требует O(N 2 ) шагов для сортировки N случайно расположенных элементов. Более сложные алгоритмы сортировки требуют в среднем O(N log N) шагов. Алгоритмы различаются константой, которая стоит перед N 2 или N log N. Кроме того, некоторые алгоритмы сортировки более чувствительны к характеру входных данных, чем другие. Быстрая сортировка, например, требует O(N log N) времени в среднем, но требует O(N 2 ) времени в худшем случае.
  • Требования к памяти. Объем дополнительной памяти, необходимой для алгоритма сортировки, также является важным фактором. Алгоритмы сортировки на месте являются наиболее эффективными с точки зрения памяти, поскольку они практически не требуют дополнительной памяти. Представления связного списка требуют дополнительных N слов памяти для списка указателей. Другие алгоритмы требуют достаточного объема памяти для еще одной копии входного массива. Это самые неэффективные с точки зрения использования памяти.
  • Стабильность. Это способность алгоритма сортировки сохранять относительный порядок одинаковых ключей в файле.

3. Сортировка выбором

  • Найдите наименьший элемент в массиве и замените его на элемент в первой позиции.
  • Найдите второй наименьший элемент в массиве и замените его элементом на второй позиции.
  • Продолжайте этот процесс, пока не закончите.

inline void swap(ItemType a[], int i, int j)
ItemType t = a[i];
a[i ] = a[j];
a[j] = t;
>

void selection(ItemType a[], int N)
int i, j, min;

для (i = 1; i 2 ) сравнений, поэтому его следует использовать только для небольших файлов. Из этого правила есть важное исключение. При сортировке файлов с большими записями и маленькими ключами стоимость обмена записями определяет время выполнения. В таких случаях сортировка выбором требует O(N) времени, поскольку количество обменов не превышает N.

4. Сортировка вставками

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

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

Вот код для сортировки вставками:

void insertion(ItemType a[], int N)
int i, j;
ItemType v;

для (i = 2; iv)
a[j] = a[j-1];
j--;
>
a[j] = v;
>
>

Важно отметить, что в цикле while нет проверки, чтобы предотвратить выход индекса j за границы. Это может произойти, если v меньше, чем a[1],a[2]. а[i-1]. Чтобы исправить эту ситуацию, мы помещаем ключ sentinel в a[0], делая его как минимум равным наименьшему элементу в массиве. Использование дозорного более эффективно, чем выполнение теста вида while (j > 1 && a[j-1] > v). Сортировка вставками — это метод O(N 2 ) как в среднем, так и в худшем случае. По этой причине он наиболее эффективно используется для файлов размером примерно N K -1)/2. 121,40,13,4,1, что получается из повторения hk = 3 hk+1+1. Обратите внимание, что последовательность, полученная путем взятия степеней двойки, приводит к плохой производительности, поскольку элементы в нечетных позициях не сравниваются с элементами в четных позициях до конца.

Вот полный код сортировки оболочки:

void shell(ItemType a[], int N)
int i, j, h;
ItemType v; < /p>

для (h = 1; h 0; h /= 3)
для (i = h+1; ih && a[jh] > v)
a[j] = a[jh];
j -= h;
>
a[j] = v;
>
>

Сортировка оболочки требует O(N 3/2 ) операций в худшем случае, что означает, что ее можно достаточно эффективно использовать даже для файлов среднего размера (скажем, N слева)
v = a[право];
i = слева - 1;
j = справа;
for (;;)
while (a[++i] v);
if (i >= j) break;
своп(a,i,j);
>
своп(a,i,право);
быстрая сортировка(a,left,i-1);
быстрая сортировка(a,i+1,right);
>
>

  • Использование метода разбиения медианы из трех делает наихудший случай гораздо менее вероятным и устраняет необходимость в дозорных. Основная идея заключается в следующем. Выберите три элемента, a[left], a[middle] и a[right] слева, посередине и справа от массива. . Отсортируйте их (путем прямого сравнения) так, чтобы медиана из трех находилась в a[середине], а наибольшая — в a[справа]. Теперь замените a[middle] на a[right-1]. Наконец, мы запускаем алгоритм разбиения на подмассив a[left+1],a[left+2]. a[right-2] с a[right-1] в качестве элемента разделения.
  • Другое улучшение заключается в удалении рекурсии из алгоритма за счет использования явного стека. Основная идея заключается в следующем. После разделения поместите больший подфайл в стек. Меньший подфайл обрабатывается немедленно путем простого сброса параметров left и right (это называется удалением конца рекурсии). При явной реализации стека максимальный размер стека составляет около log2 N. С другой стороны, при рекурсивной реализации базовый стек может достигать N.
  • Третье усовершенствование заключается в использовании сортировки отсечкой для вставки всякий раз, когда встречаются небольшие подмассивы. Это связано с тем, что сортировка вставками, хотя и алгоритм O(N 2 ), имеет достаточно маленькую константу перед N 2 , чтобы быть более эффективной, чем быстрая сортировка для небольших Н. Подходящим значением размера подмассива отсечки будет приблизительно диапазон 5 ~ 25.

7. Выбор алгоритма сортировки

В таблице 1 приведены характеристики производительности некоторых распространенных алгоритмов сортировки. Сортировка Шелла обычно является хорошим начальным выбором для файлов среднего размера N

Читайте также: