Квадратичные и субквадратичные алгоритмы — КиберПедия 

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

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...

Квадратичные и субквадратичные алгоритмы

2018-01-04 166
Квадратичные и субквадратичные алгоритмы 0.00 из 5.00 0 оценок
Заказать работу

Сортировка выбором(SelectSort)
Сортировка пузырьком(BubbleSort) и ее улучшения
Сортировка простыми вставками(InsertSort)
Cортировка Шелла (ShellSort)

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

Изображенный ниже график иллюстрирует разницу в эффективности изученных алгоритмов.

  • коричневая линия: сортировка пузырьком;
  • синяя линия: шейкер-сортировка;
  • розовая линия: сортировка выбором;
  • желтая линия: сортировка вставками;
  • голубая линия: сортировка вставками со сторожевым элементом;
  • фиолетовая линия: сортировка Шелла.

Логарифмические и линейные алгоритмы

Пирамидальная сортировка (HeapSort)
Быстрая сортировка(QuickSort)
Поразрядная сортировка(Radix sort)

 

Простой выбор

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

На Рис. 2 этот метод отображен для последовательности прямоугольников разной высоты. Два первых элемента уже упорядочены. Затем отыскивается минимальный среди остальных. Если элементы в последовательности могут быть равными, то отыскивается первый (I) среди минимальных (таким образом достигается устойчивость сортировки). Он меняется местами с третьим.

Для составления алгоритма решения этой задачи воспользуемся, как обычно, методом пошаговой детализации. Обратим внимание на то, что для получения результата нам нужно N-1 раз находить минимальное значение в таблице, длина которой уменьшается и определяется тем, в который раз мы приступили к поиску минимума. Так, в 1-й раз мы ищем минимум среди элементов A1, A2,..., AN, во 2-й - среди A2,..., AN, в i-й - среди Ai,...,AN. И еще один важный момент. Поскольку после нахождения минимального элемента его нужно будет поменять местами с другим элементом таблицы, то нужно запомнить номер минимального. Следовательно, первый шаг детализации можно представить таким оператором цикла:

I:= 1
пока I<=N-1
нц найти минимальный элемент и его номер в таблице Ai,..., АN (1)
поменять местами Аi и минимальный элемент (2)
I:= I+1
кц

Еще раз приведем разработанный ранее алгоритм поиска минимума.

1. K:= I; X:= A[I]; J:= I+1
пока J<=N
нцесли A[J]<X
то X:= A[J];K:= J
все
кц

После выполнения этих действий значением переменной Х будет значение минимального среди элементов Ai,...,AN, а значением К - номер этого элемента. Следовательно, пункт 2 можно записать конкретнее:

поменять местами элементы A1 и AK (2)

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

2. C:= A[I]; A[I]:= A[K]; A[K]:= C.

Заметим, однако, что в нашей конкретной ситуации эта третья переменная не нужна, так как ее роль играет переменная Х из пункта 1:

2. A[K]:= A[I]; A[I]:= X.

Мы сэкономили одно присваивание, но это немало, так как действия выполняются в цикле многократно.

Теперь можно записать полностью алгоритм сортировки простым выбором.

алг ВЫБОР(цел N, вещтаб A[1:N])
арг A, N
рез A
начвещ X, цел I, J, К
I:= 1
пока I<=N-1
нц K:= I; X:= A[I]; J:= I+1
пока J<=N
нцесли A[J]<X
то X:= a[J];K:= J
все
J:= J+1
кц
A[K]:= A[I]; A[I]:= X;
I:= I+1
кц
кон

На языке Паскаль оформим этот алгоритм в виде процедуры. Параметрами ее будут массив и его длина.

const m = 10;type mass = array [l..m] of real;procedure selec(n:integer; var a:mass);var i,j,k: integer; x: real;beginfor i:= 1 to n-1 dobegin k:= i; x:= a[i]; for j:= i+l to n do if a[j] < x then begin x:= a[j]; k:= j end; a[k]:= a[i]; a[i]:= xendend;

 

Простой обмен

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

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

Номер элемента          
Значение элемента          

Будем просматривать ее от конца к началу (в принципе это не обязательно, можно организовать и обычный просмотр от начала к концу). Сравним 4-й и 5-й элементы. Они расположены не в порядке возрастания, поменяем их местами. Теперь значением 4-го элемента будет 3, а 5-го - 12. Сравним далее 3-й и 4-й элементы. Их оставим на месте. Сравнение 2-го и 3-го элементов показывает, что их нужно переставить. Теперь значение 2-го элемента - 1. И, наконец, сравним 1-й и 2-й элементы. Их тоже нужно поменять местами. Таким образом, получим:

Номер элемента          
Значение элемента          

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

Если вообразить себе, что элементы таблицы - это пузырьки в резервуаре с водой, каждый весом, равным своему значению (что и изображено на Рис. 2), то каждый проход с обменами по таблице приводит к "всплыванию пузырька" на соответствующий его весу уровень. Благодаря такой аналогии сортировка простым обменом получила название сортировки методом "пузырька". В примере на Рис. 2 первые два элемента последовательности уже упорядочены и "всплывает" третий элемент. Знак <= (а не <) показывает условие прекращения сравнений, именноэтим достигается устойчивость сортировки "пузырьком".

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

I:= 2
пока I <= N
нц сравнить попарно элементы АN, АN-1,..., АII-1 1
I:= I+1
кц

Разберем более детально пункт 1. Для попарного сравнения элементов нужен оператор цикла с границей, зависящей от I, так как при каждом новом проходе по таблице длина ее будет уменьшаться.

