Добрый день друзья. Продолжаем изучать одномерные массивы. Сегодня у нас важная тема. Изучим основные алгоритмы работы с массивами: поиск в массиве и его сортировка.
Почему я говорю, что этот урок важный? Просто обработка массивов, наряду с работой со строками, это одна из самых типичных задач в программировании. Ни для кого не секрет, компьютеры появились для решения вычислительных задач математики. А вычислительные задачи, обычно связаны с большим объемом однотипных данных, которые где хранятся? Ага, правильно. Массивы.
Итак, не будем тянуть быка за хвост, ухватимся сразу за рога. Начнем с самого простого.
Поиск минимального элемента в массиве.
Поставим задачку. Пускай имеется массив из целых чисел. Необходимо среди всех элементов массива, найти элемент с минимальным значением.
Это задачка даже не на одну трубку. Сначала взгляните на картинку, и найдите в этом столбике минимальный элемент.
 |
| Рис.1 Одномерный массив |
А теперь стоп. Задумайтесь на секундочку, как вы это сделали? Скорее всего, вы пробежались по столбику глазами, и выявили там самое меньшее число. Аналогичную процедуру должна выполнить и наша программа.
Первым делом следует подумать, где будет храниться минимальное значение. Для него необходима отдельная переменная. Назовем её min. Сохраним в неё значение первого элемента массива, чтобы нам было с чем сравнивать. Дальше нужно пройтись по массиву. Это не сложно, организуем для этого цикл. В работе с массивами в большинстве случаев используется цикл for. Так как там сразу же есть счетчик, который меняется каждой итерации. Теперь основная часть алгоритма. Нам нужно последовательно сравнивать элементы массива с минимальным, и если окажется так, что элемент массива меньше минимального, то следует сохранить это значение вместо него. Вот, в принципе, и весь алгоритм.
Теперь запишем это все в виде программы.
Листинг 12.1
#include <stdio.h>
int main(){
int min, arr[11]={5,14,7,4,11,2,6,12,8,7,3};
min = arr[0];
for (int i=1; i<11; i++){
if (arr[i]<min)
min = arr[i];
}
printf("%dn", min);
return(0);
}
int main(){
int min, arr[11]={5,14,7,4,11,2,6,12,8,7,3};
min = arr[0];
for (int i=1; i<11; i++){
if (arr[i]<min)
min = arr[i];
}
printf("%dn", min);
return(0);
}
Обратите внимание, что в данном случае мы задали элементы массива при его объявлении. Запомните этот способ, он тоже иногда бывает полезен. Кстати, если бы мы объявили не все элементы, а лишь часть из них, то все остальные, автоматически заполнились бы нулями. Можете это проверить самостоятельно.
В дополнение к словесному описанию проиллюстрируем картинкой работу нашей программы.
 |
| Рис. 2 Иллюстрация поиска минимума в одномерном массиве. |
Еще раз посмотрите приведенный выше код, вам должно быть в нем все понятно. Аналогично можно найти максимальный элемент в массиве.
Сортировка массива.
Теперь пускай нам необходимо отсортировать массив, например, по возрастанию. То есть в начале стоит самый маленький элемент, а в конце самый большой. Будем рассматривать самый простой алгоритм сортировки – сортировка обменом. Другое название этой сортировки - сортировка «пузырьком».
Рассмотрим, как говорит мой преподаватель по курсу «методы оптимизации», философию метода.
Для определенности будем считать, что имеем дело с целочисленным массивом. Начиная с первого элемента, поочередно сравниваем соседние элементы, т.е. первый и второй, второй и третий, третий и четвертый и так до конца массива. Если упорядоченность массива нарушена, то меняем эти элементы местами. Так как мы упорядочиваем массив по возрастанию, в нашем случае первый элемент должен быть меньше следующего.
Давайте рассмотрим иллюстрирующую этот шаг алгоритма картинку.
 |
| Рис. 3. Пример первого шага сортировки одномерного массива методом обмена. |
Как видите, самый тяжелый элемент – тонет, то есть опускается на самый низ. А более легкие элементы, как бы всплывают, как пузырьки в воде. Отсюда, в принципе, и название алгоритма. Как видите, после одного прохода алгоритма, на последнее место. Получается, после одного шага алгоритма один элемент уже точно занимает свое место, и при следующем проходе, нам уже нет необходимости сравнивать предпоследний и последний элемент, так как последний элемент уже на своем месте и ничего менять не придется, так зачем лишнее действие? Правильно, незачем. А мы и не будем.
Повторяя описанную процедуру n-1 раз (здесь n – размерность массива) получим полностью отсортированный массив.
На следующем рисунке проиллюстрирована работа алгоритма, на примере небольшого массива.
 |
| Рис. 4. Иллюстрация сортировки массива методом "пузырька". |
Приведем код реализации алгоритма сортировки пузырьком, на языке Си. Обратите внимание на поясняющие комментарии.
Листинг 12.2
#include <stdio.h>
int main(){
int n=6, // размерность массива
arr[6]={5,14,7,4,11,2}; // массив для сортировки
for (int i=n-1;i>0;i--)
for (intj=0;j<i;j++)
if(arr[j]>arr[j+1]){ // если порядок нарушен
//меняем j и j+1 элементы массива местами
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
//выводим массив на экран
for (int i=0;i<n; i++)
printf("%dn", arr[i]);
return(0);
}
int main(){
int n=6, // размерность массива
arr[6]={5,14,7,4,11,2}; // массив для сортировки
for (int i=n-1;i>0;i--)
for (intj=0;j<i;j++)
if(arr[j]>arr[j+1]){ // если порядок нарушен
//меняем j и j+1 элементы массива местами
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
//выводим массив на экран
for (int i=0;i<n; i++)
printf("%dn", arr[i]);
return(0);
}
Помните, мы говорили, что на каждом шаге нам нужно сокращать длину основного цикла? Т.е. сначала проходим все элементы до n-1, на следующем шаге до n-2 и т.д. В приведенном выше алгоритме это реализовано внешним циклом. Обратите внимание, что мы впервые используем направление цикла «сверху вниз». Т.е. движемся не от единицы к n, а наоборот, от n-1 к 1.
На этом сегодняшнее занятие окончено.
Задание для практической работы.
- Задан целочисленный массив a. Написать программу, которая ищет максимальный элемент в массиве и выводит на экран его номер. Обратите внимание не значение, а номер элемента в массиве.
- Задан целочисленный массив arr[1000], в котором существует минимум 10 различных значений. Найти 10 по величине элемент массива.
- Задан целочисленный массив arr[40] . Найти количество элементов массива, которые по модулю меньше произвольного наперед заданного числа. Вывести количество таких элементов в массиве.
- Составьте функцию, которая по заданному массиву определяет, есть ли в массиве хотя бы один отрицательный элемент.
- В уроке был приведен кусок кода, в котором с помощью дополнительной переменной меняются местами два элемента массива. Подумайте, как можно обменять значения двух переменных, не используя дополнительной переменной. Т.е. например, int a=3, b=5; должно стать a=5, b=3; Помните, что использовать дополнительные переменные нельзя.
При выполнении заданий, помните о нашей договоренности, код программы оформлять в виде отдельных функций.
Если Вам понравился этот урок, расскажите о нем вашим друзьям. В этом Вам могут помочь кнопки основных социальных сетей, расположенные ниже. Вам остается всего лишь кликнуть по любой из них.
Если Вам понравился этот урок, расскажите о нем вашим друзьям. В этом Вам могут помочь кнопки основных социальных сетей, расположенные ниже. Вам остается всего лишь кликнуть по любой из них.