[МУЗЫКА] Рассмотрим другой метод сортировки, который работает несколько более быстро, чем предыдущий. Мы с вами сказали, что в предыдущем методе если элементы массива уже изначально упорядочены или частично упорядочены, то наш метод всё равно будет сравнивать все пары элементов. Метод «пузырька» в этом случае просто пройдет по всем парам элементов ровно один раз и на этом завершится. За что же этот метод называется методом «пузырька»? Поведение элемента в массиве в этом методе аналогично поведению пузырька в жидкости. Если мы представим себе какую-нибудь жидкость с пузырьками, например, газированную воду, то пузырек, начиная от дна сосуда постепенно поднимается вверх. Так вот здесь аналогичным образом будут вести себя элементы массива. В чем состоит суть метода? В данном методе элементы сравниваются попарно, причем сравниваются два соседних элемента. Если элементы в паре расположены неверно, то мы должны их поменять местами. После этого мы рассматриваем следующую пару элементов и так до конца массива. При этом если при очередном сравнении всех пар была хотя бы одна перестановка элементов в какой-нибудь паре, то мы с вами будем заново просматривать массив. То есть сначала мы сравним все пары и переставим те, которые стоят неправильно, а затем, если перестановки были, начнем опять сравнение всех пар сначала. И сортировка закончится тогда, когда при очередном просмотре массива и сравнении всех пар мы обнаружим, что ни одной перестановки не было. В качестве примера снова рассмотрим сортировку по возрастанию и возьмем тот же самый массив. Итак, вообразим себе, как работает метод «пузырька», сортирующий этот массив по возрастанию. Первая пара — это 2 и −3. Она у нас расположена в неверном порядке. Мы поменяем в ней элементы местами. И продолжаем процесс сравнения пар. Следующая пара — это второй элемент и третий, 2 и 0. Эта пара тоже не расположена по возрастанию, значит мы поменяем ее местами тоже. Следующая пара у нас — это 2 и 5. Для 2 и 5 у нас с вами порядок следования правильный, значит эта пара не меняется. Теперь 5 и 3. Пятерку нужно поменять местами с 3, так как эта пара у нас не была расположена по возрастанию. Последняя пара — это 5 и 1. Эти элементы также расположены в неправильном порядке, меняем их местами. Вот теперь на этом шаге уже видно, почему метод носит название метода «пузырька». Обратите внимание на поведение 5. Наша 5 постепенно всплывает, то есть приближается к концу массива. При этом сравнении пар у нас было несколько перестановок, значит мы начинаем заново сравнивать все пары. Пара −3 и 0 расположена в правильном порядке, пара 0 и 2 также расположена по возрастанию, пара 2 и 3 тоже переставляться не будет, пара 3 и 1 не расположена по возрастанию. Значит мы поменяем элементы местами и дальше рассмотрим пару 3 и 5, эта пара расположена по возрастанию. Мы снова пришли к концу массива, и перестановки были еще на этом шаге произведены. Поэтому мы снова начинаем рассмотрение элементов массива сначала. −3 и 0 — это правильная пара, 0 и 1 — это пара, которая расположена верно, 1 и 2 также расположены правильно, 2 и 3 также у нас расположены в правильном порядке, и 5 тоже стоит за 3, то есть она больше. Следовательно, все наши элементы массива расположены в правильном порядке, и сортировка завершена. Для того чтобы понять, были ли на очередном шаге произведены перестановки, мы будем использовать логическую булевскую переменную, которая будет показывать завершился ли наш процесс сортировки. Рассмотрим, как выглядит сортировка методом «пузырька» по возрастанию, если мы запишем ее на псевдокоде. Вначале мы введем исходные данные, затем нам нужно организовать два цикла. Первый цикл будет проверять, завершились ли уже все перестановки, а второй внутренний цикл будет сравнивать все пары элементов последовательно. В первом цикле мы с вами используем булевкую логическую переменную flag, которой изначально присвоим значение «истина», это признак завершения сортировки. Мы каждый раз надеемся, что все перестановки уже завершены. Затем мы начинаем второй цикл, который будет сравнивать все пары элементов последовательно, мы будем сравнивать каждый элемент со следующим. Этот цикл будет иметь границы от 1 до n − 1. Понятно, почему до n − 1. Потому что у последнего элемента нет следующего, нет пары. И далее мы сравниваем элемент на i-том месте, с тем, который стоит следом за ним. Если эта пара расположена неправильно, то есть у нас i-тый элемент больше, чем следующий, мы должны произвести несколько действий. Во-первых, поменять местам через третью переменную эту пару элементов, и во-вторых, поменять значения флага на «ложь». Перестановка была, и, следовательно, нам придется, завершив сравнение всех пар, снова переходить к началу массива и опять сравнивать эти пары между собой. Далее мы закрываем наше условие, завершаем наш внутренний цикл и пишем условие завершения внешнего цикла. Этот цикл будет продолжаться до тех пор, пока flag не сохранит свое значение true («истина») после просмотра всех пар. Обращаю ваше внимание на квадратные скобки. Квадратные скобки показывают, что «= true»можно не записывать, можно записать «до flag» и этот цикл завершится, когда flag будет равен «истине». Далее мы пишем ключевое слово «конец цикла», выводим полученный массив и на этом наш алгоритм заканчивается. Теперь попробуем сравнить метод установки, который мы изучали ранее, с методом «пузырька». Во-первых, очевидно, что метод установки проще. Но метод «пузырька» лучше тем, что он дает меньшее количество сравнений, особенно если наш массив будет упорядочен изначально, ну или хотя бы частично упорядочен. Кроме того, если вспомнить процесс сортировки методом установки и методом «пузырька», то мы видим, что в методе установки элементы, которые уже заняли свои места, постепенно располагаются, начиная от начала массива. Сначала на первое место приходит нужный первый элемент, затем на второе – второй и так далее до конца массива. А вот в методе «пузырька» элементы, которые уже заняли свои места, будут располагаться в конце. Сначала на свое место приходит последний нужный элемент и так далее. То есть эти методы отличаются еще и тем, где располагается уже упорядоченная часть элементов массива. [МУЗЫКА] [МУЗЫКА]
