53452

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

Доклад

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

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

Русский

2014-04-01

18.77 KB

0 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

44221. Сюжетно-дидактические игры математического содержания в самостоятельной деятельности детей 6 го года жизни 10.3 MB
  Теоретические аспекты использования игровой деятельности детей дошкольного возраста для развития математических представлений Содержание математических представлений детей 6 го года жизни. Характеристика самостоятельной деятельности детей шестого года жизни и условия применения в ней сюжетно-дидактических игр математического содержания.
44222. Лига Арабских государств и ее роль в Интеграционном процессе арабского мира 358.5 KB
  Следует сказать, что в последние годы объем исследований и научных работ по интеграции арабского мира возрос, однако, до сих пор нет четкого анализа происходящих в этом регионе процессов. Они изучаются, главным образом, с точки зрения роли субъективного фактора, сознательных намерений тех или иных социальных групп, но в них не выделяются закономерности, тенденции, объективные факторы, обстоятельства.
44224. Охорона праці. Методичні вказівки 371 KB
  МЕТОДИЧНІ ВКАЗІВКИ до виконання розділу дипломного проекту Охорона праці Затверджено на засіданні кафедри безпеки життєдіяльності і інженерної екології Протокол № 3 від 30. Харків ХДТУБА 2010 Методичні вказівки до виконання розділу дипломного проекту Охорона праці для студентів спеціальностей....
44225. Влияние лыжного спорта на развитие физических качеств подростков 15-17 лет 505 KB
  Проблема исследования: ухудшение физических качеств школьников не занимающихся спортом. Объект исследования: физические качества школьников 1517 лет. Целью данной работы является сравнительный анализ физических качеств спортсменов лыжников и школьников не занимающихся спортом 1517 лет между собой. Для этого поставлены следующие задачи: изучить литературные источники по данной теме; изучить место лыжной подготовки в системе общего физического воспитания школьников; определить этапы исследования и развития физических качеств у лыжников...
44226. Психологическая реабилитация женщин после развода 2.94 MB
  Изучить особенности состояния женщин 25 – 32 летнего возраста после развода. Выявить особенности реакции на фрустрации, уровни тревоги и депрессии, а так же состояние самооценки женщин после развода. Определить степень потребности их в психологической реабилитации, и на основе изученного теоретического и практического материала внести коррективы в предложенные ранее программы помощи и реабилитации женщин после развода.
44227. Автоматизована система керування АСК «Радіомайстерня. Ведення обліку радіодеталей» 1.88 MB
  При цьому ємність магнітних стрічок була досить великою але за своєю фізичною природою вони забезпечували послідовний доступ до даних. Магнітні барабани надавали можливість довільного доступу до даних але були обмеженого розміру. До цього кожна прикладна програма яка потребувала зберігання даних у зовнішній пам’яті сама визначала положення кожної порції даних на магнітній стрічці або барабані і виконувала обміни між оперативною та зовнішньою пам’яттю за допомогою програмноапаратних засобів низького рівня. Крім того кожній прикладній...
44228. Операційна система Windows на прикладі сучасних систем 3.92 MB
  Працює в багатозадачному режимі. Використовує процесну форму (паралельно виконується кілька програм) та потокову форму (паралельно виконуються різні частини однієї програми). При одному процесорі багатозадачний режим реалізується так: попрацювавши якийсь час, задача у Windows 98 автоматично розвантажується і керування передається наступній задачі. При перебоях під час розв'язування задачі її можна зняти без розвантаження всієї системи
44229. Товарознавство та торгівельне підприємництво. Методичні вказівки 584.5 KB
  Методичні вказівки містять загальні рекомендації щодо написання бакалаврської роботи тематику робіт загальні вимоги до написання оформлення та виконання окремих розділів. Організація виконання випускної бакалаврської роботи Керівництво бакалаврськими випускними роботами Напрямки і теми бакалаврських випускних робіт Структура і зміст випускної бакалаврської роботи. Структура бакалаврської випускної роботи