53452

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

Доклад

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

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

Русский

2014-04-01

18.77 KB

0 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

54782. Модель «предельный доход – предельные издержки» 17.34 KB
  Когда фирма достигла такого соотношения, она уже не станет увеличивать производство, выпуск станет стабильным, отсюда и название равновесия фирмы.
54783. Створення та діяльність ОУН 103.5 KB
  Мета: познайомити учнів з процесом створення ОУН розкрити зміст діяльності організації з׳ясувати тактику та стратегію боротьби розвивати вміння працювати з історичними джерелами аналізувати історичний матеріал сприяти розвитку критичного осмислення історичних подій виховувати в дусі толерантності. Тип уроку: урок формування знань умінь та навичок Обладнання: підручник роздатковий матеріал схеми Створення ОУН та Розкол ОУН Основні поняття та терміни: інтегральний націоналізм націоналізм ОУН. Очікувані результати Учні...
54784. Our Unique Planet 38 KB
  As a warming up exercise for today I have prepared a short practicing in reading. Look at the monitors. The words will be there for only two seconds and your task is to read them correctly. Read aloud and think carefully. We’ll see who the champion is! And your home task was to speak about the beauty of the world and to write colour poems. It’s time to check it and listen to you.
54785. Озера і лимани. Особливості гідрологічного режиму. Водосховища 155.5 KB
  Мета: сформувати в учнів уяву про озера, лимани, водосховища України, їх походження, гідрологічний режим та екологічні проблеми; розглянути проблему доцільності створення водосховищ; розвивати навички роботи з тематичними і контурними картами; сприяти розширенню знань географічної номенклатури; закріпити знання отримані в курсі географії 6 класу при вивченні тем: «Озера, типи озерних улоговин», «Водосховища, їхня роль у господарському комплексі».
54786. Озера, болота і штучні водойми України 63 KB
  Мета уроку: навчальна: сформувати в учнів уявлення про основні озера болота водосховища України; загальні риси гідрологічного режиму та роботи озер водосховища України; розвивальна: розвивати вміння учнів аналізувати тематичні карти; виховна: сприяти розвитку навичок мислення високого порядку критичного мислення;сприяти формуванню екологічної культури особистості.
54788. МУЗЕЙ ОЦТУ 448 KB
  Вони протягом декількох місяців збирали інформацію про оцет його історію виробництво застосування значення. Застосування оцтової кислоти Різновиди оцту Виробництво оцту Оцет в моєму домі: практичні поради Оцтова кулінарія Оцтове дерево Оцет як хобі Оцет для краси Оцет помічник здоровя Оцтові історії Оцет в мистецтві Висловлювання про оцет Деякі експозиції Музею оцту є також в електронному варіанті зроблені за допомогоб програми РоwerPoint. Оцет грец. όος Ще більше 4000 років тому в Стародавньому Єгипті...
54789. Північна Америка. Фізико-географічне положення. Історія відкриття й дослідження материка 35 KB
  Мета уроку: сформувати знання про фізикогеографічне положення особливості берегової лінії історію відкриття та дослідження материка Північна Америка; удосконалювати вміння працювати з картоювизначати географічні координати; розвивати увагу уяву зорову память логічне мислення; виховувати інтерес до пізнання нового. До цього ви ознайомилися з чотирма материками. Сьогодні на уроці ми з вами більш детально ознайомимося з особливостями географічного положення материка Північна Америка та...
54790. Пагін, його будова. Стебло – вісь пагона 37.5 KB
  Цілі: Сформувати в учнів поняття про пагін основний надземний орган рослини що складається із стебла листків і бруньок познайомити з видами бруньок продовжити формування умінь і навичок виконання і оформлення лабораторної роботи. Що ж головне корінь чи пагін Давайте послухаємо байку Михайла Старицького Коріння та пагін.