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