53452

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

Доклад

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

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

Русский

2014-04-01

18.77 KB

0 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

64847. ЖАНРОВА ПАЛІТРА РАДІОМОВЛЕННЯ 44.5 KB
  Відмінність жанрів радіожурналістики від жанрів газетної журналістики обумовлено специфікою радіокомунікації. Ключ до розуміння особливостей формування радіожанрів дають специфічні виражальні засоби якими оперує мовлення.
64848. ТЕЛЕБАЧЕННЯ В СИСТЕМІ ЗМІ 40.5 KB
  Особливості технічного постачання телевізійного сигналу ефірне телебачення кабельні мережі супутникові телеканали. Телебачення як обєкт культурології та соціології.
64849. ІНФОРМАЦІЙНІ ПРОГРАМИ НА ТЕЛЕБАЧЕННІ 43 KB
  Виробництво телевізійного сюжету Мова та стиль інформаційної програми. Єдність усіх журналістських матеріалів які утворюють цілісну структуру складеного інформаційного тексту програми є вищим рівнем професійної майстерності журналістів.
64850. ЖУРНАЛІСТСЬКЕ РОЗСЛІДУВАННЯ НА ТЕЛЕБАЧЕННІ 43.5 KB
  Технологія розслідування: методи етапи. Умови реалізації журналістського розслідування: доступ до джерел інформації правові та етичні обмеження безпека журналістів Журналістські розслідування англ. Журналістське розслідування не просто відповідає на запитання...
64851. ПОЛИТИЧЕСКИЕ ПАРТИИ И ПАРТИЙНЫЕ СИСТЕМЫ ЗАРУБЕЖНЫХ СТРАН 83 KB
  В структуру политической организации входит: государство партии иные общественные организации выражающие интересы доминирующих классов партии и иные организации классов которые противостоят правящим слоям общества важнейшим элементом являются политические партии.
64852. КОНСТИТУЦИОННО-ПРАВОВОВЙ СТАТУС ЧЕЛОВЕКА И ГРАЖДАНИНА В ЗС 95 KB
  В науке КП для обозначения правового положения личности установленного нормами законодательства принято использовать следующие термины: основы правового статуса человека и гражданина; конституционно-правовой статус человека и гражданина.
64853. ФОРМЫ ГОСУДАРСТВА В ЗС 126 KB
  Форма государства совокупность внешних признаков организации и осуществление государственной власти. Форма государства включает в себя 3 стороны организации государственной власти: форма правления форма государственного устройства политический режим историческая практика свидетельствует...
64854. ИЗБИРАТЕЛЬНОЕ ПРАВО И ИЗБИРАТЕЛЬНЫЕ СИСТЕМЫ ЗАРУБЕЖНЫХ СТРАН 120 KB
  Избирательное право и избирательная система связана с формированием органов государственной власти и ОМС. в объективном смысле это система юридических норм регулирующих порядок формирования выборных государственных органов...
64855. ГЛАВА ГОСУДАРСТВА 100 KB
  Центральные высшие действуют от имени всего государства и осуществляют свои полномочия свои полномочия на территории соответствующих административно-территориальных единиц. Большинство современных конституций в той или иной форме производят принцип разделения властей...