53452

Процедура Bubble_sort и ее особенности

Доклад

Информатика, кибернетика и программирование

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.

Русский

2014-04-01

18.77 KB

0 чел.

Процедура Bubble_sort и ее особенности.

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.

Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировка методом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: "метод пузырька"?

Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).

Алгоритм и особенности этой сортировки таковы: 1. При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.

Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.

При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.

На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.

В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.

После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.

Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).

При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.


 

А также другие работы, которые могут Вас заинтересовать

67470. Исследование модели кольцевой ЛВС с маркерным доступом 1.4 MB
  Цель работы: Исследование особенностей построения и функционирования кольцевой ЛВС с маркерным методом доступа и определение основных характеристик сети. Определить основные характеристики ЛВС основе исследования аналитической модели сети.
67471. Выбор рациональной длины пакета сети ЭВМ 149.5 KB
  Исходные данные средняя длина передаваемого сообщения: l = 5000 бит; длина заголовка пакета: С = 320 бит; коэффициент учитывающий системные издержки на сборку сообщений: К1 = 15; время изменения направления передачи t1n = 0 t2n = 004; номинальная...
67472. Функционирование мостов и коммутаторов на основе протокола канального уровня STP стека протоколов TCP/IP 119.5 KB
  Изучение основных принципов работы мостов и коммутаторов в сетях ЭВМ на основе протокола STP. Получение знаний по принципам построения и алгоритмам функционирования мостов и коммутаторов в сетях ЭВМ и навыков по устранению активных петель в сети при помощи протокола STP.
67473. Функционирование маршрутизаторов на основе протокола сетевого уровня OSPF стека протоколов TCP/IP 81.5 KB
  Получение знаний по принципам построения и алгоритмам функционирования маршрутизаторов в сетях ЭВМ и навыков по выбору кратчайших путей в сети на основе протокола OSPF. Граф сети Граф-схемы алгоритмов Граф-схема алгоритма выбора кратчайших путей Дейкстра Граф-схема алгоритма выбора...
67474. Финансы и финансовая система. Основные понятия финансов 146.5 KB
  Термин финансы происходит от французского fin = finis означающего конец окончание. Финансы связаны с движением денег от одного владельца к другому следовательно финансы связаны с экономическими отношениями и являются экономической категорией. Финансы представляют собой отношения по созданию...
67475. КРИЗИС СЕРЕДИНЫ ЖИЗНИ 205.5 KB
  Проблема возраста всегда актуальна, как для каждого отдельного человека, так и для всего общества в целом. Переход из одного возрастного периода в другой является судьбоносным и определяет всю дальнейшую жизнь.
67476. Становление личностного новообразования периода кризиса трех лет 125.5 KB
  Кризисов, которые будет преодолевать ребенок несколько: это кризис новорожденности, кризис одного года, трех лет, семи лет, кризис подросткового возраста. Время их возникновения зависит от конкретного ребенка и условий его жизни. Общим для всех кризисов развития являются несколько основных критериев: острый период, трудновоспитуемость, впечатление регресса.
67477. Суперкомпьютер SuperMUC 600 KB
  Производительность суперкомпьютеров чаще всего оценивается и выражается в количестве операций с плавающей точкой в секунду (FLOPS). Это связано с тем, что задачи численного моделирования, под которые и создаются суперкомпьютеры, чаще всего требуют вычислений, связанных с вещественными числами с высокой степенью точности