Билет №4. Понятие сортировки.

Главные понятия и способы сортировки
Сортировка – это процесс расстановки частей «в неком порядке». Элементы располагаются так, чтоб, во-1-х, вычисления требующие определенного порядка расположения данных, могли производиться отлично, во-2-х, результаты имели осмысленный вид, в третьих, следующие процессы бы применимые начальные данные.
Записи, поля и ключи.Единица данных, приемлимо обрабатываемая информационными Билет №4. Понятие сортировки. системами, именуется записью. Запись – это совокупа частей инфы о каком-то событии либо структуре. Каждый элемент инфы в записи, таковой как номер служащего, стоимость единицы продукта либо валовой объем, именуется полем записи. Совокупа полей идентифицирует и обрисовывает то, что представлено в записи. Из записей составляются файлы либо наборы данных. Сортировка Билет №4. Понятие сортировки. является процессом перестановки записей либо их индексов, при котором их обоюдное размещение в файле приводиться в порядок, определяемый неким известным ключом. Ключом именуется поле, содержащее величину, применяемую в правилах упорядочивания файла.
В предположении, что результатом сортировки является физическое упорядочивание, сортировка 2-ух записей в собственной простейшей форме состоит из сопоставления их Билет №4. Понятие сортировки. главных полей и определений, которое из их «меньше». После чего записи переставляются так, что запись с «меньшим» ключом ставиться перед записью с «большим» ключом.
Найти, какой ключ «меньше», можно, используя хоть какое правило. Явными правилами являются: алфавитное упорядочивание, числовое и буквенно-цифровое. (В последнем правиле ключи могут Билет №4. Понятие сортировки. содержать смесь букв и цифр; соглашения, принятые в системе, определяют упорядочение букв и цифр.)
Ключом записи может быть одно поле либо композиция полей, распределенных по записи. Если ключ состоит из нескольких несоприкасающихся полей, то он именуется составным ключом.
Время от времени лучше упорядочение снутри упорядочивания. К примеру, файл Билет №4. Понятие сортировки. может быть упорядочен по номеру места работы, а снутри этого упорядочения – по номеру служащего. Поле, содержащее номер места работы, именуется старшим ключом, а поле, содержащее номер служащего, – младшим ключом. Так стильно найти несколько уровней ключей, и все уровни, хорошие от первого, именуются младшими ключами. Старший и младший ключи можно рассматривать как один Билет №4. Понятие сортировки. составной ключ в записи.
В информационной системе время от времени комфортно, чтоб файлы упорядочивались не единственным методом. Разные сортировки в качестве ключа могут использовать разные поля.
Запись может состоять только из поля ключа. В обработке научных приложений это не является кое-чем исключительным. В данной работе Билет №4. Понятие сортировки. при рассмотрении способов сортировки будет предполагаться, что записи состоят из 1-го поля. Это изготовлено для того, чтоб упростить первоначальное представление о способах сортировки за счет устранения побочных заморочек, возникающих при перемещении данных. Так как эти способы идиентично отлично применимы к записям, содержащим как главные, так и неключевые поля, то это Билет №4. Понятие сортировки. предположение не ограничивает общности.
Обычно способы сортировки делят на внутренние и наружные. Внутренние способы – это такие способы, которые могут применяться с применимой производительностью только к тем перечням данных, которые полностью помещаются в основной (оперативной) памяти микропроцессора. Наружные способы – это такие способы, которые применимы для файлов данных, которые очень значительны, чтоб поместится Билет №4. Понятие сортировки. в основной памяти, и потому должны в течение процесса сортировки размещаться на устройствах наружной памяти (лентах, дисках, барабанах). Слово перечень нередко обозначает набор записей, расположенных в основной памяти.
Линейный выбор с обменом: внедрение обменов
В качестве примера обмена в процессе сортировки разглядим тут наименьшую по памяти Билет №4. Понятие сортировки. версию линейного выбора. Обменом именуется перестановка позиций 2-ух записей в перечне зависимо от результата проверки их относительной величины. Если в перечне встречается запись с ключом, наименьшим, чем у предшествующей, то эти записи изменяются местами. Производительность способов обмена находится в зависимости от трудности определения последовательности сравнений и обменов. Нередко число обменов уменьшают Билет №4. Понятие сортировки., откладывая обмен до конца каждого просмотра. Это прием, а именно, употребляется в способе, который будет описан ниже.
Линейный выбор с обменом. Сначала первого просмотра подразумевается, что 1-ый элемент перечня имеет меньший ключ. Этот ключ вкупе с адресом пересылается в рабочую память, где сравнивается со всеми линейными преемниками до того Билет №4. Понятие сортировки. времени, пока не повстречается наименьший ключ. Наименьший ключ и его адресок становятся содержимым рабочей области памяти.
Сопоставления длятся при новеньком содержимом рабочей памяти. Пересылка производится всегда, когда в перечне встречается ключ, который меньше ключа в рабочей памяти. Таким макаром, в рабочей памяти всегда размещен меньший из уже просмотренных ключей. Просмотр Билет №4. Понятие сортировки. завершается по достижении конца перечня. Ранее момента процесс схож обычному линейному выбору. Сортировка обменом отличается последующим шагом.
По окончании первого просмотра запись, ключ которой размещен в рабочей памяти, переставляется с записью из верхушки перечня. Сейчас меньшая величина в перечне занимает первую позицию. 2-ой просмотр схож первому Билет №4. Понятие сортировки. с той только различием, что вторым по величине считается 2-ой ключ, потому что первым стоит меньший элемент. 1-ая позиция исключается из процесса. По окончании второго просмотра 2-ая запись с минимальным ключом помещается во вторую позицию перечня. 3-ий просмотр начинается сопоставлением ключа из третьей позиции и т.д. Эта процедура Билет №4. Понятие сортировки. завершается, когда свое место занимает (N – 1) – я запись.
алг Sort (арг цел N, вещ таб A [1:N])
нач цел i, j, k, Maxi
нц для i от N до 2 шаг -1
Maxi:= i;
нц для j от 1 до i – 1
ЕслиA[j] >A[Maxi]
то Maxi:= j;
все
Если Maxi i
тоk:= A[i];
A[i Билет №4. Понятие сортировки.]:= A[Maxi];
A[Maxi]:= k;
все
кц
кон
Оценим количество сравнений. При первом просмотре их N – 1, при втором – N – 2, при последнем – 1. Полное количество C = N –1 + N – 2 + …+ 1 = C = N × (N – 1)/2, другими словами имеет порядок O(N2).
Линейный выбор с подсчетом
Способ сортировки с подсчетом описывается в литературе Билет №4. Понятие сортировки. как процедура упорядочения внутреннего перечня чисел. Практически, это не способ сортировки, а технический прием, который можно использовать в разных способах для сокращения количества обменов либо полного их устранения. Он является формой индексирования, в какой счетчик относительной позиции каждого элемента корректируется в течение процесса сопоставления. Ниже будет описан этот технический прием Билет №4. Понятие сортировки. применительно к линейному выбору.
Подсчет как технический прием. Память, применяемая линейным выбором с подсчетом, будет включать область вывода (так же как и при линейном выборе) для хранения совсем упорядоченного перечня. Размер области вывода отвечает этим же суждениям, что и при линейном выборе. Дополнительно должна быть обеспечена память под счетчик для Билет №4. Понятие сортировки. каждого элемента перечня. В итоге действий над значениями этих счетчиков появляется огромное количество индексов позиций для частей в упорядоченном перечне. При каждом просмотре ключ сравнивается со своими линейными преемниками. Всякий раз, когда находится больший ключ, его счетчик возрастает на единицу. Если отысканный ключ меньше либо равен, то возрастает Билет №4. Понятие сортировки. счетчик соответственный большему из сравниваемому ключей. Как следует, в хоть какой момент времени счетчик элемента показывает количество ключей, о которых понятно, что они меньше ключа рассматриваемого элемента.
При первом просмотре 1-ый ключ в перечне сравнивается со всеми остальными ключами. В его счетчике подсчитывается количество наименьших ключей. В счетчиках Билет №4. Понятие сортировки. огромных ключей будут 1. При втором просмотре 1-ый ключ не рассматривается. 2-ой ключ сравнивается с ключами всех преемников. Подсчеты фиксируются. Этот процесс длится N – 1 раз. На этом шаге понятно относительная позиция каждого элемента. Помещая ключи в выходной перечень в согласовании со значениями их счетчиков, получаем упорядоченный перечень.
алг Sort (аргцел Билет №4. Понятие сортировки. N, цел таб A [1:N], рез цел табB [1:N]);
нач целi, j, цел таб Count [1:N]
нц для i от N до2 шаг -1
нц для j от i – 1 до 1 шаг -1
ЕслиA[i] < A[j]
то Count [j]:= Count [j] + 1
иначеCount [i]:= Count [j]+1
все
кц
кц
нц для i от 1 до N
B Билет №4. Понятие сортировки. [Count [i] + 1]:= A[i]
кц
кон
Число сравнений равно N2/2. Производится (N-1) просмотров с N/2 сопоставлениями в среднем на каждом просмотре. Значение счетчиков меняется столько раз, сколько раз производится сопоставление.
Сортировка обменом
Сортировка обменом – это общий термин, применяемый для описания семейства малых по памяти способов сортировки, которые меняют Билет №4. Понятие сортировки. местами элементы перечня, если предыдущий элемент больше следующего. Просмотр файла может протекать сверху вниз либо снизу ввысь либо изменяться от просмотра к просмотру.
Существует ряд определенных вариантов, которые различаются последовательностями сравнений частей перечня. Во всех простых способах обмена элемент сравнивается со своим наиблежайшим соседом, а вероятными перемещениями являются перемещение Билет №4. Понятие сортировки. элемента с огромным ключом на одну позицию вниз и перемещение элемента с наименьшим ключом на одну позицию ввысь. Парный обмен, стандартный обмен и просеивание являются 3-мя ординарными формами сортировки обменом.
Способ парного обмена (также именуемый «нечетно-четная перестановка») состоит из различного числа «нечетных» и «четных» просмотров. При нечетных просмотрах Билет №4. Понятие сортировки. каждый элемент из нечетной позиции сравнивается со своим соседом из четной позиции и больший из их занимает огромную позицию. Нисходящий просмотр перечня длится до того времени, пока последний нечетный элемент (N – 1) в перечне не сравнивается с последним четным элементом N. Если в перечне нечетное число частей, то последний элемент Билет №4. Понятие сортировки. не будет участвовать в сопоставлении. В течение каждого просмотра ведется подсчет обменов.
При четных просмотрах четные позиции сравниваются с примыкающими нечетными. Обмены производятся тогда, когда нужно, чтоб больший из пары занял нечетную позицию. Таким макаром, ключи с большенными значениями передвигаются на дно перечня. При всем этом должно быть столько Билет №4. Понятие сортировки. просмотров, сколько нужно для того чтоб переместить в позицию число, более удаленное от собственной конечной позиции. Потом производится заключительный просмотр, нужный для того, чтоб опознать упорядоченность. В течение этого просмотра счетчик обменов равен 0. Данный способ просит, по последней мере, 2-ух просмотров – 1-го нечетного и 1-го четного.
Способ стандартного Билет №4. Понятие сортировки. обмена (также именуемый «методом пузырька») перемещает один элемент перечня в подобающую позицию при каждом просмотре. Таким макаром, при первом просмотре запись с большим ключом помещается в последнюю позицию, при втором просмотре запись со последующим по величине ключом перемещается в предпоследнюю позицию и т.д. Способ может быть преобразован Билет №4. Понятие сортировки. так, что будет располагать элементы по убыванию.
При первом просмотре 1-ый элемент перечня сравнивается со своим конкретным преемником, и, если этот преемник меньше, они изменяются местами. Сейчас больший элемент, расположенный во 2-ой позиции, сравнивается с элементом из третьей позиции. Обмен происходит, если нужно больший из их расположить в третьей позиции. Потом позиция Билет №4. Понятие сортировки. 3 сравнивается с позицией 4, позиция 4 с позицией 5 и т.д. когда позиция N – 1 сравнивается с позицией N, просмотр завершается.
Если в перечне элемент k – 1 размещен ранее чем k, то при каждом сопоставлении (k – 1): k больший элемент попадает в позицию k. Элемент, перемещаемый вниз, считается на этот момент большим в перечне Билет №4. Понятие сортировки.. Когда при сопоставлении находится, что k-й элемент больше, обмен не происходит. Как следует, всякий раз сравниваются элемент, считающийся большим (k – 1), и его конкретный преемник k.
2-ой просмотр схож первому с той только различием, что уже установленная позиция исключается из последовательности. Каждый следующий просмотр исключает еще одну установленную позицию Билет №4. Понятие сортировки., укорачивая перечень.
Подсчет обменов ведется для каждого просмотра. Просмотр, в итоге которого число обменов не возросло, кончает сортировку.
алгSort (аргцел N, цел таб A [1:N])
нач целk, i, w
нц для k от N доN – 1
нц дляi от 1 доN – k
еслиA[i] > A [i + 1]
тоw:= A[i]
A[i Билет №4. Понятие сортировки.]:= A [i + 1]
A [i + 1]:= w
все
кц
кц
кон
При сортировке «методом пузырька» производится N – 1 просмотр, при этом на i – м просмотре делается N – i сравнений. Общее количесво сравнений C = N × (N – 1)/2, другими словами имеет порядок O(N2).
Способ просеивания (также именуемый «линейной вставкой с обменом» либо «челночной сортировкой») является самым Билет №4. Понятие сортировки. наилучшим из этих способов. Он отличается от других способов обмена тем, что не сохраняет фиксированной последовательности сравнений. Не считая этого, исчезает разделение на отдельные просмотры как следствие схемы последовательностей сравнений. Способ просеивания работает точно так же, как стандартный обмен до того времени, пока не нужно делать перестановку Билет №4. Понятие сортировки.. Сравниваемая величина с наименьшим ключом подымается как это может быть ввысь по списку. Она сравнивается «в оборотном порядке» со всеми ее линейными предшественниками по направлению к верхушке перечня. Если ее ключ меньше, чем у предшественника, то производится обмен и начинается еще одно сопоставление. Когда элемент, передвигаемый ввысь, встречается с наименьшим Билет №4. Понятие сортировки. ключом, этот процесс прекращается и нисходящие сопоставления возобновляются с той позиции, с которой производился 1-ый обмен.
Будем именовать нисходящее сопоставление первичным, а восходящее вторичным. Хоть какое первичное сопоставление может прирастить число вторичных сравнений. Если первичное сопоставление обхватывает позиции 6 и 7, то цепочка вторичных сравнений может иметь самое большее 5 сравнений Билет №4. Понятие сортировки.. Этот максимум достигается, если начальный ключ из позиции 7 меньше всех ключей в перечне, расположенных выше этой позиции. Фактическая длина последовательности вторичных сравнений находится в зависимости от величины двигающегося ввысь элемента относительно величины каждого элемента из предыдущей упорядоченной части перечня.
Сортировка завершается, когда первичное сопоставление обхватит (N + 1) – й элемент.
Сортировка Билет №4. Понятие сортировки. вставками
Сортировка вставками есть общее заглавие группы способов сортировки, основанных на поочередной вставке «новых» частей в увеличивающийся упорядочиваемый перечень. Посреди их есть три значительно различных способа: линейная вставка, центрированная вставка и двоичная вставка. Эти способы сортировки различаются способами поиска подходящего места для вставки элемента. Простым способом является линейная вставка. Как Билет №4. Понятие сортировки. надо из наименования, в этом способе уже имеющийся перечень рассматривается как обычной линейный перечень, просматриваемый поэлементно сверху вниз, пока не будет найдена соответственная позиция для нового элемента.
Этот способ обычно употребляется тогда, когда процесс, наружный к данной сортировке, динамически заносит добавление в перечень, все элементы которого известны и который должен всегда Билет №4. Понятие сортировки. поддерживаться в упорядоченном состоянии. Сортировка производится всякий раз при получении нового элемента, размещая этот элемент в необходимое место перечня и облегчая контроль. Некие свойства систем реального времени делают вставку полезным техническим приемом.
Связь меж процессом, порождающим подлежащие сортировке числа, и сортировкой такая, что сортировка привлекается неоднократно. Такое Билет №4. Понятие сортировки. повторное вербование может быть связано с некими издержками, такими как передача характеристик, вход и выход из процедуры. Эти издержки должны быть выявлены и учтены при анализе использования способа вставок таким методом. Сортировку вставками можно организовать как один унифицированный процесс.
Способ линейной вставки. Под сортировку выделяется количество памяти, равное предполагаемой Билет №4. Понятие сортировки. длине окончательного перечня из всех частей. Счетчик длины перечня в самом начале устанавливается равным нулю. С помощью этого счетчика контролируется длина области поиска подходящей позиции для элемента, вставляемого в перечень. Сортировка привлекается для каждого элемента. Один «вызов» сортирующей подпрограммы располагает один элемент в перечне и наращивает счетчик перечня на Билет №4. Понятие сортировки. единицу.
1-ый элемент помещается в верхнюю позицию области вывода. Последующий элемент, присоединяемый к списку, сравнивается с первым. Если ключ нового элемента больше, он помещается в позицию, последующую за позицией первого элемента. Если ключ нового элемента меньше, то 1-ый элемент перемещается в позицию 2, а новый элемент помещается в позицию 1.
В предстоящем Билет №4. Понятие сортировки. все новые элементы поочередно сравниваются с каждым элементом перечня, начиная с первого, до того времени, пока не повстречаться больший. Этот больший элемент и все следующие элементы перечня передвигаются на одну позицию вниз. Таким макаром освобождается место, на которое вставляется новый элемент.
Способ сортировки Шелла
Сортировка Шелла является расширением сортировки просеиванием Билет №4. Понятие сортировки.. Последний просмотр в сортировке Шелла схож способу просеивания, описанному чуть повыше. Предыдущие просмотры употребляют тот же технический прием, но в их сравниваются и обмениваются не конкретные соседи, а элементы отстоящие на данное расстояние. К примеру, позиция 1 сравнивается с позицией 5, позиция 5 с позицией 9, 9 с 13 и т.д Билет №4. Понятие сортировки.. Когда найдена инверсия, цепочка вторичных сравнений обхватывает те элементы, которые входили в последовательность первичных сравнений. К примеру, если найдена инверсия меж позициями 9 и 13, то вероятная вторичная последовательность состоит из сравнений 5: 9 и 1: 5.
На каждом просмотре шаг меж сравниваемыми элементами определяется методом сокращения вычисленного начального шага. На последнем просмотре он сокращается до 1. Цель способа Билет №4. Понятие сортировки. на ранешних просмотрах – уменьшить число вторичных сравнений и обменов на более поздних просмотрах. В этом способе элементы могут совершать резкие скачки к необходимым позициям на ранешних просмотрах, а не передвигаться на одну позицию за раз. На последнем просмотре числа будут стремиться размещаться близко к своим позициям и, как Билет №4. Понятие сортировки. следует, потребуют малозначительных перемещений при окончательном размещении.
Модификации способа различаются методами вычисления исходного шага меж элементами и правилами сокращения этого шага от просмотра к просмотру.
Вариант с отложенными обменами
При описании способа сортировки Шелла предполагалось, что обмен следует за каждым сопоставлением, которое выявляет элемент больший, чем предшествующий элемент части. В Билет №4. Понятие сортировки. методе (размещенном Хиббардом) применен способ, сокращающий число обменов. Этот метод отличается то ранее описанного тем, что он употребляет временную память для хранения сравниваемых частей в течение всей последовательности сравнений.
Каждое первичное сопоставление Ключi: ключi +шаг включает пересылку ключi +шаг во временную память. Сопоставление позиции 1 с позицией 4, к Билет №4. Понятие сортировки. примеру, по сути включает пересылку из позиции 4 во временную память и сопоставление ключа из временной памяти с ключом из позиции 1. Если ключi больше, он перемещается в позицию ключi +шаг. Если ключi +шаг больше, то перемещение не надо. Пересылка во временную память позволяет отлично освобождать позицию следующего элемента этой части.
Когда ключi Билет №4. Понятие сортировки. больше, чем ключi +шаг, то ключi пересылается из собственной позиции в «свободную» позицию, и способ начинает последовательность вторичных сравнений. Содержимое временной памяти (ключi +шаг) – это запись, поднимающаяся на верх данной части. Ключ каждой записи сравнивается с временной памятью и, если найдено, что он больше, пересылается вниз Билет №4. Понятие сортировки. перечня в текущую свободную позицию. Любая пересылка высвобождает позицию перемещенного элемента. Когда в перечне найден элемент с ключом, наименьшим ключа временной памяти, содержимое временной памяти помещается в позицию перечня освобожденной самой последней, т.е. в необходимое место.
Внедрение временной памяти отлично тогда, когда длина последовательности вторичных сравнений не меньше 2. Так Билет №4. Понятие сортировки. как, вероятнее всего это правильно для списков случайной конечной длины со случаем упорядоченными данными, то вариант с отложенными обменами может, вообщем говоря, быть лучше других сортировок Шелла.
Стремительная сортировка
Способ резвой сортировки был в первый раз описан Ч.А.Р. Хоаром В 1962 году. Стремительная сортировка – это общее заглавие ряда алгоритмов Билет №4. Понятие сортировки., которые отражают разные подходы к получению критического параметра, влияющего на производительность способа.
Способ резвой сортировки. Некий элемент перечня выбирается в качестве «основы». Все элементы, меньше базы, располагаются в позициях с начала списка»; все элементы, больше базы, располагаются в позициях с конца перечня. Элементы сравниваются с основой и изменяют свою позицию Билет №4. Понятие сортировки., когда они больше и размещены в писке выше нее, либо когда меньше и размещены в перечне ниже нее. Это упорядочение составляет шаг сортировки. В конце шага для размещения базы применима некая позиция в перечне. Эта позиция соответствует месту базы в окончательном перечне, так как ее относительный адресок Билет №4. Понятие сортировки. в перечне определяется числом частей выше и ниже нее.
Шаг определяет две части. Если значение базы отлично аппроксимирует медиану перечня, то эти две части будут приблизительно равной длины. Если база является наихудшей вероятной оценкой медианы (большим либо минимальным элементом перечня), то эти части будут длиной 0 и К – 1, где Билет №4. Понятие сортировки. К – это длина начального перечня.
Метод построения частей, по существу, один и тот же во всех версиях метода. Инсталлируются два указателя, один на начало, другой на конец перечня. После выбора базы поиск наименьшей величины начинается с указателя конца, перемещающегося ввысь к началу перечня. Сопоставления длятся до того времени, пока не будет найден Билет №4. Понятие сортировки. элемент, наименьший базы, либо не будет исчерпан перечень.
Когда элемент, наименьшей базы, найден, его нужно переместить в позицию, содержащий элемент, большей базы. Эта позиция находится при сопоставлениях, использующих указатель начала. Сопоставления производятся сверху в низ по списку до того времени, пока указатель начала не укажет на Билет №4. Понятие сортировки. больший элемент. Таким макаром, элементы, больший и наименьший базы, идентифицированы, и сейчас производится обмен меж ними.
Модификации появляются исключительно в способе пересылки частей данных. Один метод заключается в том, что база пересылается во временную память, а содержимое начала перечня перемещается в освободившуюся позицию. При всем этом освобождается исходная позиция, куда можно Билет №4. Понятие сортировки. переместить элемент. После пересылки свободная позиция двигается в ячейку, расположенную близко к концу перечня. При нисходящем поиске отыскивается элемент для пересылки в эту свободную позицию. Свободная позиция чередуется с верхней и нижней позициями до того времени, пока указатели не совместятся.
После обмена либо двойной пересылки возобновляется поиск Билет №4. Понятие сортировки. другого элемента, наименьшего базы. Когда он найден, начинается поиск большего элемента с внедрением указателя начала. Этот процесс длится до того времени, пока два указателя не повстречаются. Относительная длина частей определяется позицией в перечне, в какой совместятся указатели начала и конца. В неких версиях этого способа нужно ассоциировать относительные позиции указателей после Билет №4. Понятие сортировки. каждого перемещения по списку ввысь либо вниз.
На первом шаге строятся две части. Одна из их употребляется в качестве начальной на втором шаге, 2-ая помещается в стек LIFO. Общепринятое правило таково: первой обрабатывать наименьшую часть, а границы большей запоминать в стеке. 2-ой шаг порождает две части. Наименьшая обрабатывается на Билет №4. Понятие сортировки. 3-ем шаге, а большая перемещается в стек над большей частью, построенной на шаге 1. Процесс порождения частей, запоминания большей из их в стеке и разделения наименьшей длится до того времени, пока все части не сократятся до 1-го элемента. При появлении одноэлементной части новенькая часть для стека не строится Билет №4. Понятие сортировки.. Ожидающие части выбираются из стека и обрабатываются. Сортировка выполнена, когда стек пуст.
Обработка наименьшей из 2-ух частей гарантирует, что ожидающих частей в стеке будет менее log2N. Последовательность обработки частей совсем произвольна и может изменяться по желанию программера.
Стремительная сортировка может употребляться в комбинированном методе, чтоб уменьшить части до заблаговременно определенного размера Билет №4. Понятие сортировки., после этого они упорядочиваются другим способом, более действенным для малых списков.
Алг QuickSort (арг цел m, t)
нач целi, j, x, w
i:= m
j:= t
x:= div (A (m + t), 2)
нц
нц покаA[i] < x
i:=i+1
кц
нц покаA[j] > x
j:=j-1
кц
еслиi <= j
то
w:= A[i Билет №4. Понятие сортировки.]
A[i]:= A[j]
A[j]:= w
i:= i+1
j:= j-1
все
кц покаi > j;
еслиm < j
тоQuickSort (m, j);
все
еслиi < t
тоQuickSort (i, t);
все
кон
Оценим эффективность способа. Представим, что размер массива равен числу, являющемуся степенью двойки, и при каждом разделении элемент X находится точно посреди массива. В данном Билет №4. Понятие сортировки. случае при первом просмотре производится N сравнений и массив делится на две части размерами » N/2 сравнений и т.д. как следует,
C = N + 2 × (N / 2) + 4 × (N / 4) + … + N × (N / N) = O(N ×log2N).
Внутреннее слияние
Основой процесса слияния является базовая мысль упорядочения данных методом чередования частей из 2-ух либо более Билет №4. Понятие сортировки. упорядоченных списков. Упорядоченное объединение этих списков представляет собой окончательный упорядоченный перечень из 10 частей. Сравниваются меньшие элементы каждой части и наименьшей из их продвигается в перечень вывода. Процесс сопоставления частей, продвижения наименьшего в перечень вывода и выбор преемника в «победившей» части длится до того времени, пока не исчерпывается одна из Билет №4. Понятие сортировки. частей. После того как одна часть исчерпана, все оставшиеся элементы другой пересылаются в перечень вывода.
АлгSl (арг цел k, m, q, цел таб A [1:N])
нач целk, i, j, t, цел таб A [1:N]
i:= k
j:= m +1
t:= 1
нц пока(i <= m) и(j <= q)
еслиA[i Билет №4. Понятие сортировки.] <= A[j] то
D[t]:=A[i]
i:= i +1
по другому
D[t]:= A[j]
j:= j +1
t:= t +1
все
кц
нц покаi = m
D[t]:= A[i]
i:= i +1
t:= t +1
нц покаj:= q
D[t]:= A[j]
j:= j +1
t:= t +1
кц
кц
нц дляi от 1 доt – 1
A [k + i – 1]:= D Билет №4. Понятие сортировки.[i]
кц
кон
Эффективность метода составляет C = O (N×log2N).


biletnapravlennost-lichnost-.html
bili-li-sredi-vashih-rodstvennikov-uchastniki-velikoj-otechestvennoj-vojni-esli-bili-to-znaete-li-vi-kakie-libo-podrobnosti-ih-zhizni-v-godi-vojni.html
bili-podgotovleni-k-publikacii-vo-vnutrennej-seti-ic-fgbu-vgnki-i-dlya-razmesheniya-na-zakritoj-chasti-sajta-fgbu-vgnki-dokumentirovannie-proceduri-i-vnutrennie-proceduri.html