Array M. УЭИТ - Язык Си - руководство для начинающих

Проверьте вашу программу и посмотрите, работает ли она так, как должна. Самое простое - предположить, что limitравен 1 и пройти по программе шаг за шагом.

Рассмотрим еще раз функцию main( ):

main( )

{

int numbers[MAXSIZE]; /* массив для ввода */

int size; /* количество введенных элементов */

size = getarray(numbers, MAXSIZE); /* помещает ввод в массив */

sort(numbers, size); /* сортировка массива */

printf(numbers, size); /* печать отсортированного массива */

}

Мы видим, что функция sort()имеет на входе массив целых чисел, предназначенных для сортировки, и счетчик количества элементов, подлежащих сортировке. На выходе получается массив, содержащий отсортированные числа. Мы все еще не решили, как выполнять сортировку, поэтому мы должны дополнительно уточнить это описание.

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

Рассмотрим теперь метод, который будем использовать для сортировки. В настоящее время разработано много алгоритмов сортировки; возьмем один из самых простых.

Вот наш план на псевдокоде:

от n = первому элементу до n = ближайшему - к- последнему элементу находим самое большое из оставшихся чисел и помещаем его в n-ю позицию.

Он выполняется примерно так. Сначала пусть n = 1. Мы просматриваем весь массив, находим самое большое число и помещаем его в первый элемент. Затем n = 2, и мы опять просматриваем весь массив, кроме первого элемента, находим самое большое из оставшихся чисел и помещаем его во второй элемент. Продолжаем этот процесс до тех пор, пока не достигнем ближайшего - к - последнему элементу. Теперь осталось только два элемента. Мы сравниваем эти числа и помещаем большее в элемент, ближайший - к - последнему. Оставшееся самое меньшее из всех чисел помещаем в последний элемент.

Это выглядит очень похоже на задачу с циклом for, но мы все же должны описать процесс "найти и поместить" более детально. Как сделать так, чтобы мы находили каждый раз самое большое из оставшихся чисел? Вот один способ. Сравните первый и второй элементы оставшегося массива. Если второй больше, поменяйте их местами. Теперь сравните первый элемент с третьим. Если третий больше, поменяйте местами эти два. Каждый раз больший элемент перемещается вверх. Продолжаем таким образом, пока не сравним первый элемент с последним. Если мы дошли до конца, самое большое число теперь будет в первом элементе оставшегося массива. По существу мы имеем отсортированный массив для первого элемента, но остаток массива находится в беспорядке. На псевдокоде это можно выразить так:

для n = от второго до последнего элемента сравниваем n-й элемент с первым; если n-й больше, меняем их местами.

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

/* сортировка массива целых чисел в порядке убывания */

sortarray(array, limit)

int array[ ], limit;

{

int top, search;

for(top = 0; top < limit - 1; top++)

for(search = top + 1; search < limit; search++)

if(array [search] > array[top]

interchange(&array[search], &array[top] );

}

Мы помним, что первый элемент имеет индекс 0. Кроме того, еще в гл. 9 была создана функция обмена, поэтому мы использовали ее здесь. Так как функция interchange"работает" с двумя элементами массива, а не со всем массивом, мы должны использовать адреса только двух интересующих нас элементов. (В то время как имя array является указателем на весь массив, нам нужно применить операцию &, чтобы указывать на отдельные элементы.)

Мы использовали top в качестве индекса для элемента массива, который следует заполнить, так как он является вершиной не отсортированной части массива. Индекс searchперемещает по массиву в порядке убывания текущий элемент. Большинство текстов использует обозначения i и j для этих индексов, однако это осложняет ситуацию, если нужно посмотреть, что происходит.