Список литературы

программирования для ЭВМ», том 1 и 3, 1976-78.
3. Т.Кормен, Ч.Лейзерсон,

Р.Ривест. «Алгоритмы: построение и анализ», 2001,2004,2009,2011.
4. Р.Седжвик. «Фундаментальные алгоритмы
на С++», 2002.
5. Е.В.Курапова, Е.П.Мачикина. «Структуры и алгоритмы обработки данных», 2006.
6. Е.В.Курапова, Е.П.Мачикина. «Основные методы кодирования данных», 2010.

информатики,
известный теоретик в области разработки языков программирования,
профессор компьютерных

наук.
Участвовал в разработке языков ALGOL68 и PL/360
Разработал языки Паскаль и Модула-2
8,

в разных странах, иностранный член Российской академии наук,
преподаватель и идеолог

программирования,
автор 19 монографий.

первое место.
Среди оставшихся элементов (начиная со второго) находим наименьший

элемент и переставляем его на второе место в массиве.
Среди оставшихся элементов (начиная с третьего) находим наименьший элемент и переставляем его на третье место
и т. д. сколько раз???

... n-1)
k := i
DO ( j := i+1, i+2,… ,n

)
IF ( aj < ak ) k := j FI
OD
ai <--> ak
OD

П О В

А
А У Р К П О В А
А А Р К П О В У
А А В К П О Р У
А А В К П О Р У
А А В К О П Р У
А А В К О П Р У
А А В К О П Р У

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

и сравнений.
1) По количеству пересылок: на каждой итерации старшего

цикла выполняется один обмен (3 пересылки).
M = 3(n-1)
2) По количеству сравнений можем сказать:
когда i=1 требуется (n-1) сравнение,
когда i=2 требуется (n-2) сравнения, и т.д.
Суммируя, получим:
С = (n-1) + (n-2) + (n-3) + … + 1
С = 1 + 2 + 3 + … + (n-1)
2С = n + n + n + … + n
2С = n (n-1)

C =

Трудоемкость метода SelectSort

элементы массива.
Для удобства реализации алгоритмов на Си массив можно описывать

следующим образом:
int A [ 1+n ];
Тогда при заполнении и выводе массива элемент А[0] не используется.
Для метода прямого выбора SelectSort:
Значения М и С не зависят от исходной упорядоченности массива.
Сортировка не устойчива.
Пример:
3’ 3” 2 -> 2 3” 3’

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

функций.
Определение.
Функция f(x) асимптотически доминирует
над функцией g(x) или g(x) = O ( f(x) ),
если |g(x)| ≤ const |f(x)| при x→∞.
Примеры:
1) g(x) = 10х f(x) = х
2) g(x) = 1 f(x) = x
3) g(x) = 2х f(x) = х2

f1 , f2 и константы k справедливы свойства:
f = O(f)
O

(k*f) = O (f)
O (f1+f2) = O (f1) +O (f2)
Пример: T = 10n + 20
T = O(10n+20) = O(10n) + O(20) = O(n) +O(1) = O(n),
при n→ ∞.
Приведем ряд доминирования основных функций
O(1) < O(log n) < O(n) < O(n log n) < O(na) < O(an) <
< O(n!) < O(nn) , при n→∞, a >1.

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

Если правый элемент будет меньше, чем левый, то поменяем их местами.
При первом проходе наименьший элемент переместится на первое место. При втором проходе наименьший элемент из оставшихся “всплывёт” на второе место, и т.д.
Через (n-1) итерацию массив будет отсортирован.

индекс правого элемента в текущей паре.

DO (i := 1, 2, ... n-1)
DO (j := n, n-1, ... i+1)
IF (aj < aj-1) aj↔aj-1 FI
OD
OD

П О В

А
А В
А О
А П
А А
А Р
А У
А К
А К У Р А П О В
В О
В П
А В
А Р
А У
А К

А А К У Р В П О
О П
В О
В Р
В У
В К
А А В К У Р О П
О П
О Р
О У
К О
А А В К О У Р П
П Р
П У
О П

О П У

Р
Р У
П Р
А А В К О П Р У
Р У
А А В К О П Р У

А А В К О П Р У