Remkomplekty.ru

IT Новости из мира ПК
2 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Сортировка простыми вставками паскаль

Сортировка простыми вставками паскаль

Алгоритмы сортировки массивов

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

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

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

Алгоритмы и программы сортировки

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

Procedure Puzirek;
Var i, j: Integer;
y:Integer;
Begin
For i := 2 to n do
For j := n downto i do
If X[j-1] > X[j] then begin y:=X[j-1];
X[j-1]:=X[j];
X[j]:=y
end;
End;

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

Procedure Vstavka;
Var Z, Y, i, j: Integer;
Begin
For i := 2 to n do
For j := 1 to i-1 do
If X[j] > X[i] then
begin
Z := X[i];
For Y := i downto j+1 do X[Y] := X[Y-1];
X[j] := Z
end
End;

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

Procedure Vibor;
Var r, i, j: Integer;
Begin
For i := 1 to n-1 do
begin
r := i;
For j := i+1 to n do If a[r] > a[j] then r := j;
Y:=a[r]; a[r]:=a[i]; a[i]:=Y;
end
End;

Сортировка простыми вставками паскаль

Простые и улучшенные методы упорядочения данных.

Содержание

Задача сортировки

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

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

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

Методы упорядочения подразделяются на внутренние (обрабатывающие массивы) и внешние (занимающиеся только файлами) 1 .

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

Простые сортировки

К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных. Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N 2 действий, где С — некоторая константа.

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

Как правило, сложность алгоритмов подсчитывают раздельно по количеству сравнений и по количеству перемещений данных в памяти (пересылок), поскольку выполнение этих операций занимает различное время. Однако точные значения удаётся найти редко, поэтому для оценки алгоритмов ограничиваются лишь понятием «пропорционально», которое не учитывает конкретные значения констант, входящих в итоговую формулу. Общую же эффективность алгоритма обычно оценивают «в среднем»: как среднее арифметическое от сложности алгоритма «в лучшем случае» и «в худшем случае», то есть (Eff_best + Eff_worst) / 2.

Сортировка простыми вставками

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

Алгоритм ПрВст

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

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

— записать новый элемент на освободившееся место.

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

Реализация алгоритма ПрВст

Метод прямых вставок с барьером (ПрВстБар)

Для того, чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний var ) и будем записывать в неё поочерёдно каждый вставляемый элемент (сравните строки <*>и <**>в приведённых вариантах программы). В тех случаях, когда вставляемое значение окажется меньше, чем a[1], компонента a[0] будет работать как «барьер», не дающий индексу j выйти за нижнюю границу массива. Кроме того, компонента a[0] может заменить собою и дополнительную переменную х:

Эффективность алгоритма ПрВстБар

Понятно, что для этой сортировки наилучшим будет случай, когда на вход подаётся уже упорядоченная последовательность данных. Тогда алгоритм ПрВстБар совершит N-1 сравнение и 0 пересылок данных.

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

N 2 (читается «порядка эн квадрат») по обоим параметрам.

Пример сортировки

Предположим, что нужно отсортировать следующий набор чисел:

Выполняя алгоритм ПрВстБар, мы получим такие результаты (подчёркнута уже отсортированная часть массива, полужирным выделена сдвигаемая последовательность, а квадратиком выделен вставляемый элемент):

0 шаг: 5343621
1 шаг: 5 343621 1 1+1 3 1+2 4
2 шаг: 35 43621 1 1+1 1+2
3 шаг: 345 3621 2 2+1 2+2
4 шаг: 3345 621 0 1 0
5 шаг: 33456 21 5 5+1 5+2
6 шаг: 233456 1 6 6+1 6+2
Результат: 1233456 15 20 25

Сортировка бинарными вставками

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

Пусть, к примеру, нужно найти место для элемента 7 в таком массиве:

Найдём средний элемент этой последовательности (10) и сравним с ним семёрку. После этого всё, что больше 10 (да и саму десятку тоже), можно смело исключить из дальнейшего рассмотрения:

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

Итак, отсечём половину последовательности:

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

Из приведенных примеров уже видно, что поиск ведётся до тех пор, пока левая граница не окажется правее(!) правой границы. Кроме того, по завершении этого поиска последней левой границей окажется как раз тот элемент, на котором необходимо закончить сдвиг «хвоста» последовательности.

Будет ли такой алгоритм универсальным? Давайте проверим, что же произойдёт, если мы станем искать позицию не для семёрки или девятки, а для единицы:

Как видим, правая граница становится неопределённой — выходит за пределы массива. Будет ли этот факт иметь какие–либо неприятные последствия? Очевидно, нет, поскольку нас интересует не правая, а левая граница.

