Размещено на http://allbest.ru/

Размещено на http://allbest.ru/

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ФИЛИАЛ ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

МОСКОВСКОГО ГОСУДАРСТВЕННОГО ИНДУСТРИАЛЬНОГО УНИВЕРСИТЕТА В Г. ВЯЗЬМЕ СМОЛЕНСКОЙ ОБЛАСТИ

КУРСОВАЯ РАБОТА

По дисциплине: Структуры и алгоритмы компьютерной обработки данных

Тема: Сравнительный анализ метода Шелла и метода Бэтчера по критерию эффективности применения к различным исходным данным

2009

СОДЕРЖАНИЕ

• ЗАДАНИЕ
• ВВЕДЕНИЕ
• ГЛАВА 1. АЛГОРИТМЫ СОРТИРОВКИ И ПОИСКА ИНФОРМАЦИИ
• 1.1 Классификация алгоритмов сортировки и поиска информации
• 1.2 Метод Шелла
• 1.3 Параллельная сортировка Бэтчера
• ГЛАВА 2. ИНСТРУМЕНТАРИЙ ИССЛЕДОВАНИЯ АЛГОРИТМОВ СОРТИРОВКИ
• 2.1 Корреляционно - регрессионный анализ как основной инструмент исследования алгоритмов
• 2.2 Табличный процессор MS Excel' 2003 как основной инструмент автоматизации процесса проведения регрессионного анализа данных
• ГЛАВА 3. СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ШЕЛЛА И БЭТЧЕРА ПО КРИТЕРИЮ ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ К РАЗЛИЧНЫМ ИСХОДНЫМ ДАННЫМ
• 3.1 Исследование метода Шелла посредством построения линейного уравнения регрессии
• 3.2 Исследование сортировки методом Бетчера посредством построения линейного уравнения регрессии
• 3.3 Сравнительный анализ двух алгоритмов
• ЗАКЛЮЧЕНИЕ
• Библиография
• ПРИЛОЖЕНИЯ
• ЗАДАНИЕ

Изучить способы сортировки и поиска информации с применением методов сортировки Шелла и Бэтчера.

Разработать программы на языке Turbo Pascal 7.0. для реализации изученных методов. Построить регрессионные модели для анализа эффективности методов. Выполнить сравнительный анализ алгоритмов Шелла и Бэтчера на основе полученных регрессионных моделей.

ВВЕДЕНИЕ

В последние годы программирование для вычислительных машин выделилось в некоторую дисциплину, владение которой стало основным и ключевым моментом, определяющим успех многих инженерных проектов, а сама она превратилась в объект научного исследования. Из ремесла программирование перешло в разряд академических наук. Первый крупный вклад в ее становление сделали Э. Дейкстра и Ч.Хоар. Основное внимание в их работах уделяется построению и анализу программ, а более точно - структуре алгоритмов, представляемых текстом программы. Программы представляют собой конкретные, основанные на некотором реальном представлении и строении данных воплощения абстрактных алгоритмов.

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

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

При сравнении методов сортировки, с точки зрения их эффективности, выполняют многократное тестирование разработанной программы на данных различной длины со всевозможными перестановками. Для каждого входного вектора значений размерности n определяется число сравнений sr и число обменов m, выполняемых с его координатами в процессе работы алгоритма. Полученные статистические данные отражают средние значения параметров, на основании которых можно сделать вывод об эффективности того или иного метода сортировки или поиска.

При сравнении способов организации некоторой логической структуры данных, например, списка или дерева, в процессе анализа учитывают, насколько быстро и просто выполняется её формирование посредством некоторой физической реализации, сколько времени и вычислительных ресурсов требуется для её модификации (вставки, удаления, перестроения), как быстро осуществляется поиск необходимой информации в такой структуре.

ГЛАВА 1. АЛГОРИТМЫ СОРТИРОВКИ И ПОИСКА ИНФОРМАЦИИ

1.1 Классификация алгоритмов сортировки и поиска информации

Хотя в словарях слово «сортировка» определяется как процесс разделение объектов по виду или сорту, программисты традиционно используют его в гораздо более узком смысле, обозначая им такую перестановку предметов, при которой они располагаются в порядке возрастания или убывания.

Под сортировкой массивов понимают процесс перестановки элементов массива в определенном порядке.

Цель сортировки - облегчить последующий поиск элементов в отсортированном массиве.

Методы сортировки важны при обработке данных, с ними связаны многие фундаментальные приемы построения алгоритмов.

Сортировки могут быть выполнены с использованием различных алгоритмов: как простых, так и усложненных (но более эффективных). Основное требование к методам сортировки: экономное использование памяти и быстродействие. Первое требование может быть выполнено, если переупорядочение элементов будет выполняться на том же месте. Хорошие алгоритмы сортировки требуют порядка n *lognсравнений.

Простые методы сортировки можно разбить на три основных класса в зависимости от лежащего в их основе приема:

1.сортировка выбором;

2.сортировка обменом;

3.сортировка включением.

Простые методы сортировки требуют порядка n*n сравнений элементов (ключей).

