Программирование на ЭВМ

            если  X[C]<P

      2.2.1. то   пересчитать А 

      2.2.2. иначе  пересчитать В

    2.2.1 и 2.2.2 очень ответственны. От правильности  пересчета зависит окончание  работы цикла. По условию 2 цикл прекратит свою работу при А=В. Как достичь этого?

    Пусть мы уже сделали пересчет несколько  раз и достигли соотношения А+1=В. Значит при очередном сравнении  будем искать нужный элемент среди двух, расположенных рядом: X[A] и X[B]. Согласно шагу 2.1 вычисленное значение С при этом будет равно А. То есть сравнение 2.2 в этом случае выполнится как X[A]<P. Если условие истинно, то искомый элемент, возможно, есть X[B]. Тогда нужно сделать так, чтобы А стало равно В, то есть

    2.2.1. A:=C+1;

    Если  же X[A]<P – ложно, то искомый элемент, возможно, есть X[A].  Тогда для завершения цикла полагаем

    2.2.2. B:=C;

    Легко  проверить, что такие присваивания не противоречат выбранному нами алгоритму на любом шаге работы цикла.

3. Проверка необходима, так как в цикле мы не делаем проверки на совпадение какого-либо элемента с поисковым, а только определяем, меньше этот элемент или не меньше Р. Теперь надо убедиться в том, что найденный элемент является искомым. Поэтому

          3.IF X[A]=P

            THEN  K:=A

            ELSE K:=0;

    Полностью алгоритм запишется следующим образом.

    Ввод (последовательность Х);

          A:=1; B:=N;

          WHILE A<B DO

              BEGIN

                C:=(A+B) DIV 2;

                IF X[C]<P

                THEN A:=C+1;

                ELSE B:=C;

        END;

    IF X[A]=P

    THEN K:=A;

    ELSE K:=0;

    Вывод (К);

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

    Ввод (матрица А);

    min := A[1,1];

    nom1 := 1;

    nom2 := 1;

    FOR I:=1 TO M DO

      FOR J:=1 TO N DO

          IF A[I,J]<min

          THEN

            BEGIN

                min :=A[I,J];

                nom1:=I;

                nom2:=J;

            END;

    Вывод (min, nom1, nom2);

    2.2. Задача сортировки

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

    2.2.1. Основные понятия

    Под сортировкой понимают процесс перестановки элементов данного множества в определенном порядке. Цель сортировки – облегчить поиск элементов в упорядоченном множестве. В этом смысле элементы сортировки присутствуют почти во всех задачах. Упорядоченные объекты содержатся в телефонных книгах, в оглавлениях, в библиотеках, в словарях, на складах и так далее (почти всюду, где их приходится разыскивать).

    Поэтому методы сортировки очень важны, особенно при обработке данных. При кажущейся простоте задачи именно с сортировкой связаны многие фундаментальные приемы построения алгоритмов, которые и интересуют нас прежде всего. Сортировка является идеальным примером огромного разнообразия алгоритмов, выполняющих одну и ту же задачу. Многие из них являются в некотором смысле оптимальными, большинство имеет какие-то преимущества перед остальными. Поэтому на примере сортировки мы убеждаемся в необходимости сравнительного анализа алгоритмов. С помощью сортировки можно прекрасно иллюстрировать многие принципы программирования и ситуации, возникающие в других задачах. Создается впечатление, что можно построить целый курс программирования, выбирая примеры только из сортировки.

    Очень часто выбор алгоритма зависит  от структуры данных. В случае сортировки эта зависимость настолько сильна, что методы сортировки обычно разделяют на две группы: сортировка массивов и сортировка файлов (последовательных). Эти две группы часто называют внутренней и внешней сортировкой, так как массивы располагаются во «внутренней» (оперативной) памяти ЭВМ, а файлы – во «внешней», более медленной, но более вместительной (ленты, диски). Пример – сортировка пронумерованных карточек. Представление карточек в виде массива соответствует ситуации, когда все они располагаются перед сортирующим (на столе) и каждая карточка видна и доступна. Представление карточек в виде файла предполагает, что они сложены стопкой и видна только верхняя карточка из стопки.

    Пусть даны элементы а₁, а₂, …а_N. Сортировка означает перестановку этих элементов в таком порядке а_к1, а_к2, …а_kN, что при заданной функции упорядочения f справедливо отношение

      f (a_k1) ≤ f (a_k2) ≤ … ≤ f (a_kN).

    Обычно  функция упорядочения не вычисляется по какому-то специальному правилу, а содержится в каждом элементе в виде явной компоненты (поля). Ее значение называется ключом элемента (key). Прочие компоненты – это все существенные данные об элементе. С точки зрения же алгоритмов сортировки ключ – единственная существенная компонента, и нет необходимости определять остальные.

    Метод сортировки называется устойчивым, если относительный порядок элементов  с одинаковыми ключами не меняется при сортировке. Устойчивость сортировки часто бывает желательна, если элементы упорядочены по каким-то вторичным ключам, то есть по другим свойствам.

    2.2.2. Особенности сортировки  массивов. Простые

                      методы сортировки массивов

    Основное  требование к методам сортировки массивов – экономное использование памяти. Это означает, что упорядочение нужно проводить на том же месте, то есть методы, которые пересылают элементы из массива А в массив В, нам не интересны. Таким образом, выбирая метод сортировки по критерию экономии памяти, классификацию алгоритмов можно проводить по их эффективности, то есть быстродействию. Удобной оценкой такой эффективности является количество С необходимых сравнений ключей и М - пересылок элементов. С и М являются некоторыми функциями от числа элементов n.

    Хотя  хорошие алгоритмы сортировки требуют порядка n * log ₂ n сравнений, обсудим вначале несколько несложных и очевидных методов сортировки, называемых простыми методами, которые требуют С ~ n².

    Причины такого рассмотрения состоят в следующем:                              