«А что будет, если мы захотим добавить 21?» — спросит особо въедливый читатель. Проверим это:

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

Вспомним, однако, что в реальности на (N + 1)–й позиции как раз и находится вставляемый элемент (21). Таким образом, если левая граница вышла за рассматриваемый диапазон, получается, что ничего сдвигать не нужно. Вообще же, такие действия выглядят явно лишними, поэтому от них стоит застраховаться, введя одну дополнительную проверку в текст алгоритма.

Реализация алгоритма БинВст

Эффективность алгоритма БинВст

Теперь на каждом шаге выполняется не N, а log N проверок 5 , что уже значительно лучше (для примера, сравните 1000 и 10 = log 1024). Следовательно, всего будет совершено N*log N сравнений. Впрочем, улучшение это не слишком значительное, ведь по количеству пересылок наш алгоритм по–прежнему имеет сложность «порядка N 2 ».

Сортировка простым выбором

Попробуем теперь сократить количество пересылок элементов.

Алгоритм ПрВыб

На каждом шаге (всего их будет ровно N — 1) будем производить такие действия:

  1. найдём минимум среди всех ещё не упорядоченных элементов;
  2. поменяем его местами с первым «по очереди» не отсортированным элементом. Мы надеемся, что читателям очевидно, почему к концу работы этого алгоритма последний (N–й) элемент массива автоматически окажется максимальным.

Реализация ПрВыб

Эффективность алгоритма ПрВыб

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

Таким образом, алгоритм ПрВыб имеет квадратичную сложность (

N 2 ) по сравнениям и линейную (

N) — по пересылкам.

Замечание. Если перед вами поставлена задача отсортировать строки двумерного массива (размерности NxN) по значениям его первого столбца, то сложность алгоритма ПрВыб, модифицированного для решения этой задачи, будет квадратичной (N 2 сравнений и N 2 пересылок), а алгоритма БинВст — кубической (N*log N сравнений и N 3 пересылок). Комментарии, как говорится, излишни.

Пример сортировки

Предположим, что нужно отсортировать тот же набор чисел, при помощи которого мы иллюстрировали метод сортировки простыми вставками:

Теперь мы будем придерживаться алгоритма ПрВыб (подчёркнута несортированная часть массива, а квадратиком выделен её минимальный элемент):

1 шаг: 5343621
2 шаг: 1 343625
3 шаг: 12 43635 <***>6
4 шаг: 123 3645 <ничего не делаем>
5 шаг: 1233 645
6 шаг: 12334 65
результат: 1233456

Сортировка простыми обменами

Рассмотренными сортировками, конечно же, не исчерпываются все возможные методы упорядочения массивов.

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

Тем же, кто всё-таки желает ознакомиться с обменными сортировками, а также с подробными данными по сравнению различных сортировок, мы рекомендуем труды Д. Кнута 7 или Н. Вирта 8 .

12. Методы сортировки массивов

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

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

Мы рассмотрим только три простейшие схемы сортировки.

Метод «пузырька»

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

В результате наибольший элемент оказывается в самом верху массива.

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

Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее «всплывшие» элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j -го прохода не проверяются элементы, стоящие на позициях выше j .

Теперь можно привести текст программы упорядочения массива M[1..N] :

Стандартная процедура swap будет использоваться и в остальных алгоритмах сортировки для перестановки элементов (их тип мы уточнять не будем) местами:

procedure swap (var x,y: . );
var t: . ;
begin
t := x;
x := y;
y := t
end;

Заметим, что если массив M — глобальный, то процедура могла бы содержать только аргументы (а не результаты). Кроме того, учитывая специфику ее применения в данном алгоритме, можно свести число парметров к одному (какому?), а не двум.

Применение метода «пузырька» можно проследить здесь.

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

Второй метод называется метод вставок ., т.к. на j -ом этапе мы «вставляем» j -ый элемент M[j] в нужную позицию среди элементов M[1] , M[2] ,. . ., M[j-1] , которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены.
Сказанное можно записать следующим образом:

нц для j от 2 до N
переместить M[j] на позицию i = M[i-1], либо i=1
кц

Чтобы сделать процесс перемещения элемента M[j] , более простым, полезно воспользоваться барьером: ввести «фиктивный» элемент M[0] , чье значение будет заведомо меньше значения любого из «реальных»элементов массива (как это можно сделать?). Мы обозначим это значение через —оо.

Если барьер не использовать, то перед вставкой M[j] , в позицию i-1 надо проверить, не будет ли i=1 . Если нет, тогда сравнить M[j] ( который в этот момент будет находиться в позиции i ) с элементом M[i-1].

