Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад
Новый рекорд!

Очки опыта

0

Обракоины

0
Как вам тренажер?

Следующая тема
Очки
0
Решено
0
Время
00:00:00

Бесплатные занятия

Оформите подписку, чтобы заниматься без ограничений.

Вы не вошли в аккаунт

Создайте бесплатный аккаунт, чтобы сохранить прогресс и получить персональную подборку полезных материалов.

Настройки

Остановка

Длительность тренировки

Времени на один вопрос

Другие тренажеры по теме
Cледующая тема
Cледующая тема
Все тренажеры Все тренажеры

Ошибки

Здесь появятся ошибки, допущенные во время тренировки.

Прогресс

Завершите тренировку, чтобы освоить навык.

О тренажере

Сортировка массива методом пузырька

Сортировка массива — один из основных алгоритмов школьного курса информатики. Метод пузырька упорядочивает массив проходами: в каждом проходе сравниваются соседние элементы, и если левый больше правого, они меняются местами. Тренажер отрабатывает главный шаг этого алгоритма — выполнить один проход вручную, по сравнениям, как его выполняет программа.

Для кого этот тренажер

Тренажер предназначен для 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] = t
print(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]); сравнивать числа исходного массива, а не уже измененного; переносить в конец только наибольший элемент и не менять другие пары; выполнить за один проход всю сортировку.

Вернуться к тренажерам Вернуться к тренажерам

Предложить улучшение