Теоретические сведения. Упорядочение в одномерных массивах

Упорядочение в одномерных массивах. Для демонстрации некоторых особенностей вложения циклов и работы с массивами рассмотрим простейшие алгоритмы сортировки. Необходимо, введя значение переменной 1<n<=100 и значения n первых элементов массива а[0],а[1],...,а[n-1], упорядочить эти первые элементы массива по возрастанию их значений. Текст первого варианта программы:

/* Упорядочение элементов массива */

#include <stdio.h>

main( )

{

int n,i,j;

double a[100],b;

while(1)

{

printf("\n Введите количество элементов n=") ;

scanf("%d",&n);

if (n > 1 && n <= 100) break;

printf ("Ошибка! Необходимо 1<n<=100! ") ;

}

printf("\n Введите значения элементов массива:\n");

for(j=0; j<n;j++)

{

printf("a[%d]=”, j+1) ;

scanf(“%lf”,&a[j]);

}

for(i=0; i<n-1; i++)

for(j=i+l; j<n; j++)

if(a[i]>a[j])

{

b=a[i]; a[i]=a[j];. a[j]=b;

}

printf("\n Упорядоченный массив: \n") ;

for(j=0; j<n; j++)

printf("a[%d]=%f\n", j+1,a[j]);

}

При заполнении массива и при печати результатов его упорядочения индексация элементов выполнена от 1 до n, как это обычно принято в математике. В программе на Си это соответствует изменению индекса от 0 до (n-1).

В. программе реализован алгоритм прямого упорядочения - каждый элемент a[i], начиная с а[0] и кончая а[n-2], сравнивается со всеми последующими, и на место a[i] выбирается минимальный. Таким образом, а[0] принимает минимальное значение, а[1] - минимальное из оставшихся и т.д. Недостаток этого алгоритма состоит в том, что в нем фиксированное число сравнений, не зависимое от исходного расположения значений элементов. Даже для уже упорядоченного массива придется выполнить то же самое количество итераций (n-1)*n/2, так как условия окончания циклов не связаны со свойствами, т.е. с размещением элементов массива.

Алгоритм попарного сравнения соседних элементов позволяет в ряде случаев уменьшить количество итераций при упорядочении. В цикле от 0 до n-2 каждый элемент a[i] массива сравнивается с последующим a[i+l] (0<i<n-l). Если a[i]>a[i+l], то значения этих элементов меняются местами. Упорядочение заканчивается, если оказалось, что a[i] не больше a[i+l] для всех i. Пусть k - количество перестановок при очередном просмотре. Тогда упорядочение можно осуществить с помощью такой последовательности операторов:

do {

for (i=0, k=0; i<n-l; i++)

if ( a[i] > a[i+l] )

{

b=a[i]; a[i]=a[i+1]; a[i+1]=b;

k=k+l;

}

n--;

}

while ( k > 0 ) ;

Здесь количество повторений внешнего цикла зависит от исходного расположения значений элементов массива. После первого завершения внутреннего цикла элемент а[n-1] становится максимальным. После второго окончания внутреннего цикла на место а[n-2] выбирается максимальный из оставшихся элементов и т.д. Таким образом, после j-гo выполнения внутреннего цикла элементы a[n-j],...,a[n-l] уже упорядочены, и следующий внутренний цикл достаточно выполнить только для 0<i<(n-j-l). Именно поэтому после каждого окончания внутреннего цикла значение n уменьшается на 1.

В случае упорядоченности исходного массива внешний цикл повторяется только один раз, при этом выполняется (n-1) сравнений, k остается равным 0. Для случая, когда исходный массив упорядочен по убыванию, количество итераций внешнего цикла равно (n-1), а внутренний цикл последовательно выполняется (n-1)*n/2 раз.

Задание. Написать программу на СИ для задачи, указанной в таблице 24. Имя и размер массива выбрать самостоятельно.

Таблица 24

Вар.	Условие задачи
	Найти сумму двух наибольших четных чисел массива
	Найти произведение двух наибольших нечетных чисел массива
	Найти произведение двух наибольших четных чисел массива
	Найти сумму двух наибольших нечетных чисел массива
	Найти сумму трех наибольших четных чисел массива
	Найти сумму двух наименьших четных чисел массива
	Найти сумму двух наименьших нечетных чисел массива
	Найти сумму трех наименьших нечетных чисел массива
	Найти сумму двух наименьших положительных чисел массива
	Найти сумму двух наибольших отрицательных чисел массива
	Найти сумму трех наименьших положительных чисел массива
	Найти произведение двух наименьших положительных чисел массива
	Найти произведение двух наибольших отрицательных чисел массива
	Найти произведение трех наибольших кратных 5 чисел массива
	Найти произведение трех наименьших не кратных 4 чисел массива
	Найти произведение трех наибольших положительных кратных 3 чисел массива
	Найти произведение трех наименьших отрицательных нечетных чисел массива
	Найти сумму трех наименьших положительных четных чисел массива
	Найти сумму трех наибольших нечетных, лежащих в интервале [1,30], чисел массива
	Найти произведение четырех наименьших, лежащих в интервале [-20,20], чисел массива
	Найти сумму четырех наименьших кратных 5 и не больших 50 чисел массива
	Найти произведение двух наибольших и двух наименьших положительных четных чисел массива
	Найти сумму двух наибольших и двух наименьших отрицательных четных чисел массива
	Найти произведение двух наибольших и двух наименьших отрицательных нечетных чисел массива
	Найти сумму двух наибольших и двух наименьших нечетных чисел массива, лежащих в интервале [1,25]
	Найти произведение двух наибольших и двух наименьших положительных кратных 3 чисел массива
	Найти сумму двух наибольших и двух наименьших кратных 3 и не меньших 10 чисел массива
	Найти произведение двух наибольших и двух наименьших кратных 5 и не больших 20 чисел массива
	Найти сумму трех наибольших, не кратных 5 положительных чисел массива
	Найти произведение трех наименьших отрицательных кратных 3 чисел массива