Настройки
Прогресс
Завершите тренировку, чтобы освоить навык.
Сортировка массива методом пузырька
Сортировка массива — один из основных алгоритмов школьного курса информатики. Метод пузырька упорядочивает массив проходами: в каждом проходе сравниваются соседние элементы, и если левый больше правого, они меняются местами. Тренажер отрабатывает главный шаг этого алгоритма — выполнить один проход вручную, по сравнениям, как его выполняет программа.
Для кого этот тренажер
Тренажер предназначен для 9 класса (тема «Массивы») и для повторения в 11 классе. Нужно знать, что такое массив, элемент массива и индекс, и уметь сравнивать числа. Индексы, как в Python, начинаются с нуля: первый элемент — a[0].
Какие задания встречаются
В каждом задании — массив из 6 или 7 разных чисел от 1 до 99, над каждым элементом записан его индекс. Нужно определить, каким станет массив после первого прохода сортировки пузырьком по возрастанию. Проход идет слева направо, это сказано в каждом задании: сравниваются a[0] и a[1], затем a[1] и a[2] и так до последней пары; обмен выполняется, если левый элемент больше правого.
Массивы подобраны так, что проход меняет местами хотя бы три пары, но не упорядочивает массив целиком. Ответ нельзя получить, просто переставив наибольший элемент в конец или отсортировав весь массив: нужно выполнить все сравнения прохода по порядку, каждый раз с уже измененным массивом.
Что делает ученик
Ученик выполняет сравнения прохода и расставляет числа массива в том порядке, который получится после прохода, меняя местами по два числа. Обменов при расстановке может быть сколько угодно: они не обязаны повторять шаги алгоритма, важен только итоговый массив. Если ответ неверный, отмечаются позиции, где стоит не то число, и называется нарушенное правило, например «После прохода наибольший элемент стоит последним». Расстановку можно исправить и проверить снова.
К каждому заданию есть пошаговое решение: все сравнения прохода по порядку — массив перед сравнением, сравниваемая пара и решение «меняем» или «не меняем», а в конце массив после прохода.
Чему научится ученик
- выполнять проход сортировки пузырьком по массиву вручную;
- сравнивать соседние элементы по индексам a[j] и a[j + 1] и решать, нужен ли обмен;
- учитывать, что каждое следующее сравнение идет с уже измененным массивом;
- объяснять, почему после первого прохода наибольший элемент оказывается последним, а остальные еще не упорядочены;
- понимать, что делает программа сортировки пузырьком, и проверять ее работу трассировкой.
Теория
Сортировка методом пузырька
Сортировка — расстановка элементов массива по порядку. При сортировке по возрастанию каждый следующий элемент не меньше предыдущего.
Проход. Метод пузырька сравнивает соседние элементы слева направо: a[0] и a[1], затем a[1] и a[2] и так до последней пары. Если левый элемент больше правого, их меняют местами. Каждое следующее сравнение идет с уже измененным массивом, поэтому большой элемент движется к концу, как всплывающий пузырек: после первого прохода наибольший элемент стоит последним.
Например, проход по массиву [4, −2, 7, 0, 3] из пяти элементов:
- a[0] и a[1]: 4 > −2 — меняем, массив [−2, 4, 7, 0, 3];
- a[1] и a[2]: 4 < 7 — не меняем;
- a[2] и a[3]: 7 > 0 — меняем, массив [−2, 4, 0, 7, 3];
- a[3] и a[4]: 7 > 3 — меняем, массив [−2, 4, 0, 3, 7].
После прохода наибольший элемент 7 стоит последним, но массив еще не упорядочен: 4 стоит перед 0.
В некоторых учебниках проход ведут с конца массива, тогда к началу перемещается наименьший элемент; в этом тренажере проход идет слева направо.
Следующие проходы. Второй проход ставит на предпоследнее место второй по величине элемент, третий — третий по величине, и так далее. Элементы в конце массива уже на своих местах, их можно не сравнивать. Массив из n элементов упорядочен самое большее за n − 1 проходов. Например, второй проход по [−2, 4, 0, 3, 7]: −2 < 4 — не меняем; 4 > 0 — меняем; 4 > 3 — меняем. Получается [−2, 0, 3, 4, 7], пару 4 и 7 уже не сравниваем.
По убыванию соседей меняют, если левый элемент меньше правого: к концу движется наименьший. Например, проход по [3, 8, 5]: 3 < 8 — меняем, массив [8, 3, 5]; 3 < 5 — меняем, массив [8, 5, 3].
Программа на Python. Внешний цикл считает проходы, внутренний сравнивает соседей. В проходе с номером i последние i элементов уже на своих местах, поэтому внутренний цикл короче на i:
a = [5, 2, 9, 1, 6]n = len(a)for i in range(n - 1): for j in range(n - 1 - i): if a[j] > a[j + 1]: t = a[j] a[j] = a[j + 1] a[j + 1] = tprint(a)
Программа выведет [1, 2, 5, 6, 9]. Обмен через переменную t можно записать в Python и одной строкой: a[j], a[j + 1] = a[j + 1], a[j]. Первый проход — это внутренний цикл при i = 0: j пробегает значения от 0 до n − 2.
Частые ошибки: сравнивать пары через одну (a[0] и a[1], потом сразу a[2] и a[3]); сравнивать числа исходного массива, а не уже измененного; переносить в конец только наибольший элемент и не менять другие пары; выполнить за один проход всю сортировку.