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

UptoLike

ВУЗ: 

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

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

Рубрика: 

а)
Проход1:
б)
Проход2:
Исходный
массив:
РИСУНОК
5.
Первые
два
прохода
при
сортировке
массива.
состоящего
из
пяти
целых
чисел,
методом
пузырька:
а)
первый
проход;
б)
второй
проход
На
рис.
5,
а
показаны
результаты
первого
прохода
алгоритма
сортировки
методом
пузырька
на
примере
массива,
содержащего
пять
целых
чисел.
Сначала
сравниваются
между
собой
элементы
первой
пары
-
числа
29
и
10.
Они
нарушают
заданный
порядок,
поэтому
их
меняют
местами.
Затем
сравниваются
элементы
второй
пары
-
числа
29
и
14,
поэтому
их
также
меняют
местами.
После
этого
сравниваются
элементы
третьей
пары
-
числа
29
и
37.
Они
не
нарушают
установленный
порядок,
поэтому
остаются
на
своих
местах.
В
заключение
меняются
местами
элементы
последней
пары
-
числа
37
и
13.
Хотя
после
первого
прохода
массив
остается
неупорядоченным,
наибольший
элемент
оказывается
в
конце
массива,
"всплывая",
как
пузырек
на
поверхность
воды.
Во
время
второго
прохода
нужно
вернуться
к
началу
массива
и
обработать
его
точно
так
же,
как
и
в
первый
раз,
останавливая
обработку
на
предпоследнем
элементе.
Таким
образом,
при
втором
проходе
просматриваются
n-l
элемент
массива.
После
второго
прохода
второй
наибольший
элемент
окажется
на
предпоследнем
месте,
как
показано
на
рис.
5,
б.
Теперь,
игнорируя
два
последних
элемента,
которые
уже
поставлены
в
нужном
порядке,
следует
продолжить
обработку
массива,
пока он
весь
не
будет
упорядочен.
Несмотря
на
то
что
алгоритм
сортировки
методом
пузырька
состоит
из
n-l
прохода,
в
некоторых
случаях
удается
обойтись
меньшим
количеством
шагов.
Таким
образом,
процесс
можно
прекратить,
если
в
ходе
проверки
не
выполнено
ни
одной
перестановки,
В
приведенной
ниже
функции
bubbleSort,
написанной
на
языке
С++,
дЛЯ
сигнализации
о
перестановке
используется
булева
переменная
sorted.
Функция
bubbleSort
использует
функцию
swap,
описанную
ранее.
\'oid
buhh
1
е/)()/'''(
Пала
Ту1)(;
/11(;
/~1
кк
ау
1_1.
j
/1/
11)
//---------------------------------------------------------
20

Страницы