Методы сортировок и их реализации. Беляева И.В - 20 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

Очевидно,
цикл
for
в
функции
selectionSort
выполняется
n-l
раз.
Таким
образом,
функция
selectionSort
n-l
раз
вызывает
функции
indexOfLargest
и
swap.
При
каждом
вызове
функции
indexOfLargest
ее
цикл
выполняется
last
раз
(т.е.
size-l
раз,
где
size
равно
last+l).
Итак,
при
n-l
вызове
функции
indexOf
Largest
для
значений
переменной
last
от
n-l
до
1
общее
количество
итераций
цикла
равняется
(n-l
)+(n-2)+ ... +1
==
n*(n-l )/2.
Поскольку
при
каждой
итерации
в
функции
indexOf
Largest
выполняется
одно
сравнение,
их
общее
количество
равно
n*(n-l )/2.
В
результате
для
n-l
вызова
функции
swap
выполняется
n-l
обменов.
Для
каждого
обмена
нужно
выполнить
три
присваивания.
Следовательно,
общее
количество
операций
присваивания
равно
3*(n-l).
В
сумме
алгоритм
сортировки
методом
выбора
выполняет
n*(n-I)/2+З*(n-l)
= n
2
/2 +
5*n/2-З
основных
операций.
Применяя
свойства
обозначения
О-большое,
можем
отбросить
слагаемые
с
младшими
степенями.
В
итоге
получим
величину
О(n
/2).
Игнорируя
множитель
1/2,
получаем
окончательную
оценку
о(n
2
)
.
Итак,
сложность
алгоритма
сортировки
методом
выбора
равна
о(n
2
)
.
Хотя
алгоритм
сортировки
методом
выбора
не
зависит
от
первоначального
расположения
данных,
что
можно
отнести
к
преимуществам
этого
метода,
его
можно
применять
только
для
небольших
массивов,
?
поскольку
величина
О(n-)
довольно
быстро
растет.
Хотя
алгоритм
выполняет
о(n
2
)
сравнений,
в
ходе
сортировки
осуществляется
только
О(n)
перестановок.
Алгоритм
сортировки
методом
выбора
хорош,
когда
перестановки
представляют
собой
затратные
операции,
а
сравнения
-
нет.
Это
может
произойти,
когда
каждый
элемент
данных
достаточно
велик,
а
ключ
сортировки
мал.
Разумеется,
хранение
данных
в
связанном
списке
позволяет
эффективно
выполнять
перестановки
элементов
любого
алгоритма.
Сортировка
методом
пуэырькв
Алгоритм
сортировки
методом
пузырька
(bubble sort)
сравнивает
между
собой
соседние
элементы
и
меняет
их
местами,
если
они
нарушают
порядок.
Для
этого
приходится
несколько
раз
просматривать
одни
и
те
же
элементы.
Во
время
первого
прохода
сравниваются
два
первых
элемента
массива;
если
они
нарушают
порядок,
их
меняют
местами.
Затем
сравнивается
другая
пара,
т.е.
2-й
и
3-й
элементы.
Если
они
нарушают
порядок,
их
меняют
местами.
Просмотр,
сравнение
и
обмен
двух
элементов
выполняется
до
тех
пор,
пока
не
будет
достигнут
конец
массива.
19

Страницы