Простые методы сортировки.

Сортировка посредством простого выбора.

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

1.найти элемент с наибольшим значением;

2.поменять значениями найденный элемент и последний;

3.уменьшить на единицу количество просматриваемых элементов;

4.если <количество элементов для следующего просмотра больше единицы> то <повторить пункты, начиная с 1-го>.

Алгоритм:

Цикл по количеству просматриваемых элементов {i:=n,n-1,…,2}

Найти номер k максимального элемента среди a[1],a[2],…,a[i]

Поменять местами значения элементов a[k] и a[i]

Сортировка обменом (методом пузырька).

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

Алгоритм:

Цикл по количеству просмотров

Цикл по количеству сравниваемых значений при очередном просмотре

Если < упорядоченность в паре нарушена > то <выполнить обмен значениями >.

Количество просмотров (повторений) во внешнем цикле равно n-1.Оно может быть уменьшено, если i- й шаг показал, что массив уже упорядочен (во внутреннем цикле не было перестановок).

Сортировка включением.

Сортировка основана на следующем: предполагается, что элементы a[1],a[2], …,a[i-1] упорядочены, a[i] вставляется на соответствующее место, не нарушая свойства упорядоченности. Для этого a[i] сравнивается по очереди с a[i-1], a[i-2], …до тех пор, пока не будет обнаружено, что элемент a[i] следует вставить между a[j], a[j-1] (j - номер элемента в a[1…i-1], за которым следует вставить a[i]).Тогда элементы a[j+1],…, a[i-1] сдвигаются на одну позицию вправо, а новая запись помещается в позицию j+1.Удобно совмещать сравнение и перемещение.

Можно уменьшить количество сравнений при организации внутреннего цикла. Для этого используется метод барьера: вставляемое значение помещается в начало массива на дополнительное 0-е место

(a[0]:= a[i]), диапазон индексов расширяется.

1.2 Метод Шелла

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

Такой метод предложен в 1959 году Дональдом Л. Шеллом [Donald L. Shell, CACM 2,7(Java, 1959), 30-32] и известен во всем мире под именем своего автора. Пусть имеется массив записей R1, R2, …., R16. Делим 16 записей на 8 групп по две записи в каждой группе: (R1, R9), (R2, R10), ….,(R8, R16). Сортируем выбранные пары записей в порядке, например, возрастания, т.е. если в паре (R2, R10): R2 > R10, то R2 и R10 меняем местами: R1, R10, R3, R4, R5, R6, R7, R8, R9, R2, R11, R12, R13, R14, R15, R16. То же самое выполняется и для других пар записей. Это сортировка со смещением 8. Этот процесс называется первым проходом. Разделим теперь записи на четыре группы по четыре записи в каждой: (R1, R5, R9, R13), …, (R4, R8, R12, R16). Затем опять рассортируем каждую группу в отдельности. Это сортировка со смещением 4. На третьем проходе отсортируем 2 группы по 8 записей: (R1, R3, R5, R7, R9, R11, R13, R15) и (R2, R4, R6, R8, R10, R12, R14, R16). Это сортировка со смещением 2. Процесс завершается четвёртым проходом, во время которого сортируются все 16 записей. Это сортировка со смещением 1. В каждой из промежуточных стадий сортировки участвуют либо сравнительно короткие массивы, либо уже сравнительно хорошо упорядоченные массивы, поэтому на каждом этапе можно пользоваться методом простых вставок. Метод сортировки Шелла ещё называется с «убывающим смещением», поскольку каждый проход характеризуется смещением h, таким, что сортируются записи, каждая из которых отстоит от предыдущей на h позиций. Последовательность значений смещений 8, 4, 2, 1 не следует считать неизменной, можно пользоваться любой последовательностью смещений, но последнее смещение должно быть равно 1.

Метод сортировки Шелла также известен под именем Shellsort и метода сортировки с «убывающим смещением», поскольку каждый проход характеризуется смещением h, таким, что сортируются записи, каждая из которых отстоит от предыдущей на h позиции. Последовательность значений смещений 8, 4, 2, 1 не следует считать незыблемой; можно пользоваться любой последовательностью h_t-1, h_t-2, …, h₀. но последнее смещение h₀ должно быть равно 1. Например, в таблице 2 продемонстрированная сортировка тех же данных со смещениями 7, 5, 3, 1. Как будет показано ниже, выбор значений смещений на последовательных проходах имеет весьма существенное значение для скорости сортировки.

Сортировка Шелла.

Алгоритм D (сортировка Шелла). Запись R₁,…,R_N перекомпоновываются в том же адресном пространстве памяти. После завершения сортировки их ключи будут упорядочены: K₁ …K_N. Для управления процессом сортировки используется вспомогательная последовательность смещений h_t-1, h_t-2, …, h₀ , где h₀ =1; правильно выбрав эти значения в последовательности , можно значительно сократить время сортировки. При t=1 этот алгоритм сводится к алгоритму S.

D1:[Цикл по s.] Выполнить шаг D2 при s =t -1, t-2, …,0, после чего завершить процедуру.

