Алгоритм bubble sort

Question

У меня вопрос о конкретной строке в псевдокоде.

Я не понимаю, почему i = (n-1). означает ли это, что мы должны начать сравнивать с последним элементом (1 и 7)?

Answer 1

№ Элементы, которые сравниваются, имеют индексы j и j+1. На первой итерации внутреннего цикла j==0, чтобы вы сравнили элементы 5 и 9.

Проведите некоторое время «запустив» алгоритм вручную.

Answer 2

Нет, ваш алгоритм сортировки «пузырь» всегда работает с первого взгляда. Несмотря на то, что внешний цикл отсчитывается в обратном направлении, переменная i никогда не используется для обращения к индексу массива, только j, который определен во внутреннем цикле. Скорее, внешний цикл в вашем коде используется для определения того, насколько высок счет в ваших внутренних циклах, представляющих, сколько сравнений нам нужно преформировать.

---

код работает следующим образом:
Предполагая, что A держит наш массив: [5,9,2,7,1], «п» является 5, длина массива, и наша swap функция работает, внешняя петля RAN:
for i=(n-1) to 1 , Это устанавливает i в 4. Цикл будет работать 4 раза. Переменная i в нашем коде представляет количество сравнений.
Внутренний цикл:
for j = 0 to (i-1) это устанавливает j в 0. Цикл будет работать 4 раза.
Наш Условный оператор называется:
if A[j] < A[j+1] таким образом, сравнивая индексы 0 и 1. A[0] имеет 5 и A[1] имеет 9. С 5 меньше, чем 9, наш, если-утверждение верно.
swap(A[j],A[j+1]) называется. Теперь наш массив: [9,5,2,7,1]

Наш внутренний цикл снова запускается, j = 1.
Наша инструкция if сравнивает индексы 1 и 2. A[1] имеет 5 и A[2]. 2. Поскольку значение 5 не меньше 9, наш оператор if является ложным.

Наш внутренний цикл снова запускается, j = 2.
Наша инструкция if сравнивает индексы 2 и 3. A[2] имеет 2 и A[3]. 7. Поскольку 2 меньше 7, наше утверждение if истинно.
swap(A[j],A[j+1]) называется. Наш массив теперь читает: [9,5,7,2,1]

Наш внутренний цикл снова запускается, j = 3.
Наш оператор if сравнивает индексы 3 и 4. A[3] имеет 2 и A[4] 1. Наш оператор if является ложным.

Наш внутренний цикл завершен, теперь мы знаем, что наш последний элемент правильный. Итак, мы снова запускаем наш внешний цикл. i теперь 3, так как наш последний элемент правильный.

Мы управляем нашей внутренней петлей с j = 0.он будет работать до i, который равен 3.

A[0] содержит 9 и A[1] имеет 5, наш оператор if является ложным.
Следующий цикл, j = 1.
A [1] имеет 5 и A [2]. 7. наше if-statement истинно, поэтому мы их заменяем. Наш массив теперь читается: [9,7,5,2,1]
Наша логика продолжается до тех пор, пока мы не уверены, что наш второй-последний элемент правильный.
После того, как наш внутренний цикл завершен, мы снова закончим внешний цикл:
i теперь 2, количество сравнений.
Наши внутренние петлевые пожары с j = 0 до 1.
Таким образом, мы сравниваем индексы 0 с 1 и 1 с 2. Оба значения дают false.
Теперь мы уверены, что наш средний элемент правильный.
i сейчас 1, что означает, мы делаем одно сравнение.
Наш внутренний цикл работает с j = 0 до 0:
Таким образом, мы сравниваем индексы 0 и 1, так как наш оператор if является ложным, мы ничего не меняем.
Наша внутренняя петля завершается.
Теперь мы уверены, что наш второй элемент правильный.
Наша внешняя петля завершается.
Теперь мы уверены, что весь наш массив правильный.

---

Наш массив теперь сортируется: [9,7,5,2,1]

Алгоритм также отлично работает в худшем случае:
http://jsfiddle.net/mw5L8qzL/
(пустой массив, а массив с одним элементом в комплекте)

Answer 3

Внешняя петля «пузыривает» максимальный элемент в диапазоне A [0, ..., i] в слот A [i]. Поэтому на следующей итерации вы можете забыть об A [i] и ограничить задание сортировкой A [0, ..., i-1]. Очевидно, что когда размер проблемы один после n-1 итераций внешнего цикла, вы остаетесь с одним элементом в диапазоне, поэтому вы останавливаетесь на нем.