53452

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

Доклад

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

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

Русский

2014-04-01

18.77 KB

0 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

64858. Двоичное кодирование 157 KB
  В отличие от привычного для нас десятичного кодирования чисел то есть кода с основанием десять при двоичном кодировании в основании кода лежит число два рис.3 показано соответствие первых двадцати чисел в десятичной и двоичной системах.
64859. ПРЕДМЕТ ТЕОРИИ ГОСУДАРСТВА И ПРАВА 135 KB
  В познании окружающего мира особое место занимает наука представляющая одну из сфер человеческой деятельности. Теория государства и права относится к общественным гуманитарным наукам.
64860. ВИДЫ ХИРУРГИЧЕСКОЙ ПОМОЩИ. ОРГАНИЗАЦИЯ ХИРУРГИЧЕСКОГО ОТДЕЛЕНИЯ. ПОДГОТОВКА КАДРОВ ХИРУРГОВ. ИСТОРИЯ КАФЕДРЫ ОБЩЕЙ ХИРУРГИИ. ВЕДЕНИЕ МЕДИЦИНСКОЙ ДОКУМЕНТАЦИИ 208.5 KB
  Знать: принципы организации современной многопрофильной больницы, санитарно-гигиенические требования работы приемного отделения, хирургического отделения, процедурного кабинета, перевязочной, операционного блока.
64862. Періодизація розвитку української культури. Джерела. Культура на українських землях у найдавніші часи. Стародавня культура східних слов’ян 7.01 MB
  Україна — промислово-аграрна країна. Вона є одним з провідних експортерів деяких видів сільськогосподарської продукції і продовольства, зокрема, соняшникової олії. Народно-господарський комплекс країни включає такі види промисловості як важке машинобудування, чорна та кольорова металургія...
64863. СОДЕРЖАНИЕ И СУЩНОСТЬ МАРКЕТИНГА 94 KB
  Исходной идеей лежащей в основе маркетинга является идея человеческих нужд где под термином нужда понимается ощущение нехватки человеком чего-либо. Вторая исходная идея маркетинга потребность нужда принявшая специфическую форму в соответствии...
64865. Правление первых Славянских князей 36 KB
  В это время Ярослав который имел все права на престол нанимает Шведскую дружину но тут ему не повезло: Шведы прибыв в Новгород напились и устроили массовое изнасилование Новгородок. Часть Шведов была перебита но Новгородцы помирились с князем Ярославом...
64866. Древнерусские праздники и обряды 34.5 KB
  Святки имя беса который являлся во время зимних развлечений и игр. В печах в это время тушили все очаги и разводили в них новый огонь называвшийся Колядин огонь. В каждой крестьянской семье совершались торжественные обрядовые трапезы характеризующиеся наличием ритуальной...