D2:[Цикл по j.] Присвоить h h_s и выполнить шаг от D3 до D6 при h < i < N. (Для сортировки элементов, отстоящих один от другого на h позиций, воспользуемся методом простых вставок и в результате получим K_i K_i+h для 1 i N-h.Шаги от D3 до D6, по существу, такие же , как соответственно от S2 до S5 в алгоритме S.)

D3. [Установка I, K, R.] Присвоить i j - h, K K_i, R R_j.

D4. [Сравнение K : K_i.] Если K K_i , то перейти к шагу D6.

D5. [Перемещение R_i, уменьшение i.] Присвоить R_i+h R_i, затем i i - h. Если I>0, то возвратиться к шагу D4.

D6. [Перемещение R на место R_i+h .] Присвоить R_i+h R_i.

Анализ Метода Шелла.

Для рационального выбора последовательности значений смещений сортировки h_t-1,…,h₀ для алгоритма D нужно проанализировать время выполнения как функцию от этих смещений. Такой анализ приводит к постановки очень красивых, но еще не до конца решенных математических задач; никому до сих пор не удалось найти наилучшею возможную последовательность смещений для больших N. Тем не менее известно довольно много интересных свойств сортировки методом Шелла с убывающим смещением.

1.3 Параллельная сортировка Бэтчера

Чтобы получить алгоритм обменной сортировки, время работы которого имеет порядок, меньший N² , необходимо подобрать для сравнений пары несоседних ключей (K_i , K_j); иначе придется выполнять столько операций обмена записей, сколько инверсий имеется в исходной перестановке.

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

Алгоритм М (Обменная сортировка со слиянием). Записи R₁ , …,R_N перекомпоновываются в пределах того же пространства в памяти. После завершения сортировки их ключи будут упорядочены: K₁ <=…<=K_N. Предполагается, что N >=2 (рис. 1).

Рис. 1 Схема сортировки метода Бэтчера

М1. [Начальная установка p] Установить p < 2^{t -1}, где t=[lg N] - наименьшее целое число, такое, что 2^t N. (Шаги M2-M5 будут выполняться с p = 2 ^t-1,2 ^t-2,…,1)

M2. [Начальная установка q, p, d.] Установить q2^t-1, r0, dp.

M3. [Цикл по i] Для всех I, таких, что 0I<N-d и iЛp=r, выполнить шаг М4. Затем перейти к шагу М5. (Здесь через iЛp обозначена операция «поразрядное логическое И» над представлениями целых чисел i и p; все биты результата равны 0, кроме тех битов, для которых в соответствующих разрядах i и p находятся 1. Так, 13Л21=(1101)₂Л(10101)₂=(00101)₂=5. К этому моменту d -нечетное кратное p (т.е. частное от деления d на p нечетно), а p - степень двойки, так что iЛ p (I+d) Л p. Отсюда следует, что шаг М4 можно выполнять при всех нужных значениях i в любом порядке или даже одновременно.)

M4. [сравнение/обмен R_i+1: R_i+d+1.] Если _Ki+1 >Ki_+d+1, поменять местами записи R_i+1 R_i+d+1.

M5. [Цикл по q] Если qp, установить dq-p, qq/2, rp и возвратиться к шагу М3.

M6. [Цикл по p] (К этому моменту перестановка К₁К₂…К_n будет p-упорядочена.) Установить р[p/2]. Если р0, возвратиться к шагу М2.

В таблице этот метод проиллюстрирован при N=16. Обратим внимание на то, что, по существу, алгоритм сортирует N элементов путем независимой сортировки подмассивов R₁ R₃ R₅ ,… и R₂ R₄ R₆,…, после чего выполняются шаги М2-М5 при р=1 для слияния двух рассортированных последовательностей. Реализация данного алгоритма на языке программирования Turbo Pascal 7.0 приведена в приложении 2.

Анализ сортировки Бэтчера.

Чтобы доказать, что магическая последовательность сравнений и/или обменов, описанная в алгоритме М, действительно позволяет рассортировать любую последовательность R₁ R₃ … R_n, необходимо показать только, что в результате выполнения шагов М2-М5 при р=1 будет слита любая 2-упорядоченная последовательность R₁ R₂ … R_n; каждая 2-упорядоченная перестановка множества{1,2….,N} соответствует на решетке единственному пути из вершины (0,0) к ([N/2],[N/2]). На рисунке 1, показан пример при N=16, соответствующий перестановке 1 3 2 4 10 5 11 6 13 7 14 8 15 9 16 12. При р=1, q=2^t-1, r=0, d=1 на шаге М3 выполняется сравнение (и, возможно, обмен) записей R₁ : R₂ , R₃ : R₄ и т.д. Этой операции соответствует простое преобразование пути на решетке.

Таблица 1 Обменная сортировка со слиянием (Метод Бэтчера)

P q rd
	503	087	512	061	908	170	897	275	653	426	154	509	612	677	765
8 8 08
	503	087	154	061	612	170	765	275	653	426	512	509	908	677	897