Описанный алгоритм имеет следующий вид:

Сортировка посредством выбора

Идея сортировки с помощью выбора не сложнее двух предыдущих. На j -ом этапе выбирается элемент наименьший среди M[j] , M[j+1] ,. . ., M[N] (см. процедуру FindMin ) и меняется местами с элементом M[j] . В результате после j -го этапа все элементы M[j] , M[j+1] ,. . ., M[N] будут упорядочены.

Сказанное можно описать следующим образом:

нц для j от 1 до N-1
выбрать среди M[j] ,. . ., M[N] наименьший элемент и
поменять его местами с
M[j]
кц

В программе, как уже было сказано, используется процедура FindMin , вычисляющая индекс lowindex элемента, наименьшего среди элементов массива с индексами не меньше, чем startindex :

procedure FindMin (start index : integer; var lowindex : integer );
var lowelem: . ;
u: integer;
begin
lowindex := start index ;
lowelem := M[startindex];
for u:= start index +1 to N do
if M[u]

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

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

Таким образом, формально, находится правильное место для вставки (например, сортировка карточек в библиотеке). Этот алгоритм будет иметь следующую последовательность шагов.

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

2. Шаг итерации. Для всех последующих элементов со второго по n-1, очередной элемент i сравнивается со всеми предыдущими элементами от 0 до (i-1), пока текущий элемент i меньше или равен предыдущему. После этого будет найдена позиция для вставки или будет достигнуто начало списка. После этого элемент вставляется в найденную позицию.

3. Шаг выхода. Шаг итерации продолжается до тез пор, пока не будут просмотрены все элементы массива.

Пусть дан следующий массив:

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

.

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

Блок-схема алгоритма сортировки вставками имеет вид:

Реализовать данный алгоритм на языке С++ можно следующим образом:

template

void InsertSort(T *A, const int n)

int j;

for (int i = 1; i 0 && Temp ScanDown, то это означает, что каждый элемент находится в своем подсписке и их переставлять друг с другом нет необходимости. В противном случае элементы переставляются местами.

3. Шаг выхода. Шаг итерации выполняется до тех пор, пока ScanDown не станет меньше ScanUp. Это означает, что весь список разделен на две части: со значениями меньшими или равными серединному элементу и со значениями большими серединного элемента. Их разделяет позиция индекса ScanDown. После этого серединный элемент в нулевой позиции и элемент с индексом ScanDown переставляются местами.

4. Шаг рекурсии. Шаги 1-3 повторяются для левого подсписка с элементами от low до ScanDown-1 и правого – от ScanDown+1 до high до тех пор, пока список не останется пустым или одноэлементным.

Пусть исходный массив имеет вид:

Рекурсия продолжается пока не будет одноэлементный список или пустой.

Анализ вычислительной сложности в общем случае затруднен. Если исходный массив можно представить в виде бинарного дерева, то в общем случае необходимо будет осуществить рекурсивных вызовов. Для каждого из этих вызовов, на первом необходимо просмотреть n элементов находящихся в двух подсписках. Среднее число сравнений будет . На второй итерации надо будет просмотреть 4 подсписка. В каждом из которых нужно сделать сравнений. Общее число будет . Таким образом, затраты будут пропорциональны . Если массив отсортирован по возрастанию или убыванию, вычислительные затраты не изменяются. Наихудший случай появляется, когда в каждом подсписке серединный элемент оказывается максимальным или минимальным. Тогда один из подсписков будет оставаться пустым, а во втором подсписке будут находиться всегда n элементов. В этом случае преимущество «быстрой сортировки» исчезает и появляется обычная сортировка выборкой, затраты которой . Таким образом, в патологическом случае затраты станут пропорциональны .

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

Блок-схема алгоритма быстрой сортировки имеет следующий вид:

Реализовать данный алгоритм на языке С++ можно следующим образом:

template

void QuickSort(T *A, const int low, const int high)

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

Задача сортировки

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

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

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

Методы упорядочения подразделяются на внутренние (обрабатывающие массивы) и внешние (занимающиеся только файлами ) 1 Более подробную информацию о различных алгоритмах упорядочения смотрите в книге Дональда Кнута » Искусство программирования ЭВМ», том 3: «Сортировка и поиск». .

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

Простые сортировки

К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных. Иными словами, при сортировке массива , состоящего из N компонент , такие алгоритмы будут выполнять С*N 2 действий, где С — некоторая константа.

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

Как правило, сложность алгоритмов подсчитывают раздельно по количеству сравнений и по количеству перемещений данных в памяти (пересылок), поскольку выполнение этих операций занимает различное время. Однако точные значения удается найти редко, поэтому для оценки алгоритмов ограничиваются лишь понятием «пропорционально», которое не учитывает конкретные значения констант, входящих в итоговую формулу. Общую же эффективность алгоритма обычно оценивают «в среднем»: как среднее арифметическое от сложности алгоритма «в лучшем случае» и «в худшем случае», то есть (Eff_best + Eff_worst)/2.

Сортировка простыми вставками

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

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

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

— записать новый элемент на освободившееся место.

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

Реализация алгоритма ПрВст

Метод прямых вставок с барьером (ПрВстБар)

Для того чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний var) и будем записывать в нее поочередно каждый вставляемый элемент (сравните строки <*>и <**>в приведенных вариантах программы). В тех случаях, когда вставляемое значение окажется меньше, чем a[1], компонента a[0] будет работать как «барьер», не дающий индексу j выйти за нижнюю границу массива. Кроме того, компонента a[0] может заменить собою и дополнительную переменную х:

