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

Упорядочение в одномерных массивах. Для демонстрации некоторых особенностей вложения циклов и работы с массивами рассмотрим простейшие алгоритмы сортировки. Необходимо, введя значение переменной 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

Лабораторная работа № 13

Многомерные массивы.