Алгоритм

Постановка задачи

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

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

Алгоритм

Положить R = N

Найти наибольший элемент в массиве A[1..R]. Его место обозначим через IMAX

1. Если IMAX ¹ R и A[IMAX] ¹A[R], то поменять местами элементы A[IMAX] иA[R]

2. Передвинуть границы упорядоченной и неупорядоченной частей массива:
R = R – 1. Первые R элементов будут образовывать неупорядоченную часть массива. Последние (N – R) элементов – упорядоченную по возрастанию часть массива.

3. Если R = 1, то алгоритм окончен, иначе перейти к шагу 2.

Внешний цикл выполняется (N-1) раз, а внутренний цикл в среднем выполняется N/2 раз. Это значит, что число сравнений для сортировки выбором равно 1/2 (N²-N) и эта сортировка будет выполняться слишком медленно для большого числа элементов.

Алгоритм сортировки имеет квадратичную сложность (O(N²)) относительно операций сравнения и линейную сложность (O(N)) относительно операций перестановки. Сортировка вставками

Алгоритм

Массив разделяется на две части: отсортированную и не отсортированную. Элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве не отсортированной – все остальные.

Словесный алгоритм метода

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

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

процесс повторяется до тех пор, пока все элементы не будут упорядочены.

Для алгоритма верны следующие оценки:

Количество сравнений	Количество присваиваний
В любом случае 1+2+3+…+(N–1) =N(N–1)/2 (для реализации бинарного поиска 1+2+[log23]+1+[log24]+1+…+ +[log2(N–1)]+1+)»N log2N)	минимальное	максимальное
	3+4+5+…+N+1= =(N+4)(N–1)/2

Сортировка «пузырьком”

Алгоритм

(Идея: Представим, что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков, проход начинается "снизу")

Алгоритм начинается со сравнения 1-го и 2-го элементов массива. Если элементы расположены не по порядку, то они меняются местами. Этот процесс повторяется со 2-м и 3-м, 3-м и 4-м и т.д. элементами, пока пара (N–1)-й и N-й элемент не будет обработана. За один просмотр массива самый большой элемент встанет на старшее N-е место. Далее алгоритм повторяется, причем на P-м просмотре уже только первые (N-P) элементов сравниваются со своими правыми соседями. Если при очередном проходе перестановок не было или p=n, то алгоритм окончен.

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

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

В общем случае верны следующие оценки:

Количество сравнений	Количество присваиваний
минимальное	максимальное	минимальное	максимальное
(N–1)	(N–1)+(N–2)+(N–3)+…+1= =N(N–1)/2		3(N–1+N–2+N–3+…+1)= =3N(N-1)/2

Алгоритм имеет квадратичную сложность O(N²)

Дата добавления: 2015-08-05