ВУЗ:
Составители:
112
i 1 2 3 4 5 6 7 8 9 10
A(i) 15 11 12 9 7 2 5 3 8
1
Проход 1 1 11 12 9 7
2
5 3 8 15
Проход 2 1 2 12 9 7 11 5
3
8 15
Проход 3 1 2 3 9 7 11
5
12 8 15
Проход 4 1 2 3 5
7
11 9 12 8 15
Проход 5 1 2 3 5 7 11 9 12
8
15
Проход 6 1 2 3 5 7 8
9
12 11 15
Проход 7 1 2 3 5 7 8 9 12
11
15
Проход 8 1 2 3 5 7 8 9 11
12
15
Проход 9 1 2 3 5 7 8 9 11 12 15
Рис. 8.1. Пример сортировки методом выбора
Количество перестановок для метода выбора зависит от расположения
элементов в исходной последовательности. Однако в любом случае за один
проход потребуется не более одной перестановки. Следовательно, максималь-
ное количество перестановок равно N–1. В лучшем случае, когда исходная по-
следовательность уже упорядочена, не потребуется ни одной перестановки
.
Следовательно, среднее число перестановок пропорционально П
ср
= N/2. Для
примера, приведенного на рис. 8.1, П
ср
= 10/2 = 5. Фактическое значение числа
перестановок равно 6.
Метод обмена. При сортировке этим методом упорядоченная последо-
вательность создается на том же участке памяти, что и исходная последователь-
ность. В процессе сортировки производится попарное сравнение соседних эле-
ментов. Если порядок между соседними элементами нарушен, они меняются
местами. Этот метод называется еще методом пузырька, так
как наименьшие
элементы с каждым проходом, подобно пузырькам, «всплывают» по направле-
нию к первой позиции последовательности.
Пример сортировки исходной неупорядоченной последовательности
A(i) = {15, 11, 12, 9, 7, 2, 5, 3, 8, 1} методом обмена показан на рис. 8.2.
В течение первого прохода сравниваются элементы А(1) и А(2). Если
А(2) < А(1), то элементы меняются местами. Этот процесс повторяется для пар
элементов А
(2) и А(3), А(3) и А(4) и т. д. После первого прохода наибольший
элемент займет N-ю позицию, а наименьший переместится на одну позицию
вверх («всплывет»). На каждом последующем проходе очередные наибольшие
элементы занимают соответственно позиции N–1, N–2 и т.д. В результате будет
сформирован упорядоченный массив элементов. На рис. 8.2 затемненные
участ-
ки последовательности являются уже отсортированными. После каждого про-
хода может быть сделана проверка, были ли сделаны перестановки на данном
Страницы
- « первая
- ‹ предыдущая
- …
- 110
- 111
- 112
- 113
- 114
- …
- следующая ›
- последняя »