15337

Изучение алгоритма пирамидальной сортировки и реализация его на языке программирования С++

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

Информатика, кибернетика и программирование

Лабораторная работа №2 по дисциплине Структуры и алгоритмы обработки данных Цель работы: Изучение алгоритма пирамидальной сортировки и реализация его на языке программирования С. Задание на работу Написать программу генерирующую числовой массив ра

Русский

2013-06-13

49 KB

16 чел.

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

по дисциплине

«Структуры и алгоритмы обработки данных»

Цель работы:

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

Задание на работу

  1.  Написать программу, генерирующую числовой массив, размер которого задаётся через пользовательский интерфейс.
    1.  Реализовать функцию пирамидальной сортировки.
      1.  Оценить сложность алгоритма программы.

Реализация программы на C++

#include "stdafx.h"

#include "time.h"

#include "stdlib.h"

#include "iostream"

const int size = 20;

using namespace std;

void fillRandomArray(int m[])//функция заполняет массив

{

for(int i = 0; i < size; i++)

 m[i] = rand() % 100;//вводим случайный элемент

}

void printArray(int m[])//функция выводит массив

{

for(int i = 0; i < size; i++)//

 cout << m[i] << ' ';//

cout << endl << endl;

}

void heapify (int pos, int n, int m[])//исправление пирамиды

{

while (2 * pos + 1 < n)

{

 int t = 2 * pos +1;

 if (2 * pos + 2 < n && m[2 * pos + 2] >= m[t])

 {

  t = 2 * pos + 2;

 }

 if (m[pos] < m[t])

 {

  swap(m[pos], m[t]);

  pos = t;

 }

 else break;

}

}

void heap_make(int n, int m[])//создание неубывающей пирамиды

{

for (int i = n - 1; i >= 0; i--)

 {

 heapify(i, n, m);//исправление пирамиды

 }

}

void heap_sort(int m[], int n)//сортировка

{

heap_make(n, m);//создание неубывающей пирамиды

while(n>0)

{

 swap(m[0],m[n-1]);//обмен значениями

 n--;

 heapify(0,n,m);//исправление пирамиды

 }

}

int _tmain(int argc, _TCHAR* argv[])

{

srand(time(NULL));

int a[size];

 fillRandomArray(a);//заполнение массива случайными числами

 cout << "Original array:" << endl;

printArray(a);//вывод

cout << endl;

heap_sort(a,size);//сортировка

cout << "Sorted array:" << endl;

printArray(a);//вывод

 system("PAUSE");

return 0;

}

Скриншот с результатами выполнения программы

Оценка сложности алгоритма

В худшем случае фаза создания пирамиды требует N/2 шагов просеивания, причём на каждом шаге элементы просеиваются через log(N/2), log(N/2+1),…, log(N-1) позиций. Затем фаза сортировки требует n-1 просеиваний с не более чем log(N-1), log(N-2),…,1 пересылок. Кроме того потребуется n-1 пересылок для того, чтобы поставить элементы с вершины пирамиды на свои места. Получается, что даже в наихудшем случае пирамидальная сортировка требует N*log(N) пересылок. Это свойство является важнейшей отличительной особенностью данного алгоритма.                  
Наилучшей производительности можно ожидать, если элементы изначально стоят в обратном порядке. Тогда фаза создания пирамиды не потребует пересылок. Среднее число пересылок равно N/2*log(N), а отклонения от этого значения довольно малы.

Вывод

Алгоритм пирамидальной сортировки был изучен и реализован на языке программирования С++. Была оценена сложность алгоритма.


 

А также другие работы, которые могут Вас заинтересовать

35030. Настройка линейных и угловых единиц измерения 1.19 MB
  В AutoCAD при вычерчивании линий, а также объектов, состоящих из сегментов линий, используется одна из пяти систем линейных единиц. Угловые величины также могут измеряться в одной из пяти систем. Пользователь может выбрать самостоятельно как тип линейных
35031. Защита баз данных на примере MS ACCESS 441.3 KB
  Для защиты БД Ассеss использует файл рабочих групп systеm.mdw (рабочая группа - это группа пользователей, которые совместно используют ресурсы сети), к которому БД на рабочих станциях подключаются по умолчанию. Файл рабочих групп содержит учётные записи пользователей и групп, а также пароли пользователей.
35032. CADElectro + Search 190.5 KB
  Архивное хранилище документов [2. Различные типы документов [2. Согласование и утверждение документов [2. Проведение изменений утвержденных документов [2.
35033. Системы автоматизированного проектирования ЕLECTRICS Light 1.0. 50 KB
  К существенным преимуществам системы заметно отличающим ее от программ аналогичного назначения следует отнести: прямой расчет освещенности с использованием кривых силы света светильников с отслеживанием затенений и отражений от поверхностей; возможность расчета освещенностей в помещениях произвольной конфигурации прямоугольной овальной Г или Tобразной и т.; получение сводного результата по расчету множества помещений и всего здания проекта; возможность детального анализа распределения освещенности по области расчета построение...
35034. WinELSO 232.5 KB
  Работа с программой Для модуля Схема Электрооборудование А Компонуем модель электроснабжения промышленного общественного или жилого сооружения из элементов базы данных Расчетная схема ИСТОЧНИКИ ПИТАНИЯ Генераторы ПРЕОБРАЗОВАТЕЛИ Силовые трансформаторы КОММУТАЦИОННАЯ АППАРАТУРА Автоматические выключатели Дифференциальные автоматические выключатели УЗО Предохранители Контакторы Пускатели Переключатели Разъединители ЭЛЕКТРОПРИЕМНИКИ Силовые Электроосветительная нагрузка Розетки бытовые Квартиры Дома одноквартирные Дома садовые Сооружения...
35035. ADEM как важное звено CALS-технологий 152 KB
  Обычно понимание главной цели происходит не сразу, а в результате кропотливой работы, которая может занимать годы. Даже если задача сформулирована правильно, то для её решения необходимы ресурсы и инструменты, которых может и не существовать на данный момент времени
35036. САПР ElectriCS и UG/Wiring Технологии разработки бортовых электрифицированных систем в авиационно-космической отрасли 282 KB
  Цепочка проектирования ElectriCS и UG Wiring Укрупненная блоксхема цепочки проектирования отображенная на рис. Рис. Порядок разработки принципиальной схемы Э3: внесение в проект электрических устройств из базы электрических устройств рис. 2; определение буквеннопозиционных обозначений электрических устройств; разработка принципиальной схемы с использованием редактора схем utoCD рис.
35037. SCS и SchematiCS 57 KB
  Реферат по презентации программ SCS и SchemtiCS Преподаватель: Сенько В. Использование SchemtiCS4 2. Использование SchemtiCS. Приложение SchemtiCS работает на платформе utoCD и применяется для автоматизации создания и оцифровки схем любой сложности.
35038. Программное обеспечение Solid Edge 67 KB
  Solid Edge — среднеуровневая трехмерная твердотельная CAD-система, предназначенная для проектирования моделей деталей, создания сборок с сохранением ассоциативных связей и выпуска чертежной документации на базе созданных моделей. Интегрирована с системой высокого уровня Unigraphics и системой управления проектом iMAN