int[] array = {10, 2, 10, 3, 1, 2, 5};
1. System.out.println(Arrays.toString(array));
2. boolean needIteration = true;
3. while (needIteration) {
4. needIteration = false; // допускаем, что наш массив отсортирован, и больше итерироваться не хотим (пояснение с лекции)
5. for (int i = 1; i < array.length; i++) { // Поэтому, мы проходим элементы последовательно и проверяем это допущение (пояснение с лекции)
6. if (array[i] < array[i - 1]) {
7. swap(array, i, i-1);
8. needIteration = true;
9. }
10. }
11. }
12. System.out.println(Arrays.toString(array));
Метод swap не пишу. Не понятна работа строки 4 и строки 8. В строке 4, в моем неправильном понимании работа while, вообще должна завершится, а в строке 8 - вообще не нужна, так как эта булева переменная меняет значение на true в рамках цикла for, т.е. как она должна повлиять на while ? Т.е. переменная needIteration с каждым разом когда отработает swap будет выдавать true. И что ж, когда все будет отсортировано, она не выдаст true. Может, потому, что значение переменной в четвертой строчке отрабатывает только один раз при первом так сказать запуске, и while прекращает работу, когда из внутреннего цикла к нему перестает поступать needIteration = true ? Сам придумал.
Андрей
20 уровень
Вопрос по сортировке пузырьком (https://javarush.ru/groups/posts/1997-algoritmih-sortirovki-v-teorii-i-na-praktike)
Решен
Комментарии (4)
- популярные
- новые
- старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
ПавелFull Stack Developer в Diasoft
12 декабря 2019, 15:35полезный
Ну это конечно не канонический алгоритм пузырька, канонический на википедии можно посмотреть, но по вопросам:
1. Строка 3 не проверяет переменную всегда, а только после каждого прохода тела цикла. То есть переменную внутри цикла while можно менять хоть 500 раз, ничего не будет с while. Значение имеет только чему равна переменная needIteration в конце цикла (к строке 11).
2. Идея алгоритма такова: если хоть один раз мы отсортировали массив (строки 5-9) то переменная needIteration будет равна true, при выходе из цикла for, и это значит мы не закончили сортировку.
Иначе согласно строке 4 переменная needIteration = false и while остановится.
+1
Андрей
12 декабря 2019, 16:20
То если мы отсортировали строки 5-9, переменная обрела значение true, так с чем она сравнивается: со строкой 4, а потом строкой 3? Если так, то как while узнает о значении true? Или true ,которое возвращается из цикла for меняет значение переменной в строке 4? Или строка 4 не берется во внимание (игнорируется) когда значение переменной needIteration = true сравнивается со строкой 3?
Вообще эту четвертую строчку можно визуализировать в виде шлагбаума который пропускает значение true (точнее когда переменная needIteration со значением true возвращается из цикла for)? Или когда ничего не возвращается, (true из цикла for не меняет значение в четвертой строке), и она такой же false-анутой возвращается в 3 строку, таким образов завершая цикл while?
0
ПавелFull Stack Developer в Diasoft
12 декабря 2019, 16:39решение
Ну с оговорками правильно, вот уточнение:
Мы прошли весь массив и если произошла хоть одна перестановка (а это важно, мы не факт что отсортировали весь массив, мы отсортируем весь массив когда не произойдет ни одна перестановка в цикле for) - мы переменную поставили в true. Значение переменной needIteration = true.
Мы прошли по всем элементам, цикл for закончился.
Дальше мы переходим к проверке условия в скобках while (и только тут цикл узнает состояние переменной needIteration, все что до этого происходило с переменной для него безразлично), и прогоняем весь цикл еще раз.
А строка 4 остановит while когда в цикле for не произойдет ни одна из перестановок (мы закончили сортировку) .
+2
Андрей
12 декабря 2019, 21:51
Спасибо Тебе Павел !
0