53452

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

Доклад

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

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

Русский

2014-04-01

18.77 KB

0 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

59855. На гостину до Весни 41 KB
  Хід заняття : Діти вітаються до гостей та підходять до вікна. Скажіть діти яке воно можливо сонечко тоді і зявиться. виставляю макет сонця Давайте діти всі разом привітаємось до сонця до своєї землі один до одного. Діти дістають та роблять опис пророщеної цибулини картоплі з пагонами квасолі.
59856. Що означає бути вихованим 34.5 KB
  Чому така проста норма етикету як вітання справила настільки сильне враження на хлопчика Обґрунтуйте свою думку Відповіді дітейПеревірка письмового завдання в робочому зошиті з теми Як наші вчинки впливають на наше життя 12. Чи згоден ти з твердженнями Вчинки наші дії Далеко не всі наші дії можна назвати моральними вчинками. Оцінюючи вчинки ми співвідносимо їх з 78. Скажіть як на вашу думку співвідносяться добро та вихованість Діти доходять висновку що в основі виховання гарних манер лежить повага до інших людей бажання...
59858. Дії з десятковими дробами. 6 клас 3.22 MB
  Зацвітають перші весняні квіти. Епіграф нашого уроку слова Максима Рильського: Люби природу не як символ душі своєї Люби природу не для себе люби для неї Сьогодні ми з вами повторимо дії з десятковими дробами подорожуючи країною квітів і дізнаємось багато цікавого про квіти.
59859. МАТЕМАТИЧНИЙ ВЕЧІР «ЧУДОВА СІМКА» 6.32 MB
  Оформлення: розвішані стінгазети де центральне місце займає цифра 7 виставка малюнків по темі: У гостях у казки виставка творчих робіт з теми: Сім чудес світу карта України мультимедійна презентація Сім чудес. Наша сьогоднішня програма для учнів...
59860. Використання дидактичних ігор на уроках мови та читання 1.57 MB
  Кожна дидактична гра виконує різні функції: збагачує пізнавальний досвід дітей; розвиває мислення мову уяву точність; викликає інтерес до навчання. Ігри на уроках читання і мови Гра Встанови звязки використовується як для розвитку уяви так і для словеснологічного мислення. Гра “Яка буква†Це завдання можна виконати в групах або в парах.
59861. ВИКОРИСТАННЯ ЗАСОБІВ МУЛЬТИМЕДІА НА УРОКАХ УКРАЇНСЬКОЇ МОВИ З ТЕМИ «ЗДОРОВИЙ СПОСІБ ЖИТТЯ» 36.5 KB
  У дугому блоці подається три презентації: урок у 56 класах Обираємо здоровий спосіб життя з використанням інноваційних технологій навчання; діалогічне та монологічне висловлювання у 78 класах з теми Чому українці повинні жити 150 років; інформдайджест який використовується у процесі підготовки монологічного чи діалогічного висловлювання у 911 класах. У третьому блоці розміщено відеоролики розраховані на використання різних форм роботи на уроці але можна запропонувати найдоцільніші з них а саме: створення речень за...
59862. Математика 115 KB
  В порядке очереди каждая команда дает ответ на каждый вопрос или соглашается с первым ответом или дает свой ответ. По сколько километров пробежала каждая лошадь ответ: по 40км На грядке сидят 6 воробьев к ним прилетели еще 5.