boolean isSorted = false;
String tmp;
while (!isSorted)
{
isSorted = true;
for (int i=0; i < array.length-1; i++)
{
if (isGreaterThan(array[i],array[i+1]))
{
isSorted = false;
tmp = array[i];
array[i] = array[i+1];
array[i+1] = tmp;
}
}
}
Ольга Николаевна Мишенина
20 уровень
Метод пузырька понимаю, но вот не понимаю запись с false и true. Объясните, пожалуйста.
Решен
Комментарии (5)
- популярные
- новые
- старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Hexronimo
19 ноября 2019, 12:41
В вашем примере не самый традиционный метод написания пузырьковой сортировки, и поэтому не особо наглядный, хотя алгоритмически он тот же.
Собственно все так как написал предыдущий комментатор, а вот еще код:
0
Hexronimo
19 ноября 2019, 12:46
Как вы видите, в массиве из моего примера несколько последних чисел уже расположены в правильном порядке, их сортировать не нужно, для такого случая и есть boolean swapped - он даст возможность выйти из массива не проходя эти элементы. Таким образом, в зависимости от данного массива, есть возможность избежать лишних итераций. Это самая простая (и не особо ценная) оптимизация пузырька.
0
Ольга Николаевна Мишенина
20 ноября 2019, 11:28
Спасибо!
0
Pavel KurashovExpert
19 ноября 2019, 12:07
Суть пузырька в том что он бегает по парам значений и меняет их местами если они не по порядку. И собственно перестаёт бегать если все пары стоят по порядку. Поэтому когда мы находим хотя бы одну несортированную пару, мы сбрасывает флаг сортировки и повторяем цикл вновь.
Мне кажется оптимальней назвать этот флаг не isSorted, а например isSwapped, установить его перед циклом в true, сбросить в false в начале цикла, и устанавливать в true если мы нашли и переставили несортированную пару
+1
Ольга Николаевна Мишенина
20 ноября 2019, 11:28
Спасибо!
0