[Powered by Google Translate] [Пузырьковой сортировки]
[JACKSON Steinkamp HARVARD UNIVERSITY]
[Это CS50. CS50TV]
Bubble Сортировка пример алгоритма сортировки -
то есть, порядок сортировки набор элементов в
возрастанию или по убыванию.
Например, если вы хотите отсортировать массив, состоящий из чисел
[3, 5, 2, 9], правильное применение пузырьковой сортировки вернется
упорядоченный массив [2, 3, 5, 9] в порядке возрастания.
Теперь, я собираюсь объяснить, в псевдокоде, как работает алгоритм.
>> Скажем, мы сортировка список из 5 чисел - 3, 2, 9, 6 и 5.
Алгоритм начинается, глядя на первые два элемента, 3 и 2,
и проверки, если они вышли из строя по отношению друг к другу.
Они - 3 больше, чем 2.
Чтобы быть в порядке возрастания, они должны быть наоборот.
Таким образом, мы поменять их местами.
Теперь список выглядит следующим образом: [2, 3, 9, 6, 5].
>> Далее мы посмотрим на второй и третий элементы, 3 и 9.
Они в правильном порядке относительно друг друга.
То есть, 3 меньше, чем 9, так что алгоритм не поменять их местами.
Далее, мы смотрим на 9 и 6. Они вышли из строя.
>> Итак, нам нужно, чтобы поменять их местами, потому что 9 больше, чем 6.
Наконец, мы посмотрим на последние два целых числа, 9 и 5.
Они вышли из строя, поэтому они должны быть заменены.
После первого полного прохода по списку,
это выглядит так: [2, 3, 6, 5, 9].
Не плохо. Это почти отсортирован.
Но нам нужно запустить через список еще раз, чтобы получить его полностью отсортирован.
Два меньше, чем 3, поэтому мы не поменять их местами.
>> Три составляет менее 6, так что мы не поменять их местами.
Шесть превышает 5. Мы поменялись местами.
Шесть меньше, чем 9. Мы не поменять.
После второй проход, она выглядит следующим образом: [2, 3, 5, 6, 9]. Perfect.
Теперь, давайте запишем его в псевдокоде.
В принципе, для каждого элемента в списке, мы должны смотреть на это
и элемент непосредственно в своем праве.
Если они не в порядке относительно друг друга - то есть, если элемент слева
больше, чем тот, на правом - мы должны поменять местами два элемента.
>> Мы делаем это для каждого элемента списка, и мы сделали один проход.
Теперь мы просто должны сделать сквозной достаточное количество раз, чтобы убедиться, что список
полностью, правильно сортируются.
Но сколько раз мы должны пройти через список
гарантировать, что мы сделали?
Ну, худшем случае, если мы имеем совершенно обратную списка.
Тогда она принимает ряд пройти проходные равно числу
элементов N-1.
Если это не имеет смысла, интуитивно, думаю простой случай - список [2, 1].
>> Это будет взять один проход, чтобы отсортировать правильно.
[3, 2, 1] - В худшем случае в том, что с 3 элементы сортируются в обратном направлении,
он собирается взять 2 итераций для сортировки.
После одной итерации, это [2, 1, 3].
Второй дает упорядоченный массив [1, 2, 3].
Таким образом, вы знаете, никогда не должны идти через массив, в общем,
больше, чем N-1 раз, где п-число элементов в массиве.
Это называется Bubble Сортировка потому, что крупнейшие элементы, как правило, «пузырь вверх"
справа довольно быстро.
На самом деле, этот алгоритм имеет очень интересное поведение.
>> После т итераций через весь массив,
правые элементы м гарантировано
должны быть отсортированы в их правильном месте.
Если вы хотите в этом убедиться,
мы можем попробовать его на совершенно обратную список [9, 6, 5, 3, 2].
После одного прохода через весь список,
[Звук письменной форме]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
правый элемент 9 находится в надлежащем месте.
После второй проход, 6 будет иметь "пропускают вверх", чтобы
вторую справа место.
Эти два элемента справа - 6 и 9 - будет в их правильных местах
После первых двух проход проходные.
>> Итак, как мы можем использовать это, чтобы оптимизировать алгоритм?
Ну, а после одной итерации по массиву
Мы на самом деле не нужно проверять правый элемент
потому что мы знаем, что это отсортированы.
После двух итераций, мы знаем наверняка, самая правая из двух элементов на месте.
Так, в общем, после к итераций полный массив,
Проверка последнего к элементов является избыточным, так как мы знаем,
они в нужном месте уже.
>> Так что если вы сортировки массива из п элементов,
на первой итерации - вы будете иметь, чтобы отсортировать все элементы - первые п-0.
На второй итерации, вы должны смотреть на все элементы, кроме последнего -
первые N-1.
Другая оптимизация может быть, чтобы проверить, если список уже отсортирован
после каждой итерации.
Если он уже отсортированы, мы не должны сделать больше итераций
по списку.
Как мы можем это сделать?
Ну, если мы не делаем никаких свопов на проходной части списка,
ясно, что этот список был уже отсортирован, потому что мы не менять ничего.
Таким образом, мы, безусловно, не должны сортировать снова.
>> Может быть, вы могли бы инициализировать флаг переменная называется "Не отсортировано к
ложными и изменить его на истинный если у вас есть, чтобы обменять любые элементы на
одна итерация по массиву.
Или аналогично, сделать встречное подсчитать, сколько свопов вы делаете
на любой итерации.
В конце итерации, если не поменять любой из элементов,
Вы знаете, в список уже отсортирован, и все готово.
Bubble Сортировка, как и другие алгоритмы сортировки, может быть
переделаны, чтобы работать для любых элементов, которые имеют заказа методом.
>> То есть, при наличии двух элементов у вас есть способ сказать, если первая
больше, равно или меньше, чем второй.
Например, вы можете отсортировать буквы алфавита, сказав,
, что <B, B <C, и т.д.
Или вы можете отсортировать дни недели, где воскресенье считается менее понедельника
что меньше, чем во вторник.
>> Bubble Сортировка отнюдь не очень эффективны или быстрый алгоритм сортировки.
В наихудшем случае время работы от батарей Big O н ²
потому что вы должны сделать п итераций по списку
проверка всех п элементов, каждый проход, пхп = п ².
Это время выполнения означает, что как число элементов, вы сортировке увеличивается,
время выполнения увеличивается квадратично.
>> Но если эффективность не является главной заботой вашей программы
или если вы только сортировка небольшого числа элементов,
Вы могли бы найти Bubble Сортировка полезно, потому что
это один из простейших алгоритмов сортировки, чтобы понять
и код.
Это также отличный способ получить опыт работы с переводом теоретических
алгоритм в реальном коде функционирования.
Ну, вот и пузырьковой сортировки для вас. Спасибо за просмотр.
CS50.TV