4 8 04
	503	087	154	061	612	170	765	275	653	426	512	509	908	677	897
4 4 44
	503	087	154	061	612	170	512	275	653	426	795	509	908	677	897
2 8 02
	154	061	503	087	512	170	612	275	653	426	765	509	897	677	908
2 4 26
	154	061	503	087	512	170	612	275	653	426	765	509	897	677	908
2 2 22
	154	061	503	087	512	170	612	275	653	426	765	509	897	677	908
1 8 01
	061	154	087	503	170	512	275	612	426	653	509	765	677	897	703
1 4 17
	061	154	087	503	170	512	275	612	426	653	509	765	677	897	703
1 2 13
	061	154	087	275	170	426	503	509	512	653	612	703	677	897	765
1 1 11
	061	087	154	170	275	426	503	509	512	612	653	677	703	765	897

На следующей итерации М3 имеем p=r=1 и d=2^t-1-1,2^t-2-1,…,1. В результате произойдет сравнение и/или обмен записей R₂ : R_2+d, R₄ : R_4+d и т.д. Опять же, имеется простая геометрическая интерпретация: путь «перегибается» относительно прямой, расположенной на единиц ниже диагонали. В конце концов, получаем путь, который соответствует полностью рассортированной перестановке. На этом «геометрическое доказательство» справедливости алгоритма Бэтчера завершается (данный алгоритм можно было бы назвать сортировкой посредством перегибов).

Однако, она обладает одним важным компенсирующим качеством: все сравнения и/или обмены, определяемые данной итерацией шага М3, можно выполнять одновременно на компьютерах или в сетях, которые реализуют параллельные вычисления. С такими параллельными операциями сортировка осуществляется за ? [lgN] ([lgN]+1) шагов, и это один из самых быстрых общих методов среди всех известных. Например, 1024 элемента можно рассортировать методом Бэтчера всего за 55 параллельных шагов. Его ближайшим соперником является метод Пратта, который затрачивает 40 или 73 шага в зависимости от того, как считать: если допускать перекрытие сравнений до тех пор, пока не требуется выполнять перекрывающиеся обмены, то для сортировки 1024 элементов методом Пратта требуется всего 40 циклов сравнения и/или обмена.

(а) (б) (с) (d) (e)

Рис. 2 Геометрическая интерпретация метода Бэтчера

алгоритм сортировка линейный регрессия

ГЛАВА 2. ИНСТРУМЕНТАРИЙ ИССЛЕДОВАНИЯ АЛГОРИТМОВ СОРТИРОВКИ

2.1 Корреляционно - регрессионный анализ как основной инструмент исследования алгоритмов

Корреляционно-регрессионный анализ проверяет наличие и значимость линейной зависимости между переменными без указания зависимой и объясняемых переменных.

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

Корреляционно-регрессионный анализ связей между переменными показывает, как один набор переменных (X) может влиять на другой набор (Y). Таким образом, регрессионные вычисления и подбор хороших уравнений - это ценный, универсальный исследовательский инструмент в самых разнообразных отраслях деловой и научной деятельности (маркетинг, торговля, медицина, социология, исследования алгоритмов и т.д.).

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

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

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

Второй этап - расчет параметров и построение регрессионных моделей. Здесь стремятся отыскать наиболее точную меру выявленной связи, для того чтобы можно было прогнозировать, предсказывать значения зависимой величины Y, если будут известны значения независимых величин Х1, Х2, …, Хn. Эту меру обобщенно выражают математической моделью линейной множественной регрессионной зависимости: у = а0 + b1x1 + b2x2 + … + bnxn.

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

На третьем этапе выясняют статистическую значимость, т. е. пригодность постулируемой модели для использования ее в целях предсказания значений отклика. На этом этапе исключительно важную роль играют коэффициент детерминации и F - критерий значимости регрессии. R Squared (R2) - коэффициент детерминации - это квадрат множественного коэффициента корреляции между наблюдаемым значением Y и его теоретическим значением, вычисленным на основе модели с определенным набором факторов. Коэффициент детерминации измеряет действительность модели. Он может принимать значения от 0 до 1. Эта величина особенно полезна для сравнения ряда различных моделей и выбора наилучшей модели.

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

Для определённости эндогенные переменные в этих моделях будем называть результативными признаками, а экзогенные переменные будем называть факторными признаками. Построенная регрессионная эконометрическая модель позволит: во-первых, определить математическую зависимость между переменными, во-вторых, измерить тесноту связи между ними, в-третьих, проанализировать влияние отдельных факторных признаков на результат.

Постановка задачи регрессионного анализа:

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

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

3. После определения показателя результатов исследования и факторов собираются статистические данные по ним. Они могут быть получены путем:

а) временной (фиксируется объект наблюдений, и собираются данные за ряд периодов времени).

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

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

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

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

y = a0 + a1x -- линейная,

y = a0 + a1 / x -- гиперболическая,

y = a0 + a1x + a2x2 -- квадратичная,

y = a0 + a1x + a2x2 + … + anx2 -- полином,

