Главная » Java, Структуры данных и алгоритмы » Алгоритм сортировки пузырьковым методом

0

Рассмотрим последовательность из п элементов, которые можно сравнивать между собой по некоторым отношениям (например, компании, сравниваемые по прибылям, государства, сравниваемые по численности населения, лексикографическое сравнение слов). Задача сортировки состоит в изменении порядка следования элементов таким образом, чтобы они находились в порядке убывания. , или пузырьковой сортировки (рис. 5.9) решает эту задачу, выполняя серии проходов внутри последовательности. При каждом проходе элементы просматриваются в направлении увеличения разряда, от разряда 0 до конца последовательности. В каждой позиции элемент сравнивается с соседним элементом, и, если их порядок неверен (то есть предыдущий элемент больше последующего), эти элементы меняются местами. Сортировка последовательности осуществляется при выполнении п таких проходов.

Алгоритм пузырьковой сортировки обладает следующими характеристиками:

•          при первом проходе отыскивается наибольший элемент, который будет перемещаться, пока не достигнет последней позиции последовательности;

•          При втором обходе отыскивается второй по величине элемент, который будет перемещаться до предпоследней позиции;

•            и так далее.

Рис. 5.9. Алгоритм пузырьковой сортировки последовательности целых чисел.

При каждом проходе показаны элементы, которые меняются местами, и последовательность после окончания прохода

Таким образом, к концу /-го обхода / крайних правых элементов последовательности (то есть с разрядом от п — 1 до п — /) находятся в конечной позиции. Этот результат позволяет утверждать, что число проходов алгоритма сортировки для последовательности п элементов можно ограничить числом п. Более того, /-й обход может быть ограничен первыми п — i + 1 элементами последовательности.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии