В большинстве случаев, массивы применяются для хранения большого количества однотипной информации, создания и организации баз и банков данных и т.д. Во многих случаях номер (индекс) элемента в массиве не играет большой роли. Важно именно его значение, т.е. сама информация. Базы и банки данных, в свою очередь, необходимы не только для того, чтобы "складывать" в них информацию, но и для того, чтобы в любой момент была возможность удобного и быстрого доступа к ней. В обычном "неотсортированном" массиве информацию найти можно, но только уже известным Вам способом последовательного перебора-просмотра всех его элементов, до тех пор, пока нужный элемент не будет обнаружен. Этот самый простой метод обладает только одним но очень существенным недостатком - на поиск одного элемента уходит много времени. Все остальные методы поиска информации намного эффективнее, быстрее, но применяются только в упорядоченных, отсортированных массивах. Поэтому часто возникает задача об упорядочивании массива. Рассмотрим простой случай такой задачи: дан числовой массив x1, x2, ... xn, элементы которого попарно различны; требуется переставить элементы массива так, чтобы после перестановки они были упорядоченны в порядке возрастания: x1 < x2 < ... < xn. Существует несколько алгоритмов решения этой задачи. Мы рассмотрим два наиболее популярных.

Алгоритм сортировки выбором

Очевидно, что первое место в массиве должен занять минимальный элемент массива, второе - наименьший из всех остальных, третий - наименьший из оставшихся и т.д.

Для этого необходимо выполнить следующую последовательность действий:

1. Определить минимальный элемент массива;
2. Поменять его местами с первым элементом;
3. Определить минимальный элемент среди оставшихся;
4. Поменять его местами со вторым элементом и т.д.

Эта последовательность действий должна выполняться до тех пор, пока не будет определён последний минимальный элемент.

Всю операцию по упорядочиванию массива можно разбить на более простые задачи.

Первая - поиск минимального элемента. Предлагаемый фрагмент программы напомнит Вам, как это делается.

       min:=m[1];  {допустим, что 1-й элемент - минимален}
       t:=1;       {и его номер = 1}
      FOR i:=1 TO 30 DO
       if m[i]<min then     {проверка нашего утверждения}
                     begin
                      min:=m[i];
                      t:=i;
                     end;
       Writeln('Минимальный элемент последовательности равен ',min);
       Writeln('Номер минимального элемента ',t);

Вторая - замена местами минимального элемента с номером t с элементом N 1, в первом случае, и с номером i в общем случае. Для этого необходимо объявить дополнительную переменную buf тип которой должен совпадать с типом элементов массива, и выполнить последовательность действий:

     buf:=m[t];   {сохранить в буфере значение минимального элемента}
     m[t]:=m[i];  {в ячейку, хранившую минимальный элемент}
                  {записать значение элемента N i}
     m[i]:=buf;   {в ячейку N i записать из буфера значение минимума}

Теперь Вы можете разобраться в фрагменте программы, который выполняет полную сортировку массива состоящего из 40 элементов по возрастанию (от меньшего элемента к старшему)

    REPEAT
     ind:=true {предположим что массив уже отсортирован}
     FOR i:=1 TO 39 DO {цикл для организации просмотра}
       if m[i]>m[i+1] then  {сравнение двух соседних элементов}
          begin
           buf:=m[i];     {меняем соседние элементы местами}
           m[i]:=m[i+1];
           m[i+1]:=buf;
           ind:=false;    {как оказалось, массив неотсортирован}
          end;
    UNTIL ind; {выполняем просмотры пока ind=false}

Контрольные вопросы.

1. Опишите идею сортировки массива методом выбора и последовательность действий для его реализации на языке Turbo Pascal.
2. Опишите идею сортировки массива "пузырьковым" методом и последовательность действий для его реализации на языке Turbo Pascal.

Задания для самостоятельного выполнения

1. Организуйте массив, содержащий 20 различных целых чисел. После этого элементы массива упорядочиваются по убыванию и содержимое отсор- тированного массива выводится на экран.
2. Организуйте массив, содержащий 20 различных целых чисел. После этого 10 первых элементов массива упорядочиваются по возрастанию, а 10 последних элементов по убыванию. Содержимое отсортированного таким образом массива выводится на экран.
3. Организуйте массив, содержащий 15 различных целых чисел. После этого отдельно первых 5 элементов, вторых 5 элементов и последних 5 элементов сортируются по возрастанию. Содержимое отсортированного таким образом массива выводится на экран.
4. Создайте массив, содержащий 10 различных целых чисел. Содержимое массива сортируется по возрастанию, и после этого определяются минимальный и максимальный элементы массива.
5. Организуйте массив, содержащий 20 различных символов. Отсортируйте его по возрастанию.
6. Организуйте массив содержащий 20 целых чисел. Отсортируйте отдельно элементы с чётными индексами по возрастанию, и элементы с нечётными индексами по убыванию.
7. Создайте массив содержащий 20 целых чисел. Отсортируйте его по возрастанию. После этого определите и выведите на экран сумму элемен- тов с чётными индексами и сумму элементов с нечётными индексами.
8. Создайте массив, содержащий 15 целых чисел. Отдельно первых 5 элементов массива, вторых 5 элементов и последних 5 элементов отсорти- руйте по убыванию. Определите и выведите на экран сумму каждой пятёрки отсортированного таким образом массива.
9. Создайте массив, содержащий 15 различных символов. Отсортируйте его по убыванию. После этого определите и выведите на экран "наименьший" и "наибольший" символы.
10. Создайте массив, содержащий 10 различных символов. Первую половину массива отсортируйте по возрастанию, а вторую по убыванию. Отсортированный массив выведите на экран.
11. Создайте массив А, содержащий 8 различных символов. Отсортируйте его по возрастанию. Организуйте и выведите на экран целочисленный массив В, заполнив его числами, полученными преобразованием символов массива А в целые числа.
12. Создайте целочисленный массив А, содержащий 10 различных чисел. Отсортируйте первую половину массива А по возрастанию, а вторую по убыванию. Организуйте и выведите на экран символьный массив В, заполнив его символами, полученными преобразованием чисел массива А в символы.
13. Создайте массив, содержащий 20 различных целых чисел. Отсортируйте его по возрастанию. После этого замените все элементы массива на противоположные и выведите содержимое обработанного массива на экран.
14. Создайте массив, содержащий 20 различных целых чисел. Отсортируйте первую половину массива по возрастанию, а вторую по убыванию. Все чётные элементы массива увеличить в три раза, а нечётные в 2 раза. Содержимое обработанного таким образом массива вывести на экран.

НАЗАД                    ДАЛЕЕ