y = a0xa1 -- степенная,

y = a0a1x -- показательная.

Линейная функция (y = a0 + a1x) наиболее широко применяется в описании различных процессов, хотя является лишь приближением к реальным взаимосвязям, которые в силу своей сложности и многофакторности бывают нелинейными. В зависимости от знака коэффициента a1, который определяется в результате расчетов, влияние фактора может быть прямым (при a1> 0) и обратным (при a1 < 0).

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

2.2 Табличный процессор MS Excel' 2003 как основной инструмент автоматизации процесса проведения регрессионного анализа данных

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

Статические функции, вызываются через окно Мастер функций. Функция КОРРЕЛ (расчет корреляции между двумя множествами данных) запрашивает два исходных множества (массива) данных и выдает коэффициент корреляции в ту клетку, куда был установлен курсор перед обращением к функции.

На окно мастера функций наложено окно самой функции КОРРЕЛ, хотя на самом деле одновременный обзор этих двух окон исключен.

Множественный корреляционно-регрессионный анализ в основном ориентирован на средства дополнительного пакета Анализ данных. Активизация команды Сервис/Анализ данных открывает окно Инструменты анализа, предоставляющие 19 статических инструментальных средств. Среди них - Корреляция и Регрессия, непосредственно и эффективно поддерживающие простой и множественный корреляционно-регрессионный анализ.

При многофакторной модели табличный процессор облегчает работу, связанную с расчётом коэффициентов регрессии, частных коэффициентов эластичности, множественной корреляции и коэффициентов детерминации (при этом можно использовать такие функции, как: МОБР, МОПРЕД, МУМНОЖ, КОРЕНЬ и т.д.).

ГЛАВА 3. СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ШЕЛЛА И БЭТЧЕРА ПО КРИТЕРИЮ ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ К РАЗЛИЧНЫМ ИСХОДНЫМ ДАННЫМ

3.1 Исследование метода Шелла посредством построения линейного уравнения регрессии

Сначала были собраны исходные данные. Созданные на Turbo Pascal 7.0 программы запускались с исходными массивами от одного до 200 элементов, подсчитывалось число сравнений и перестановок для каждой группы. Затем для каждой группы элементов формировались средние значения перестановок, сравнений, неупорядоченных элементов и размерностей исходных массивов.

Таблица 2. Исходные данные для искомой эконометрической модели

группа	х1	х2	У
от 1 до 20	66	17,75	12,5
от 21 до 50	365,25	54,5	31
от 51 до 100	2011	228,5	71
от 101 до 150	5888,75	595,75	124,5
от 151 до 200	11740,5	919,75	176,5
итого:	20071,5	1816,25	415,5
сред.знач.	4014,3	363,25	83,1

Теперь нужно определить характер связи между основным показателем эффективности алгоритма сортировки y= Pr+Sr и характеристиками исходных данных. Для этого вычисляем парные коэффициенты корреляции r_yx1 , ryx2 , rx1x2. В нашем случае эти коэффициенты равны:

Rx1y=0,9748445

Rx2y=0,9930315

Rx1x2=0,9898675

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

Уравнение регрессии.

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

Для нахождения коэффициентов а₀, а₁, а₂ применим метод наименьших квадратов.

Выполнение расчётов, необходимые для формирования системы нормальных уравнений были произведены в MS Excel.

На основании полученных коэффициентов составляем систему нормальных уравнений в матричном виде:

Таблица 3 Система нормальных уравнений в матричном виде

а0	а1	а2	У
5	20071,5	1816,25	415,5
20071,5	176698601,4	14787139	2960276,38
1816,25	14787138,81	1256355,7	254641,625

Вычислим главный определитель системы, если он отличен от нуля, то система имеет решение и его можно получить методом Крамера.

С помощью функции МОПРЕД() получим значение главного определителя системы:

Д=5,78143E+12

Главный определитель 0. Теперь вычисляем другие определители, требуемые для нахождения переменных а₀, а₁, а₂. Считаем определитель ₁, полученный из главного заменой первого столбца а₀ на вектор у:

Таблица 4 Матрица для вычисления определителя ₁

У	а1	а2
415,5	20071,5	1816,25
2960276,38	176698601,4	14787139
254641,625	14787138,81	1256355,7

Д1=9,76953E+13

Получаем значение коэффициента а₀ делением 1 на :

16,89813

Считаем с помощью функции МОПРЕД() определитель ₂, полученный из главного заменой второго столбца а₁ на вектор у:

Таблица 5 Матрица для вычисления определителя ₂

a0	y	а2
5	415,5	1816,25
20071,5	2960276,375	14787139
1816,25	254641,625	1256355,7

Д2=32130895219

Получаем значение коэффициента а1 делением 2 на :

-0,0055576

Считаем с помощью функции МОПРЕД() определитель ₃, полученный из главного заменой третьего столбца а₂ на вектор у:

Таблица 6 Матрица для вычисления определителя ₃

а0	а1	У
5	20071,5	415,5
20071,5	176698601,4	2960276,4
1816,25	14787138,81	254641,63

