Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Алгоритм

Читайте также:
  1. Аксиомы алгоритма «Razoom».
  2. Алгоритм N 1
  3. Алгоритм N 2
  4. Алгоритм введения и изменения заряда точки привязки
  5. Алгоритм выполнения задания
  6. Алгоритм вычисления коэффициента корреляции Пирсона в программе Ехсе1

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

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

 

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

Алгоритм

Положить 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 (N2-N) и эта сортировка будет выполняться слишком медленно для большого числа элементов.

 

Алгоритм сортировки имеет квадратичную сложность (O(N2)) относительно операций сравнения и линейную сложность (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(N2)


Дата добавления: 2015-08-05; просмотров: 195 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Алгоритмы неустойчивой сортировки| Измерение массы тела на чашечных медицинских весах.

mybiblioteka.su - 2015-2020 год. (0.006 сек.)