5.5. Сортировка обменом ("пузырьковая" сортировка)

Принцип метода:

Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент ("всплыл" первый "пузырек"). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до (n - 1)-го элемента. И так далее. Всего требуется (n - 1) проход.

Программа, реализующая метод обмена ("пузырька"), будет иметь следующий вид:

ClrList↵
"Введите длину массива " : ? →N ↵
For 1→I To N ↵
"Введите" : I
"-й элемент массива" ↵
?→List 1 [ I ] ↵
Next ↵
List 1
For N→K To 2 Step -1 ↵
For 1→I To K-1 ↵
If List 1 [ I ]< List 1 [ I+1 ] ↵
Then List 1 [ I ] →B↵
List 1 [ I+1 ] → List 1 [ I ] ↵
B→ List 1 [ I+1 ] ↵
IfEnd ↵
Next ↵
Next ↵
List 1

Язык программирования CASIO имеет встроенную функцию сортировки (Sort), которая существенно облегчает решение подобных задач.

Пример 22.
Заполнить одномерный массив из n элементов целых чисел. Упорядочить его:
а) по возрастанию;
б) по убыванию

ClrList↵
"Введите длину массива " : ? →N ↵
For 1→I To N ↵
"Введите элемент массива " : I
?→List 1 [ I ] ↵
Next ↵
SortA(List 1) ↵ /по возрастанию/
List 1
SortD(List 2) ↵ /по убыванию/
List 1

Задачи

87. Заполнить массив из n элементов целых чисел, упорядочить его:
а) по возрастанию;
б) по убыванию.

88. Заполнить одномерный массив из n элементов чисел. Упорядочить первую половину элементов по возрастанию, вторую - по убыванию.

89. Заполнить одномерный массив из n элементов чисел. Упорядочить первую половину элементов по убыванию, вторую - по возрастанию.

90. Заполнить одномерный массив из n элементов чисел. Необходимо переставить элементы массива так, чтобы в начале шла группа элементов, больших того, который в исходном массиве располагался на первом месте, затем сам этот элемент, потом - группа элементов, меньших или равных ему.

91. Заполнить одномерный массив из n элементов чисел. Найти наибольший элемент, встречающийся в массиве после выбрасывания максимального элемента.

92. Ввести два одномерных массива с различным количеством элементов и натуральное число k. Объединить их в один массив, включив второй массив между k-м и (k+1)-м элементами первого, не используя дополнительный массив.

93. В массиве А каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все единицы, затем все двойки и, наконец, все нули (дополнительного массива не заводить).

94. Заполнить одномерный массив из n элементов чисел. Упорядочить элементы массива, стоящие на нечетных местах, в возрастающем порядке, а на четных - в убывающем.

95. Из двух упорядоченных одномерных массивов (длины K и N) сформируйте одномерный массив размером K+N, упорядоченный так же, как исходные массивы.

96. Ввести целочисленный массив. Сформировать второй массив всех таких различных значений, которые в первом массиве встречаются по два и более раза.