53452

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

Доклад

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

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

Русский

2014-04-01

18.77 KB

0 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

10592. Философия Возрождения: антропоцентризм (XV –XVI вв.) 50 KB
  Философия Возрождения: антропоцентризм XV –XVI вв. С XV века происходят изменения в социально-экономической и духовной жизни Западной Европы. Она характеризуется возникновением мануфактур техническими открытиями и нововведениями самопрялка ткацкий станок водяное к...
10593. Немецкая классическая философия во второй половине XVIII века 56 KB
  Немецкая классическая философия В Германии во второй половине XVIII века сформировалось новое направление немецкая классическая философия. Ее представители: Кант –дуалист Фихте субъективный идеалист Шеллинг объективный идеалист Гегель – объективный идеали
10594. Отечественная философия XIX - начала XX веков 82.5 KB
  Отечественная философия XIX начала XX веков Русская философия начинает свое существование с XIX века. Основная тема которая на протяжении почти целого столетия занимала умы русской интеллигенции – историческая судьба России ее прошлое настоящее и будущее ее историче...
10595. Предмет и цель математического моделирования 19.24 KB
  Предмет и цель математического моделирования. В развитии различных областей человеческой деятельности математика оказывала и оказывает существенное влияние. Ее роль складывалась исторически и зависела от двух факторов: степени развития математических понятий и ма
10596. Математическое моделирование системы индукционного нагрева 32.53 KB
  Математическое моделирование системы индукционного нагрева. Система индукционного нагрева представляет собой в общем случае источник питания индуктор нагреваемое тело и окружающую среду. Источник питания будь то генератор повышенной частоты тиристорный п...
10597. Тепловая задача. Основные положения. Критерии и числа подобия 67.46 KB
  Тепловая задача. Основные положения. Критерии и числа подобия В настоящее время существует немало как аналитических так и численных методов решения тепловых задач для тел цилиндрической и прямоугольной формы. В случае нагрева тел более сложной формы для решения п...
10598. Методы решения краевых задач. Метод разделения переменных (Метод Фурье) 119.66 KB
  Методы решения краевых задач. Метод разделения переменных Метод Фурье. Метод разделения переменных относится к классическим методам решения линейного дифференциального уравнения теплопроводности. При его применении вначале находится совокупность частных решений...
10599. Методы интегрального преобразования 76.24 KB
  Методы интегрального преобразования. Операционные методы. Для многих задач теплопроводности использование классических методов оказывается неэффективным например применение метода разделения переменных для задач с внутренними источниками тепла. Основные пра
10600. Нагрев неограниченной пластины. Решение методом преобразования Фурье 73.38 KB
  Нагрев неограниченной пластины. Решение методом преобразования Фурье Дана неограниченная пластина толщиной 2R при температуре. Теплообмен с окружающей средой происходит при ГУ2. Нагрев осуществляется переменным источником ...