Простейшие сортировки
Одной из основных операций, производимых над массивами, являются операции сортировки или упорядочивания элементов массива по какому-либо признаку: чаще по возрастанию или убыванию – для чисел, и по алфавиту – для символов и строк.
Сортировок придумано множество, и, говорят, тому, кто придумает новый эффективный метод сортировки, сразу будет вручена Нобелевская премия.
С древних времен, однако, до нас дошли два самых простых (но, конечно, не самых эффективных) способа сортировки, которые мы здесь и рассмотрим.
Сортировка выбором
Допустим, дан числовой массив из N элементов. Надо отсортировать его по возрастанию.
Суть способа в следующем. Находим наибольший элемент в массиве и меняем его местами с последним. Уменьшаем количество рассматриваемых элементов на 1 (т. к. последний элемент уже на своем месте). Повторяем операцию для уменьшенного на единицу массива. И так – N-1 раз.
Пусть дан массив из пяти элементов:
8 4 9 6 7
Рассмотрим процесс упорядочивания по шагам.
На этом шаге третий элемент поменялся сам с собой.
267. Напишите программу для упорядочивания массива по возрастанию методом выбора. Измените программу так, чтобы она упорядочивала массив по убыванию.
268. Дан массив из 13 чисел. Расположите числа по возрастанию. Введите с клавиатуры число М так, чтобы оно вошло в массив и получившийся массив также был бы упорядочен по возрастанию.
Метод обмена или "пузырька"
Название данного метода часто вызывает нездоровый смех у молодежи, хотя никакого тайного смысла у этого метода нет. Просто он выполняется таким образом, что максимальное число после каждого шага сортировки как бы всплывает в конец массива, на свое заслуженное место. Заключается метод в следующем. Программа, начиная с первых элементов массивов, сравнивает эти элементы попарно, и, в случае, если они расположены не по возрастанию, меняет их местами. В результате (N -I)2 перестановок (в случае самого плохого расположения элементов массива – все элементы по убыванию) массив окажется упорядочен по возрастанию. Например, есть массив из четырех элементов:
4 3 2 1
Рассмотрим по шагам метод "пузырька" для этого массива.
269. Напишите программу, реализующую метод "пузырька". Для уменьшения количества ненужных сравнений может служить счетчик, подсчитывающий количество обменов за один полный пробег вдоль всего массива. Как только его значение станет равно нулю (т. е. ни одного нового обмена не будет произведено), это будет означать, что массив упорядочен. Для наглядности оформите исходный и получившийся массив в виде столбиковых интерпретаций друг под другом.
270. Дан массив букв, составляющих английский алфавит, но размешенных не по порядку. Напишите программу, преобразующую этот массив в алфавит английского языка.
271. Дан массив из 13 четырехбуквенных русских слов (существительных и нарицательных), в единственном числе, в именительном падеже. Упорядочить их по алфавиту.