Эффективность алгоритма ПрВстБар

Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная последовательность данных. Тогда алгоритм ПрВстБар совершит N-1 сравнение и 0 пересылок данных.

В худшем же случае — когда входная последовательность упорядочена «наоборот» — сравнений будет уже (N+1)*N/2, а пересылок (N-1)*(N+3). Таким образом, этот алгоритм имеет сложность

N 2 (читается «порядка эн квадрат») по обоим параметрам.

Предположим, что нужно отсортировать следующий набор чисел:

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

Сортировка бинарными вставками

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

Пусть, к примеру, нужно найти место для элемента 7 в таком массиве:

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

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

Итак, отсечем половину последовательности:

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

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

Будет ли такой алгоритм универсальным? Давайте проверим, что же произойдет, если мы станем искать позицию не для семерки или девятки, а для единицы:

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

«А что будет, если мы захотим добавить 21?» — спросит особо въедливый читатель. Проверим это:

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

Вспомним, однако, что в реальности на (N+1)-й позиции как раз и находится вставляемый элемент (21). Таким образом, если левая граница вышла за рассматриваемый диапазон, получается, что ничего сдвигать не нужно. Вообще же такие действия выглядят явно лишними, поэтому от них стоит застраховаться, введя одну дополнительную проверку в текст алгоритма.

Реализация алгоритма БинВст

Эффективность алгоритма БинВст

Теперь на каждом шаге выполняется не N, а log N проверок 5 Напомним, что log N означает log2 N , что уже значительно лучше (для примера, сравните 1000 и 10 = log 1024). Следовательно, всего будет совершено N*log N сравнений. Впрочем, улучшение это не слишком значительное, ведь по количеству пересылок наш алгоритм по-прежнему имеет сложность «порядка N 2 «.

Сортировка простым выбором

Попробуем теперь сократить количество пересылок элементов.

На каждом шаге (всего их будет ровно N-1) будем производить такие действия:

  1. найдем минимум среди всех еще не упорядоченных элементов;
  2. поменяем его местами с первым «по очереди» не отсортированным элементом. Мы надеемся, что читателям очевидно, почему к концу работы этого алгоритма последний (N-й) элемент массива автоматически окажется максимальным.

Эффективность алгоритма ПрВыб

В лучшем случае (если исходная последовательность уже упорядочена), алгоритм ПрВыб произведет (N-1)*(N+2)/2 сравнений и 0 пересылок данных. В остальных же случаях количество сравнений останется прежним, а вот количество пересылок элементов массива будет равным 3*(N-1).

Таким образом, алгоритм ПрВыб имеет квадратичную сложность (

N 2 ) по сравнениям и линейную (

N) — по пересылкам.

Замечание. Если перед вами поставлена задача отсортировать строки двумерного массива (размерности NxN) по значениям его первого столбца, то сложность алгоритма ПрВыб, модифицированного для решения этой задачи, будет квадратичной (N 2 сравнений и N 2 пересылок), а алгоритма БинВст — кубической (N*log N сравнений и N 3 пересылок). Комментарии, как говорится, излишни.

Предположим, что нужно отсортировать тот же набор чисел, при помощи которого мы иллюстрировали метод сортировки простыми вставками:

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

Сортировка простыми обменами

Рассмотренными сортировками, конечно же, не исчерпываются все возможные методы упорядочения массивов.

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

Тем же, кто все-таки желает ознакомиться с обменными сортировками, а также с подробными данными по сравнению различных сортировок, мы рекомендуем труды Д. Кнута 7 Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск (любое издание). или Н. Вирта 8 Н. Вирт. Алгоритмы и структуры данных (любое издание). .

Читать еще:  Цикл for to do паскаль
Ссылка на основную публикацию
Adblock
detector