53452

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

Доклад

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

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

Русский

2014-04-01

18.77 KB

0 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

68800. Маркетинговое исследование рынка сахара в городе Омске 189.26 KB
  Целью данного маркетингового исследования является изучение рынка сахара в городе Омске, ассортимента и предпочтений потребителей. Для достижения этой цели, необходимо решить следующие задачи: Изучить сущность маркетинговых исследований; Разработать опросный лист и провести опрос...
68801. Расчет передающего устройства магистральной радиосвязи 6.62 MB
  Мощность сигнала в нагрузке – 18 кВт Диапазон рабочих частот – 3 – 9 МГц Нагрузка – несимметричная, широкополосная сопротивлением 50 Ом Модуляция – А3J – однополосная телефония с подавленной несущей. Передача одноканальная. В возбудителе содержится синтезатор с шагом рабочих частот – 60 Гц.
68802. Устройства генерирования и формирования сигналов 4.71 MB
  Мощность которую должен обеспечивать один модуль выходного каскада можно оценить по формуле: ; Вт где КПД выходной колебательной системы и КПД систем сложения мощностей; M – число модулей в выходном каскаде. Каждый двухтактный ГВВ модуля выходного каскада должен выделять мощность 1235 4 = 30875 Вт.
68803. Механизация погрузо-разгрузочных работ 1.62 MB
  Время очистки полувагона от остатков сыпучего груза с помощью накладного вибратора ВРШ2 tоч=6мин. м; αn−коэффициент амортизации эстакады αn=003; γ – коэффициент учитывающий эффективность капиталовложений γ=01; tм− время выполнения маневров tм=03 ч.− подготовительно-заключительное время tп.=015 часа...
68805. Синтез цифрового БИХ-фильтра 2.52 MB
  Используя метод Эйлера, метод билинейного преобразования и метод инвариантной импульсной характеристики, при выбранном интервале дискретизации рассчитать передаточную функцию цифровой цепи (цифровой фильтр (ЦФ) с бесконечной импульсной характеристикой (БИХ-фильтр)), получить разностное уравнение...
68806. ОРГАНИЗАЦИЯ И ИНВЕНТАРИЗАЦИЯ КОРМОВ, СЕМЯН И ПОСАДОЧНОГО МАТЕРИАЛА В СПК «УКРАИНСКИЙ» ИСИЛЬКУЛЬСКОГО РАЙОНА ОМСКОЙ ОБЛАСТИ 335 KB
  Актуальность выбранной темы заключается в том, что благодаря инвентаризации материальных запасов предприятия формируется полная и достоверная информация о деятельности организации и ее имущественном положении, необходимой внутренним пользователям бухгалтерской отчетности – руководителям...
68807. Оценка влияния температурного режима на предельно допустимую высоту и максимально допустимую скорость полёта по маршруту Сыктывкар - Мурманск 343.23 KB
  В курсовой работе требуется оценить значимость многолетнего режима температуры на высотах над участками воздушной трассы указанной в индивидуальном задании на курсовую работу для обеспечения безопасности и повышения экономичности полетов рассчитать возможные пределы изменения практического потолка...