1. на простых методах разъяснять свойства большинства принципов сортировки;
2. программы, основанные на этих методах, легки для понимания и коротки (программа тоже занимает место в памяти ЭВМ!);
3. при достаточно малых значениях n простые методы работают быстрее.

    В зависимости от лежащего в их основе приема простые методы сортировки на месте можно разбить на 3 группы: сортировка выбором,  сортировка обменом, сортировка включениями.

    Рассмотрим  эти методы для простейшего случая упорядочения числовых массивов (последовательностей) по возрастанию (убыванию) значений элементов. В этом случае ключ f (a_i) = a_i (табл.2.1 – табл.2.3).

Таблица 2.1 – Числовой массив. Все элементы различны

Номер элемента	1	2	3	4	5
Исходная  последовательность	7	12	1	49	3
Упорядоченная по возрастанию последовательность	1	3	7	12	49

Таблица 2.2 – Числовой массив. Есть повторяющиеся  элементы

Номер элемента	1	2	3	4	5
Исходная  последовательность	4	21	171	22	172
Упорядоченная по возрастанию последовательность	21	22	4	171	172

Таблица 2.3 – Массив строк. Упорядочение по алфавиту

Номер элемента	1	2	3	4	5
Исходная  последовательность	МИР	СОН	ТУР	КОЛ	ЕЛЬ
Упорядоченная по возрастанию последовательность	ЕЛЬ	КОЛ	МИР	СОН	ТУР

 

    Сортировку  можно рассматривать и как  самостоятельную задачу (например, получение упорядоченного по алфавиту списка сотрудников какого-либо учреждения), и как вспомогательную для облегчения последующего поиска.

    Следует отметить, что все методы сортировки рассчитаны на обработку одномерных массивов. При необходимости двумерный  массив всегда можно представить как одномерный путем пересчета индексов.

    Будем для определенности упорядочивать  массив А₁, А₂, … , А_N по возрастанию. Переход к алгоритмам упорядочения по убыванию не составляет труда. Рассмотрим три алгоритма, представляющие каждую из перечисленных групп методов сортировки. 

                                          Простой выбор

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

    Идея  метода такова. Найдем в последовательности элемент с наименьшим значением и поменяем его местами с первым элементом. Затем проделаем те же действия с оставшимися N-1 элементами, затем с N-2 и так далее до тех пор, пока не останется один элемент – последний. Он будет наибольшим.

    Проиллюстрируем процесс (табл.2.4).

Таблица 2.4 – Пример сортировки простым выбором

Номер элемента	1	2	3	4	5	6	7	8
Исходная последовательность	72	14	6	98	17	51	25	33
После выбора среди 8 элементов	6	14	72	98	17	51	25	33
7 элементов	6	14	72	98	17	51	25	33
6 элементов	6	14	17	98	72	51	25	33
5 элементов	6	14	17	25	72	51	98	33
4 элементов	6	14	17	25	33	51	98	72
3 элементов	6	14	17	25	33	51	98	72
2 элементов	6	14	17	25	33	51	72	98
Упорядоченная последовательность	6	14	17	25	33	51	72	98