Занятие 12. Простейшие алгоритмы для работы с одномерными массивами. Программирование для начинающих.

Добрый день друзья. Продолжаем изучать одномерные массивы. Сегодня у нас важная тема. Изучим основные алгоритмы работы с массивами: поиск в массиве и его сортировка.

Почему я говорю, что этот урок важный? Просто обработка массивов, наряду с работой со строками,  это одна из самых типичных задач в программировании.  Ни для кого не секрет, компьютеры появились для решения вычислительных задач математики.  А вычислительные задачи, обычно связаны с большим объемом однотипных данных, которые где хранятся? Ага, правильно. Массивы.

Итак, не будем тянуть быка за хвост, ухватимся сразу за рога. Начнем с самого простого.

Поиск минимального элемента в массиве.

Поставим задачку. Пускай имеется массив из целых чисел. Необходимо среди всех элементов массива, найти элемент с минимальным значением. 

Это задачка даже не на одну трубку.  Сначала взгляните на картинку, и найдите в этом столбике минимальный элемент.

Рис.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("%d\n", 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 (int j=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("%d\n", 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; Помните, что использовать дополнительные переменные нельзя.

При выполнении заданий, помните о нашей договоренности, код программы оформлять в виде отдельных функций.

Если Вам понравился этот урок, расскажите о нем вашим друзьям. В этом  Вам могут помочь кнопки основных социальных сетей, расположенные ниже. Вам остается всего лишь кликнуть по любой из них.