Уроки 49 - 50
Сортировка массивов
§64. Сортировка
Содержание урока
Метод пузырька (сортировка обменами)
Метод пузырька (сортировка обменами)
Название этого метода произошло от известного физического явления — пузырёк воздуха в воде поднимается вверх. Если говорить о сортировке массива, сначала поднимается «наверх» (к началу массива) самый «лёгкий» элемент (элемент с минимальными значениями), затем следующий и т. д.
Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно (меньший элемент «ниже»), то меняем их местами. Далее так же рассматриваем следующую пару элементов и т. д. (рис. 8.11).
Рис. 8.11
После обработки пары (А[1], А[2]) минимальный элемент стоит на месте А[1]. Это значит, что на следующих этапах его можно не рассматривать. Первый цикл, устанавливающий на свое место первый (минимальный) элемент, можно на псевдокоде записать так:
Здесь j — целочисленная переменная. Обратите внимание, что на очередном шаге сравниваются элементы А[j] и А[j+1], поэтому цикл начинается с j = N - 1. Если начать с j = N, то на первом же шаге получаем выход за границы массива — обращение к элементу А[N+1].
За один проход такой цикл ставит на место один элемент. Чтобы «подтянуть» второй элемент, нужно написать ещё один почти такой же цикл, который будет отличаться только конечным значением j в заголовке цикла. Так как верхний элемент уже стоит на месте, его не нужно трогать:
При установке 3-го элемента конечное значение для j будет 3 и т. д. Таких циклов нужно сделать N - 1: на 1 меньше, чем количество элементов массива. Почему не N? Дело в том, что если N - 1 элементов поставлены на свои места, то оставшийся автоматически встает на своё место — другого места нет. Поэтому полный алгоритм сортировки представляет собой такой вложенный цикл:
Записать полную программу на выбранном языке вы можете самостоятельно.
Следующая страница 
Метод выбора
Cкачать материалы урока