Д3=1,40874E+12

Получаем значение коэффициента а₂ делением ₃ на :

0,2436663

Получили уравнение регрессионной модели:

y=16,89813-0,0055576*x1 +0,2436663*x2

Эластичность.

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

Эyx1=-0,268470485

Эyx2=1,065123555

Это означает, что если среднее количество элементов возрастёт на 1 %, то количество перестановок возрастет на 1,065123555%, если количество элементов возрастёт на 1 %, то количество сравнений уменьшится на 0,268470485%.

Коэффициент детерминации и коэффициент множественной корреляции.

На их основании можно сделать заключение о значимости построенной регрессионной модели и возможности её дальнейшего использования для объяснения и анализа метода сравнения, проявляющегося в данной задаче при сортировке элементов одномерных массивов.

Найдем необходимые коэффициенты.

Таблица 7 Матрица корреляции факторных признаков x1, x2

	x1	x2
x1	1	0,9898675
x2	0,9898675	1

Таблица 8 Обратная матрица корреляции

49,59743705	-49,094891
-49,09489102	49,597437

Таблица 9. Вектор коэффициентов парной регрессии результативного признака y и факторных признаков x1, x2

rx1y=	0,974845
rx2y=	0,993032

На основании приведённых исходных данных получаем коэффициент множественной корреляции:

Rxy=0,9893859

Коэффициент детерминации:

D=0,9788844

Так как коэффициент детерминации больше 0,5, это указывает на довольно высокую достоверность построенной регрессионной модели, поэтому возможно её применение для объяснения процессов сортировки.

3.2 Исследование сортировки методом Бетчера посредством построения линейного уравнения регрессии

Сначала были собраны исходные данные. Созданные на Turbo Pascal 7.0 программы запускались с исходными массивами от одного до 200 элементов, подсчитывалось число сравнений и перестановок для каждой группы. Затем для каждой группы элементов формировались средние значения перестановок, сравнений, неупорядоченных элементов и размерностей исходных массивов.

Таблица 10 Исходные данные

группа	У	Х1	Х2
от 1 до 20	12	47	17
от 21 до 50	22	127	43
от 51 до 100	66	598	405
от 101 до 150	116	1326	405
от 151 до 200	156	1612	472
сумма	372	3710	1342
ср.знач.	74,4	742	268,4

парные коэффициенты корреляции r_yx1 , ryx2 , rx1x2:

Ryx1=0,995296396

Ryx2=0,901676587

Rx1x2=0,891177289

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

Уравнение регрессии.

Уравнение регрессии будет линейного вида. Для нахождения применим метод наименьших квадратов.

Таблица 11 система нормальных уравнений в матричном виде

а0	а1	а2	У
5	3710	1342	372
3710	4732762	1546344	448114
1342	1546344	552972	148492

Считаем главный определитель, другие определители, а также вычисляем коэффициенты а₀, а₁, а₂.

Таблица 12 Определители системы нормальных уравнений в матричном виде

гл.опред.	3,92766E+11
det(a0)	3,40446E+12
det(a1)	31955985760
det(a2)	7846611312

8,667885795 ; 0,081361283; 0,019977802

Получили уравнение регрессионной модели:

Y=8,667885795 +0,081361283*x1 + 0,019977802*x2

Эластичность.

Влияние отдельных факторов в многофакторных моделях может быть охарактеризовано с помощью частных коэффициентов эластичности, которые показывают, на сколько процентов изменится результативный признак, если значение одного из факторных признаков изменится на 1 %, а значения других признаков останутся неизменными. Для построенной регрессионной модели

Эyx1=0,811426

Эyx2=0,07207

Это означает, что если средний размер одномерного массива данных возрастёт на 1 %, то количество операций сравнений увеличится на 0,811426%, а количество перестановок возрастет на 0,07207%.

Коэффициент детерминации и коэффициент множественной корреляции.

Таблица 13 Матрица корреляции факторных признаков x1, x2

1	0,891177
0,891177	1

Таблица 14 Обратная матрица корреляции

4,85901474	-4,33024
-4,330243584	4,859015

Таблица 15 Вектор коэффициентов парной регрессии результативного признака y и факторных признаков x1, x2

rx1y	0,995296
rx2y	0,901677

На основании приведённых исходных данных получаем коэффициент множественной корреляции:

Rxy = 0,991663622

Коэффициент детерминации:

D = 0,983396738

Так как коэффициент детерминации больше 0,5, это указывает на довольно высокую достоверность построенной регрессионной модели, поэтому возможно её применение для объяснения процессов сортировки.

3.3 Сравнительный анализ двух алгоритмов

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

Коэффициент корреляции для метода Шелла сравнений: Rx1y =0,974845. Он показывает характер и силу связи между числом элементов в массиве и количеством сравнений и перестановок, необходимых для сортировки данного массива, т. е. определяет, каким будет результат в зависимости от различного объема сортируемых данных. Так как значение коэффициента корреляции близко к 1, то можно сделать вывод, что для метода Шелла наблюдается очень сильная связь, т. е. с увеличением размерности массива, результат возрастает.

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

