53452

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

Доклад

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

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

Русский

2014-04-01

18.77 KB

0 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

78427. Техническая эксплуатация ГЭУ 18.65 KB
  Основные сведения Основная задача при эксплуатации ГЭУ обеспечить ее безотказную и безаварий ную работу и постоянную готовность к действию что достигается выполнением следующего. своевременное пополнение судов с ГЭУ сменнозапасными частями и материала ми. выполнение графиков профилактических осмотров и ремонтов в соответствии с инструкциями по обслуживанию электрооборудования ГЭУ.
78428. ФОНЕТИКА и ФОНОЛОГИЯ 48.29 KB
  Для речевого общения чрезвычайно важно различение произносимого слова среди других сходных по звучанию. Часто слова различаются всего лишь одним звуком наличием лишнего звука по сравнению с другим словом порядком следования звуков галка галька бой вой рот крот нос сон. Словесное ударение разграничивает слова и формы слов одинаковые по звуковому составу клубы клубы дыры дыры руки руки. Эта цепь членится на звенья или фонетические единицы речи: фразы такты фонетические слова слоги и звуки.
78430. Электромеханические свойства электродвигателей постоянного и переменного тока 233.82 KB
  Механические характеристики электродвигателей Механическая характеристика электродвигателя это зависимость угловой скорости ЭД от момента на его валу: ω М. Характер изменения угловой скорости двигателя с изменением момента сопротивления определяет жесткость механической характеристики. Абсолютно жесткие характеристики присущи синхронным двигателям прямая. Естественной характеристикой называется характеристика соответствующая работе ЭД при номинальных параметрах питающей сети нормальной схеме подключения к ней и при отсутствии...
78431. Гласные звуки и их классификация. Фонология 35.62 KB
  Фонология Гласные звуки отличаются от согласных наличием голоса музыкального тона и отсутствием шума. Существующая классификация гласных учитывает следующие условия образования гласных: 1 степень подъема языка 2 место подъема языка и 3 участие или неучастие губ. Движение языка по горизонтали приводит к образованию гласных трех рядов: гласные переднего ряда...
78432. Режимы работы электродвигателей в электроприводе 208.28 KB
  Приводные ЭД могут быть постоянного и переменного тока. В настоящее время на судах морского флота широкое распространение получили ЭД переменного суда 3фазные асинхронные двигатели постоянного тока находят ограниченное применение. Б Работа электродвигателей постоянного тока в переходном режиме...
78434. Настройка RUP для использования в рамках УМК «Введение в унифицированный процесс разработки ПО» посредством IBM Rational Method Composer 3.6 MB
  Цель работы – создание базы знаний по процессу разработки программного обеспечения, который используется в рамках курса «Введение в УП». Методы исследования – теоретический (изучение возможностей RMC), экспериментальный (применение их на практике).
78435. ПОСТРОЕНИЕ СОВОКУПНЫХ ПРОСТРАНСТВЕННЫХ ОБЪЕКТОВ 1.88 MB
  Объект исследования - алгоритмы, обеспечивающие построение совокупного трехмерного объекта на основе пересечения двух других трехмерных объектов. Цель работы – построение такого алгоритма, разработка динамически подключаемой библиотеки, демонстрирующей работу алгоритма