54
7.2. Сортировка в одномерном массиве
Очевидно, что элементы массива, как правило, располагаются в произвольном порядке. Но во многих случаях может понадобиться расположить их, например, в порядке возрастания. Такая процедура упорядочения называется сортировкой.
Рассмотрим простейший способ сортировки– метод пузырька. Суть его в том, что последовательно сравниваются элементы массива и, если очередной элемент меньше предыдущего, то их меняют местами.
Пример 7.3. Ввести одномерный массив и упорядочить его методом пузырька.
Для ясности приведем блок-схе- му алгоритма такой сортировки (рис. 8.16).
Рис. 8.16. Блок-схема алгоритма сортировки массива методом пузырька
55
Соответственно текст программы имеет вид:
#include <iostream> |
|
|
#include <windows.h> |
|
|
using namespace std; |
|
|
int main() |
char str[256]; |
|
{ int i,j, a[11],b; |
||
AnsiToOem("введи |
a[",str); |
|
for (i=1; i<=10; i++) |
||
{ |
cout<<str<<i<<"] "; cin>>a[i];} |
|
for (i=1; i<=9; i++) for (j=1; j<=9; j++)
{ if (a[j]>a[j+1]){b=a[j];a[j]=a[j+1]; a[j+1]=b;}} for (i=1; i<=10; i++)
{ cout<<"\n a["<<i<<"] "<<a[i];} cout<<"\n"; return(0);}
Результат работы такой программы (см. рис. 8.17):
Рис. 8.17. Результат работы программы сортировки массива методом пузырька
Практические задания
7.1. Дан массив из N элементов. Отсортировать его по возрастанию элементов и вывести. Вывести квадраты элементов с нечетными номерами.
56
7.2. Дан массив из N элементов. Отсортировать его по убыванию элементов и вывести. Найти сумму элементов с четными номерами и отдельно – с нечетными номерами.
7.3. Дан массив из N элементов (натуральные числа). Отсортировать его по возрастанию элементов и вывести. В нем четные числа заменить на 0, нечетные – на –1. Вывести итоговый массив.
7.4. Дан массив из N элементов (N – четное). Отсортировать его по убыванию элементов и вывести. Распечатать его в следующем
порядке: a1, aN, a2, aN–1, ... , aN/2, aN/2+1.
7.5. Дан массив из N элементов (N – четное). Отсортировать его по возрастанию элементов и вывести. В нем элементы с четными и нечетными номерами поменять местами: а1 с а2, а3 с а4 и т.д. Вывести итоговый массив.
7.6. Даны два массива, каждый из N элементов. Отсортировать первый массив по убыванию элементов и вывести. Составить третий массив, в который поочередно входят элементы из 1–го и из 2– го массивов и вывести его на печать.
7.7. Дан массив из N элементов (N – четное). Отсортировать его по возрастанию элементов и вывести. Составить вдвое меньший массив, элементами которого являются: сумма 1-го и последнего, 2-го и предпоследнего элементов исходного массива и т.д. Вывести итоговый массив.
7.8. Дан массив из N элементов (натуральные числа). Отсортировать его по убыванию элементов и вывести. Определить, количество элементов, которые являются нечетными числами.
7.9. Дан массив из N элементов (натуральные числа). Отсортировать его по возрастанию элементов и вывести. Определить количество элементов, кратных 3.
7.10. Дан массив из N элементов (натуральные числа). Отсортировать его по убыванию элементов и вывести. Определить количество элементов, имеющих четные порядковые номера и являющихся нечетными числами.
7.11. Дан массив из N элементов (натуральные числа). Отсортировать его по убыванию элементов и вывести. Определить сумму тех элементов, которые кратны 5.
7.12. Дан массив из N элементов (целые числа). Отсортировать его по возрастанию элементов и вывести. Определить сумму тех, которые нечетны и отрицательны.
7.13. Дан массив из N элементов (натуральные числа). Отсортировать его по убыванию элементов и вывести. Определить среднее арифметическое кратных 5, но не кратных 10.
57
7.14. Дан массив из N элементов (натуральные числа). Отсортировать его по возрастанию элементов и вывести. Определить произведение элементов, кратных заданному числу Р.
7.15. Дан массив из N элементов (натуральные числа). Отсортировать его по убыванию элементов и вывести. Определить количество элементов, кратных 3, но не кратных 5.
7.16. Написать программу, которая вычисляет среднее арифметическое элементов заданного массива без учета минимального и максимального элементов массива. Заданный массив отсортировать по возрастанию и вывести.
7.17. Написать программу, которая вычисляет среднюю (за неделю) температуру воздуха. Исходные данные должны вводится во время работы программы в массив. Заданный массив должен быть отсортирован по убыванию.
7.18. Написать программу, которая проверяет, находится ли введенное с клавиатуры число в массиве. Массив также должен вводится во время работы программы, затем упорядочен по возрастанию.
7.19. Написать программу, которая проверяет, представляют ли элементы введенного с клавиатуры массива возрастающую последовательность и если нет – упорядочить элементы по убыванию.
7.20. Написать программу, которая вычисляет, сколько раз введенное с клавиатуры число встречается в заданном массиве. Исходный массив отсортировать по возрастанию и вывести.
7.21. Написать программу, которая проверяет, есть ли во введенном извне массиве элементы с одинаковыми значениями. Исходный массив отсортировать по убыванию и вывести.
7.22. Написать программу, которая определяет количество учеников в классе, чей рост превышает средний. «Расставить» учеников по росту (в порядке убывания)
7.23. Написать программу, которая вводит с клавиатуры одномерный массив из 15 целых чисел, после чего выводит количество ненулевых элементов. Перед вводом каждого элемента должна появляться подсказка с номером элемента. Введенный массив отсортировать по возрастанию и вывести.
7.24. Написать программу, которая вычисляет среднее арифметическое ненулевых элементов введенного массива из целых чисел. Введенный массив отсортировать по убыванию и вывести.
7.25. Написать программу, которая выводит минимальный элемент введенного с клавиатуры массива из целых чисел. Введенный массив отсортировать по возрастанию и вывести.