53452

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

Доклад

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

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

Русский

2014-04-01

18.77 KB

0 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

76520. Принципы обучения (общедидактические) 42 KB
  Прочность усвоения знаний достигается логикой построения изучаемого материала системой упражнений требующих не автоматического а творческого и сознательного перенесения полученных знаний специальными методами на этапе усвоения материала а также постоянным повторением материала уже после изучения раздела. Наглядность это использование специальных средств для опоры на различные анализаторы при восприятии и усвоении материала. Наглядность служит для того чтобы вопервых облегчить понимание материала и вовторых задействовать как можно...
76521. Принципы методики преподавания русского языка 26 KB
  Практически во всех разделах изучаются значимые единицы морфемы слова предложения. В морфемике необходимо учитывать что морфемы являются минимальными значимыми частями слова и что поэтому морфемный разбор не может быть проведен механически на глазок. При изучении морфологии существенно то что разные значения одного и того же слова могут иметь разные морфологические характеристики например: слово лес в значении ‘совокупность деревьев имеет формы единственного и множественного числа а в значении ‘строительный материал формы только...
76522. Отбор теоретических понятий при изучении лексики и фразеологии 27 KB
  Цель формирование представлений о лексикофразеологической системе русского языка; знакомство со лексическим и нормами русского литературного языка; обогащение словарного запаса учащихся; Задачи: формирование основных лексических понятий знакомство с разными способами пополнения словарного запаса научить школьников определять роль лексических и фразеологических единиц речи сформировать умение школьников использовать лексику и фразеологизмы в соответствии с лексич значением научить пользоваться разными видами словарей В начальной школе...
76523. Отбор теоретических понятий при изучении морфологии 29.5 KB
  В школьной практике изучается морфология на синт основе то есть главное внимание уделяется условию и характеру употребления словоформ в разных стилях и жанрах речи формированию умения школьников целесообразно использовать слова разных частей речи в построении связанного высказывания. Все словоформы русского языка систематизированы и объединены в части речи которые в школе рассматриваются с точки зрения структурно семантического принципа значения формы и функции слова. Цели: формирование понятия морф система русского языка обогащение...
76524. Отбор теоретических понятий при изучении синтаксиса 30.5 KB
  ИНТЕРНЕТ Рассмотрение синтаксической единицы предложения начинается в 1 классе Обеспечить усвоение учащимися знаний о строе русского языка на основе сознательного восприятия ими системы синтаксических понятий и правил ; Разграничение в научном синтаксисе словосочетания и предложения способствовало выделению существенных признаков качественно различных единиц языка более глубокому постижению специфики каждой из них. Синтаксис предложения рассматривает коммуникативную единицу языка служащую средством формирования выражения и сообщения...
76525. Основные теоретические понятия методики обучения стилистике 25.5 KB
  Выделяют пять стилей из них четыре книжных: научный официальноделовой публицистический художественный и разговорный стиль. Научный стиль Научный стиль один из книжных стилей который используется в научных трудах учебниках и учебных пособиях устных выступлениях на научные темы. В научном стиле можно выделить следующие разновидности: 1 собственно научный стиль. 2 научнопопулярный стиль который присущ текстам предназначенным для популяризации научных знаний.
76526. Виды речевых ошибок: методика работы по их предупреждению и исправлению 29 KB
  Употребление слов в несвойственных им значениях. Повторение однокоренных слов в одном предложении тавтология: Писатель ярко описывает события того дня. Речевая недостаточность возникает в случае когда пропущено нужное слово. Употребление лишних слов.
76527. Отбор теоретических понятий при изучении фонетики, графики и орфоэпии 31 KB
  Необходимо при изучении словообразования: буквы имеющие два один звук. Цель изучения:осознаное усвоение звуковой системы языка; знакомство с орфоэпическими нормами СРЛЯ; формирование орфографических навыков.Задачи:Формирование основных фонетических понятий: звук слог ударение интонация;Дать представление о русской графике как науке устанавливающей общие принципы передачи звучащей речи на письме;Развивать фонематический слух учащегося и на этой основе формировать орфографическую грамотность школьника;Закрепить умение обозначить звуки...