Другой коэффициент для этого же метода Rx2y=0,993032 показывает направление и силу связи между числом элементов, стоящих не на месте и результатом. Так как значение коэффициента близко к 1, поэтому связь очень сильная. Так как коэффициент положительный, то связь -- прямая и при увеличении числа неупорядоченных элементов, количество сравнений и перестановок будет также увеличиваться.

Коэффициент корреляции для метода Бэтчера: Rx1y=0,995296. Это говорит о том, что зависимость результата от размера массива прямая и сильная, т. е. с увеличением размера массива, количество сравнений и перестановок увеличивается.

Другой коэффициент корреляции для метода Бэтчера: Rx2y=0,901677. Этот коэффициент также положительный и близок к 1, что указывает на прямую и очень сильную зависимость числа сравнений и перестановок от количества элементов, стоящих не на месте. Соответственно, если массив полностью неупорядочен, то необходимо сравнивать практически все элементы между собой и поменять их все, чтобы получить упорядоченный массив; если же некоторые элементы уже стоят на своих местах, то потребуется немного сравнений и перестановок для получения желаемого результата.

Коэффициент множественной корреляции для метода Шелла: Rxy=0,9893859 и этот же коэффициент для метода Бэтчера равный: Rxy=0,991663622.

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

Так как коэффициенты множественной корреляции близки к 1, то можно сделать вывод, что количество элементов, стоящих не на месте почти полностью зависит от размерности массива.

Коэффициент детерминации для метода Шелла: D=0,9788844 и метода Бэтчера: D=0,983396738.

Так как коэффициенты детерминации для двух методов больше 0,5, то это указывает на довольно высокую достоверность построенных регрессионных моделей, т.е. построенные модели можно использовать для анализа эффективности алгоритмов.

Уравнение регрессионной модели для метода Шелла -- линейное и имеет вид: y=16,89813-0,0055576*x1 +0,2436663*x2.

Уравнение регрессии для метода Бэтчера также является линейным и выглядит следующим образом: Y=8,667885795 +0,081361283*x1 + 0,019977802*x2.

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

Эластичность построенной регрессионной модели для метода Шелла:

Эyx1= -0,268470485; Эyx2= 1,065123555.

Частные коэффициенты эластичности для метода Бэтчера:

Эyx1= 0,811426; Эyx2= 0,07207.

На основании вышеприведенных частных коэффициентов эластичности для данных регрессионных моделей можно сделать следующий вывод:

Алгоритм сортировки Шелла выигрывает при рассмотрении количества элементов, находящихся в массиве (т. к. при возрастании среднего размера одномерного массива на 1%, количество операций сравнений и перестановок уменьшится на 0,545338456), а метод Бэтчера в этом случае менее эффективен.

Однако если увеличить число элементов, стоящих не на месте на 1%, то результат для метода Бэтчера возрастет на 0,584324086%, а для метода Шелла этот процент будет больше, следовательно, второй алгоритм в данном случае работает хуже.

ЗАКЛЮЧЕНИЕ

В этой курсовой работе были изучены следующие вычислительные алгоритмы: метод Шелла и метод Бэтчера.

Был проведен сравнительный анализ эффективности алгоритмов и их возможностей использования для решения различных задач.

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

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

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

Собраны статистические данные по этим показателям. Для сбора данных были проведены тестирования с использованием двух различных программ (для каждого метода), реализованных с помощью языка программирования Turbo Pascal 7.0.

По собранным данным были выбраны и построены функции для уравнений регрессии и графики соответствующих уравнений. Уравнение регрессии для метода Шелла получилось линейным и приняло вид: Y=16,89813-0,0055576*x1 +0,2436663*x2. Уравнение регрессии для метода Бэтчера выглядит следующим образом: Y=8,667885795 +0,081361283*x1 + 0,019977802*x2. При построении уравнения регрессии, в частности для определения коэффициентов уравнения был применен метод наименьших квадратов. Все расчеты по построению уравнения регрессии, нахождения эластичности, коэффициентов парной и множественной корреляции и детерминации проводились с помощью табличного процессора Microsoft Excel 2002. Использовались следующие функции:

Сумм - сумма аргументов;

Произвед - произведение аргументов;

Срзнач - нахождение среднего значения;

Мопред - вычисление детерминанта;

Мобр - вычисление обратной матрицы;

Корень - нахождение квадратного корня.

При регрессионном анализе были оценены качественные характеристики построенных уравнений и проведен анализ показателей, вытекающих из полученных расчетов.

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

Получены коэффициенты детерминации, равные: для метода Шелла D=0,9788844; для метода Бэтчера: D=0,983396738. Они оказались близки к единице, т. е. достоверность построенных уравнений регрессии получилась довольно высокой, и эти уравнения можно использовать для анализа эффективности алгоритмов.

