[Играет музыка] ДАГ Lloyd: Ладно, пузырьковой сортировки является алгоритм Вы можете использовать для сортировки набора элементов. Давайте взглянем на то, как это работает. 

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

как нам это сделать? Ну в псевдокода кода, мы могли бы сказать, давайте установить счетчик на своп не-нулевое значение. Мы увидим, почему мы делаем, что в секунду. А потом мы повторяем следующие Процесс пока счетчик не подкачки равен 0, или пока мы не делаем никаких свопы на всех. 

Сброс подкачки счетчик 0, если это не уже 0. Тогда посмотрите на каждый соседней парой элементов. Если эти два элемента не в порядке, поменять их местами, и добавить 1 к прилавку подкачки. Если вы думаете о это, прежде чем визуализировать его, заметить, что это будет двигаться ниже значения элементов слева и выше ценится элементы права, эффективно делать то, что мы хотим сделать, что двигаться те группы элементов таким образом. Давайте себе, как это может выглядеть с помощью нашего массива что мы использовали для тестирования из этих алгоритмов. У нас есть несортированный массив здесь, указывает все элементы находясь в красный цвет. И я могу установить счетчик подкачки в ненулевое значение. Я выбрал произвольно отрицательное 1-- это не 0. Мы хотим, чтобы повторить этот процесс до счетчика подкачки не равно 0. Вот почему я могу установить своп вразрез с какой-то ненулевое значение, поскольку в противном случае Счетчик подкачки будет 0. Мы даже не начать Процесс алгоритма. Итак, еще раз, шаги are-- сбросить счетчик подкачки 0, а затем посмотреть на каждый рядом пара, и если они не в порядке, обменять их, и добавить 1 к прилавку подкачки. Итак, давайте начнем этот процесс. Поэтому первое, что мы делаем, это мы устанавливаем счетчик подкачки на 0, и тогда мы начинаем глядя на каждой смежной пары. 

Так мы впервые начать смотреть на 5 и 2. Мы видим, что они находятся вне заказать и поэтому мы поменять их местами. И мы добавляем 1 к прилавку подкачки. Так что теперь наша подкачки счетчик 1, и 2 и 5 были включены. Теперь мы повторяем этот процесс снова. 

Мы смотрим на следующей смежной пары, 5 и 1-- они также вышли из строя, таким образом, мы поменять их и добавить 1 к прилавку подкачки. Затем мы рассмотрим 5 и 3. Они вышли из строя, поэтому мы переставляем их и добавить 1 к прилавку подкачки. Затем мы рассмотрим 5 и 6. Они в порядке, так что мы на самом деле не нужно поменять что-нибудь в этот раз. Затем мы рассмотрим 6 и 4. Они также не в порядке, таким образом, мы поменять их и добавить 1 к прилавку подкачки. 

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

И таким образом мы можем объявить сегодня что это сортируется, и в будущем iterations-- переживает массива again-- мы не должны рассматривать 6 больше. У нас есть только рассмотреть неотсортированной элементы когда мы смотрим на соседних пар. Таким образом, мы закончили один пройти через пузырьковой сортировки. Так что теперь мы вернемся к вопросу, повторять, пока счетчик замены не равно 0. Ну счетчик подкачки 4, так что мы собираемся чтобы повторять этот процесс снова. 

Мы собираемся, чтобы сбросить счетчик подкачки 0, и смотреть на каждой смежной пары. Итак, мы начинаем с 2 и 1-- они в порядке, так что мы обменять их и мы добавляем 1 к прилавку подкачки. 2 и 3, они в порядке. Нам не нужно ничего делать. 3 и 5 в порядке. Нам не нужно, чтобы сделать что-нибудь там. 

5 и 4, они находятся вне порядка, и поэтому мы нужно поменять их и добавить 1 к прилавку подкачки. А теперь мы переехали 5, второй по величине элемент, к концу несортированных части. Так что теперь мы можем назвать, что часть отсортированной части. 

Теперь вы глядя на Экран и, вероятно, может сказать, а я могу, что массив отсортировано прямо сейчас. Но мы не можем доказать, что еще. Мы не имеем гарантию что это сортируется. Но это, где своп Счетчик собирается вступить в игру. 

Таким образом, мы завершили проход. Счетчик своп 2. Так что мы собираемся повторить этот процесс снова, повторять, пока счетчик замены не равно 0. Сброс счетчика подкачки 0. Таким образом, мы сбросить его. 

Теперь посмотрим на каждой смежной пары. Это в порядке, 1 и 2. 2 и 3 в порядке. 3 и 4 находятся в порядке. Таким образом, на данный момент, обратите внимание, мы завершили глядя на каждого соседней пары, но счетчик своп по-прежнему 0. 

Если мы не придется переключаться любые элементы, то они должны быть в порядке, от Достоинство этого процесса. И так что эффективность сортов, что мы любим компьютерные ученые, Теперь мы можем объявить весь массив должен быть отсортированы, потому что мы не сделали есть, чтобы поменять какие-либо элементы. Это очень приятно. 

Так что в худшем случае Сценарий с пузырьковой сортировки? В худшем случае массив В полностью обратном порядке, и поэтому мы должны друг пузыря крупных элементов всего путь через массив. И мы эффективно также должны пузырь все маленькие элементы обратно весь путь через массив, тоже. Таким образом, каждый из п элементов должен двигаться по всем другим п элементов. Так что это наихудший сценарий. В лучшем случае сценарий, хотя это немного отличается от выбора рода. Массив уже отсортировано когда мы идем в. Мы не должны делать какие-либо свопы на первом проходе. Таким образом, мы, возможно, придется искать в меньшем количестве элементов, правильно? Мы не должны повторить это обрабатывать несколько раз. 

Так что это значит? Так что в худшем случае для пузырьковой сортировки, и то, что лучший сценарий для пузырьковой сортировки? Вы догадались это? В худшем случае вам придется повторять по всем п элементов п раз. Таким образом, в худшем случае будет н в квадрате. 

Если массив прекрасно отсортированный хотя, вы только должны смотреть друг на элементов сразу. И если счетчик своп по-прежнему 0, Вы можете сказать, что это массив отсортирован. И так, в лучшем случае, это на самом деле лучше, чем выбор sort-- это омега п. 

Я Дуг Ллойд. Это CS50.