J:= N
пока J<=I
нц сравнить aj и aj-iи при необходимости поменять их местами 1.1
J:= J-1
кц

Пункт 1.1. уже легко записать в виде условного оператора:

1.1 если A[J-1]>A[J]
то X:= A[J-l]; A[J-1]:= A[J];A[J]:= X
все

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

алг ОБМЕН(цел N, вещтаб A[1:N])
арг N, А
рез А
начцел
I, J, вещ Х
I:= 2
пока I<=N
нц J:= N
пока J>=I
нцесли A[J-1]>A[J]
то X:= A[J-1]
A[J-1]:= A[J]
A[J]:= X
все
J:= J-1
кц
I:= I+1
кц
кон

В паскале

const m = 10;type mass = array [l..m] of real;procedure bubble(var a:mass; n:integer);var i,j: integer; x: real;begin for i:= 2 to n do for j:= n downto 1 do if a[j - 1] > a[j] then begin x:= a[j - 1]; a[j - 1]:= a[j]; a[j]:= x endend;

 

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

Пусть в заданной последовательности а1, А2,..., АN первые I-1 элементов уже отсортированы. Найдем в этой части последовательности место для I-го элемента. Для этого будем сравнивать его по порядку со всеми элементами, стоящими левее, до тех пор пока не окажется, что некоторый АK<= аI. Затем сдвинем часть последовательности АK+1, АK+2,..., АI-1 на один элемент вправо и освободимтаким образом место АK+1для элемента АI, куда его и поставим. Эта последовательность действий отображена на Рис. 2 при упорядочивании последовательности треугольников разной высоты. Считая, что первые три элементауже упорядочены, ищем место для четвертого по вышеизложенному правилу. Знак <= (а не <) показывает, когда нужно прекратить сравнения, т. е. движение влево по последовательности. При этом достигается устойчивость сортировки вставками.

После того как мы проделаем подобные действия для всех элементов от 2-го до N-го, мы получим отсортированную последовательность.Отметим очень важную деталь в наших действиях. Когда мы проводим сравнение I-го элемента со всеми, стоящими левее него, может оказаться, что не найдется такого Ак, что АK<= аI; это произойдет, если АI меньше всех левых элементов. На Рис. 2 эта ситуация отмечена дорожным знаком "Прочие опасности". В этом случае нужно закончить просмотр (по достижении первого элемента последовательности) и осуществить сдвиг A1,..., AI-1 вправо, а элемент AI поставить на первое место.

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

I:= 2;
пока I <= N
нц найти место Ак для АI, в упорядоченной части последовательности (1)
сдвинуть элементы Ак+1, Ак+2,:, Ai-1 вправо (2)
поставить элемент АI на нужное место (3)
I:= I+1
кц

В результате действия 1 мы должны получить номер К, индекс элемента, рядом с которым справа нужно поставить АI.

Чтобы найти место для АI, нужно сравнивать его последовательно со всеми левыми соседями до элемента АK<= аI и, если такового не окажется, остановиться на первом элементе. Действия эти - циклические, причем удобнее оформить цикл по текущему номеру элемента. Получим:

1 инициализация цикла (1.1)
пока J>0
нц сравнить элементы аI и aJ (1.2)
кц

Обдумывая пункт 1.1 - инициализацию цикла, мы должны предусмотреть три момента. Во-первых, значение элемента аI; нужно запомнить, так как иначе при сдвиге оно может потеряться. Во-вторых, нужно зафиксировать номер I-1 - с этого элемента начнется сравнение. В-третьих, нужно позаботиться о том, чтобы в ситуации, когда аI, меньше A1, A2..., AI-1, он смог встать на первое место. Следовательно, получаем:

1.1 X:= A[I]; J:= I-1; K:= 1

Далее, по результатам сравнения аI, и aJ мы должны сделать вывод о том, продолжать сравнение или нужный элемент уже найден и пора закончить цикл. Закончить цикл можно присваиванием переменной J нулевого значения. Имеем:

1.2 если A[I] >= A[J]
то K:= J+1; J:= 0
иначе J:= J-1
все

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

2. J:= I
пока J>K
нц A[J]:= A[J-1]
J:= J-1
кц

Пункт 3 - это один оператор присваивания:

3. A[K]:= X

И наконец, законченный алгоритм сортировки простыми вставками.
алг ВСТАВКА (цел N, вещтаб A[1:N])
арг A, N
рез A
начцел I, J, K, вещ X
I:= 2
пока I <= N
нц X:= A[I]; J:= I-1; K:= 1
пока J>0
нцесли A[I] >= A[J]
то K:= J+1; J:= 0
иначе J:= J-1
все
кц

J:= I
пока J>K
нц A[J]:= A[J-1]
J:= J-1
кц
A[K]:= X;
I:= I+1
кц
кон

На паскале

Program SortByVstavka;var A: array of Integer;i, j, key: Integer;begin//Заполняем массив Afor i:= 0 to Length(A) - 1 dobegin key:= A[i]; j:= i - 1; while (j >= 0) and (A[j] > key) do begin A[j + 1]:= A[j]; j:= j - 1; A[j + 1]:= key; end;end;End.

 

Найти номер минимального элемента последовательности (все элементы разные). const m = 10;type mass = array [1..m] of real;procedure nommin (x:mass; n:integer; var nom:integer);var i: integer; min: real;begin min:= x[i]; nom:= 1;for i:= 2 to n do if min > x[i] then begin min:= x[i]; nom:= i endend;

Поделиться с друзьями:

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...

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

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

Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.032 с.