Стр. 79 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
77
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4
3
2
5
1
3
4
2
5
1
3
2
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
1
5
2
3
1
4
5
2
1
3
4
5
1
2
3
4
5
Алгоритм
for (i=2; i<=n; i++)
{
for (j=i; j>=2; j--)
{
if (x
j
>x
j
-1
) break;
<x
j
меняем местами с x
j
-1
>
}
}
Анализ быстродействия
. Итераций по
i
– (
n
-1). На каждой итерации будет
в худшем случае (
i
-1) итераций по
j
. Тогда всего сравнений и обменов:
0
min
min
= =
O C
;
)1 (
4
1
ср
ср
− = =
nn
O C
;
)1 (
2
1
max
max
− = =
nn
О C
.
Единственным плюсом пузырьковой сортировки является простота в
программировании.
Как в простой сортировке вставками, так и в пузырьковой сортировке
основным источником неэффективности является тот факт, что обмены дают
слишком малый эффект, так как в каждый момент времени имена сдвигаются
только на одну позицию. Такие алгоритмы непременно требуют порядка
n
2
операций как в среднем, так и в худшем случаях. Прием, приводящий к тому,
что каждый обмен совершает больше работы, используется в быстрой
сортировке.
