Сортировка массивов
М4.1. Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива.
М4.2. Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок.
М4.3. Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа.
М4.4. Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине. Используйте сортировку слиянием.
Пример:
Массив: 5 3 4 2 1 6 3 2
После сортировки: 2 3 4 5 6 3 2 1
М4.5. Напишите программу, которая сортирует массив и находит количество различных чисел в нем.
Пример:
Массив: 5 3 4 2 1 6 3 2 4
После сортировки: 1 2 2 3 3 4 4 5 6
Различных чисел: 6
М4.6. Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «методом пузырька» и слиянием. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.
М4.7. Напишите программу, которая сортирует массив по убыванию. Используйте алгоритм быстрой сортировки.
М4.8. Массив содержит четное количество элементов. Напишите программу, которая сортирует по возрастанию отдельно элементы первой и второй половин массива. Каждый элемент должен остаться в «своей» половине. Используйте алгоритм быстрой сортировки.
Пример:
Массив: 5 3 4 2 1 6 3 2
После сортировки: 2 3 4 5 1 2 3 6
М4.9. Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Используйте алгоритм быстрой сортировки.
Пример:
Массив: 5 3 4 2 1 6 3 2 4
После сортировки: 1 2 2 3 3 4 4 5 6
Различных чисел: 5