15337

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

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

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

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

Русский

2013-06-13

49 KB

17 чел.

Лабораторная работа №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), а отклонения от этого значения довольно малы.

Вывод

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


 

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

35929. Виноград как сырье для винодельческой промышленности. Требования, предъявляемые к винограду, при производстве различных типов вин. Факторы, определяющие качество винограда. Сбор урожая 59.95 KB
  Факторы определяющие качество винограда. Характеристика винограда Сырьём для винодельческой промышленности является виноград. Ягоды винограда содержат высокосахаристый сок из которого получают вино. Характеристика и механический состав винограда.
35930. Особливості обслуговування у податкових органах великих платників податків 57.5 KB
  24 Податкового кодексу великий платник податків це юридична особа у якої обсяг доходу від усіх видів діяльності за останні чотири послідовні податкові звітні квартали перевищує п'ятсот мільйонів гривень або загальна сума сплачених до Державного бюджету України податків за платежами що контролюються органами державної податкової служби за такий самий період перевищує дванадцять мільйонів гривень. У разі включення платника податків до Реєстру великих платників податків далі Реєстр ВПП та отримання повідомлення центрального органу...
35931. Биосфера. Роль живого вещества в жизни планеты. Географические закономерности распределения биологического разнообразия и биомассы 57 KB
  Роль живого вещества в жизни планеты. В структуре биосферы Вернадский выделял семь видов вещества: живое; биогенное возникшее из живого или подвергшееся переработке; косное абиотическое образованное вне жизни; биокосное возникшее на стыке живого и неживого; к биокосному по Вернадскому относится почва; вещество в стадии радиоактивного распада; рассеянные атомы; вещество космического происхождения. 2 Биогенез преобразование косного вещества геосферы земли в живое вещество биосферы образование высокомолекулярных органических...
35932. Понятие, функции, предмет и объект массовых коммуникаций 56.95 KB
  История развития коммуникации: Изобретение письма; Изготовление печатного станка; Внедрение электронных СМИ; Термин появился в начале 20 в. Он определил основные вопросы коммуникации: кто передал Что передал По какому каналу Кому С каким результатом Формула Лассуэлла стала как собственно моделью отражающей структуру коммуникационного процесса так и моделью исследования этого процесса его структуры и отдельных элементов. В первую очередь это важно для массовой коммуникации особенно в кризисные моменты общественной жизни...
35933. Размножение 56.5 KB
  БЕСПОЛОЕ РАЗМНОЖЕНИЕ бесполое размножение происходит без образования гамет в нем участвует лишь один организм. Перед делением клетки происходит репликация ДНК а у эукариот деление и ядра. В большинстве случаев происходит бинарное деление при котором образуются две идентичные клетки. Множественное деление при котором следом за рядом повторных делений клеточного ядра происходит деление самой клетки на огромное множество дочерних клеток можно наблюдать у споровиков это группа простейших и к ним относится например возбудитель малярии...
35934. Экологическая экспертиза 56.5 KB
  в Российской Федерации вступил в силу закон Об экологической экспертизе где определяется что экологическая экспертиза это установление соответствия намечаемой хозяйственной и иной деятельности экологическим требованиям и определение допустимости реализации объекта экологической экспертизы в целях предупреждения возможных неблагоприятных воздействий этой деятельности на окружающую природную среду и связанных с ними социальных экономических и иных последствий реализации объекта экологической экспертизы. Основные принципы проведения...
35935. Трудовая деятельность. Роль труда в развитии человека и общества 59 KB
  Труд это особая система состоящая из трех компонентов: Предметы труда это вещество природы вещь или комплекс вещей на которые человек воздействует в процессе труда при помощи средств труда с целью приспособления их для удовлетворения личных и производственных потребностей. Если предметы труда образуют материальную основу продукта то они называются основными материалами а если способствуют самому процессу труда или придают основному материалу новые свойства то вспомогательными материалами. К предметам труда в широком смысле...
35936. Перекрытия ребристые с плитами, опертыми по контуру. Общие сведения 55.5 KB
  Общие сведения Конструктивная схема перекрытий включает плиты работающие на изгиб в двух направлениях и поддерживающие их балки. Толщина плиты в зависимости от ее размеров и нагрузки составляет 50140 мм но не менее l1 50 Применяют в основном по архитектурным соображениям. а б а трещины на нижней поверхности плиты б на верхней 2 Расчет плит опертых по контуру как упругих систем Характер распределения усилий в плите можно рассматривать в результате расчета плиты как тонкой пластинки для этого...
35937. Состояние и перспективы развития винодельческого производства в России, основные регионы возделывания винограда и производства винодельческой продукции и специализация 55.81 KB
  Более 400 винодельческих заводов занимаются обработкой и розливом вина. Потребление вина в России которое до начала антиалкогольной кампании 19701985 гг. Тем не менее по потреблению вина на душу населения Россия занимает одно из последних мест в Европе. В Краснодарском крае преимущественно производят столовые вина и виноматериалы для игристых вин.