Были определены коэффициенты эластичности, позволяющие узнать, на сколько увеличится количество сравнений и перестановок при возрастании размерности массива и числа элементов, находящихся до начала сортировки не на своих местах, на 1%. Получились очень интересные результаты, по которым нельзя однозначно сказать какой из исследуемых алгоритмов является наиболее эффективным. Коэффициент эластичности показал, что если увеличить число элементов, стоящих не на месте на 1%, то результат для метода Бэтчера увеличится на 0,07207%, а для метода Шелла этот процент будет возрастать на 1,065123555%. Откуда можно сделать вывод, что второй алгоритм в данном случае работает хуже. Алгоритм Шелла выигрывает при рассмотрении количества элементов, находящихся в массиве (т. к. при возрастании среднего размера одномерного массива на 1%, количество операций сравнений и перестановок уменьшится на 0,268470485%), а метод Бэтчера в этом случае менее эффективен (Эyx1= 0,811426).

В результате сравнительного анализа возможностей использования алгоритмов для решения различных задач, выяснилось, что рассмотренные алгоритмы относятся к одному классу алгоритмов. Они мало подходят для сортировки массивов с большим количеством сортируемых элементов. При малых N (N?25) эти алгоритмы очень эффективны, кроме того, они достаточно просто реализуются программно и не требуют дополнительного объема памяти, способны адаптироваться к различным компьютерам. Если возникнет необходимость отсортировать большой массив, то лучше применить другие алгоритмы сортировки, которым понадобиться меньше времени для достижения результата.

Анализируя коэффициенты корреляции Rxy можно сделать вывод, что на эффективность метода Бэтчера размерность исходных данных оказывает большее влияние, чем на метод Шелла (Rxy=0,9893859- для сортировки методом Шелла и Rxy=0,991663622- для сортировки методом Бэтчера).

В заключении можно сделать вывод: для обработки массивов с большим количеством элементов более эффективно работает метод Бэтчера.

Библиография

1. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффи Д. Ульман. Структуры данных и алгоритмы.: Пер. с англ.: М.: Издательский дом «Вильямс», 2003. - 384 с.: ил. - Парал. Титю англ.

2. Дональд Э. Кнут «Искусство программирования»: М.: Наука, 2006. - 437 с.

3. Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ/ Пер. с англ. под ред. А.Шеня. - М.: МЦНМО, 2002. - 960 с.: 263 ил.

4. Минакова Н.И., Невская Е.С., Угольницкий Г.А., Чекулаева А.А., Чердынцева М.И. «Методы программирования»: М.: «Вильямс», 2005. - 502 с.

5. Никлаус Вирт. Алгоритмы и структуры данных: Пер. с англ. - 2-е изд., испр. - СПб.: Невский Диалект, 2001. - 352 с.: ил.

6. Практикум по эконометрике: Учеб. Пособие / Под ред. И.И. Елисеевой. - М.: Финансы и статистика, 2004. - 279 с.

7. Эконометрика: Учебник для вузов / Под. ред. И.И. Елисеевой. - М.: Финансы и статистика, 2004. - 346 с.

ПРИЛОЖЕНИЯ

Приложение А Программа № 1: Метод Шелла

program kurs;

type arr=array[1..200] of integer;

var r,n:integer;

var Kol_Per,Kol_Srav, i,j:integer;

var arr1:arr;

var a1:arr;

procedure shellsort( var arr);

var i,incr,j:integer;

s:integer;

begin

incr:=n div 2;

while incr>0 do begin

for i:=incr+1 to n do begin

j:=i-incr;

if a1[j] > a1[j+incr] then begin Kol_Srav:=Kol_Srav+1;

s:=a1[j];a1[j]:=a1[j+incr];

a1[j+incr]:=s;Kol_Per:=Kol_Per+1;

End else Kol_Srav:=Kol_Srav+1;

end; incr:=incr-1; end; end;

begin

Writeln ('Введите количество перестановок ');

Readln(n);

Writeln('Введите исходный массив');

For i:=1 to n do

readln(a1[i]);

Writeln;

Writeln('Вывод исходного массива');

For i:=1 to N do

Write(a1[i]:5);

Writeln;

Kol_Per:=0;

Kol_Srav:=0;

shellsort(a1);

Writeln('Kol_Per=',Kol_Per);

Writeln('Kol_srav=',Kol_Srav);

Writeln('Вывод отсортированного массива');

For i:=1 to N do

Write(a1[i]:5);

Writeln;

Writeln('Введите <Enter> для продолжения ');

Readln;

End.

Результаты для программы № 1:

Пример 1:

Введите количество элементов n=30

вывод массива А

4 20 3 9 16 24 7 1 17 10 21 26 13 14 2 23 6 27 19 12 28 22 8 30 25 15 18 11 29 5

вывод отсортированного массива А

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

ВЫВОД ЧИСЛА ПЕРЕСТАНОВОК Kol_Per=45

ВЫВОД ЧИСЛА СРАВНЕНИЙ Kol_Srav=330

Кол-во эл-тов, стоящих не на месте p=21

Пример 2:

Введите количество элементов n=16

вывод массива А

1 2 14 9 5 6 10 8 13 4 11 12 16 7 15 3