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

Вывод

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


 

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

45211. Этапы и технологии проектного обоснования рекламной кампании 28.5 KB
  Этапы и технологии проектного обоснования рекламной кампании Определение целей и задач рекламной кампании. Содержание целевого блока определяется в зависимости от нескольких факторов: проблем рекламодателя; специфики предмета рекламной коммуникации размера и особенностей целевого сегмента силы партнеров и характера конкуренции этапа жизненного цикла предмета рекламы и др. Возможные цели рекламной кампании: продвижение продукта или услуги на рынок; стимулирование потребительской активности целевых групп путем формирования потребности в...
45212. Маркетинговый потенциал и технологии разработки социально культурных программ 26 KB
  Маркетинговый потенциал и технологии разработки социально культурных программ Потенциал: В постиндустриальном мире сфера культуры из иждивенца экономики превращается в главную движущую силу развития общества. За счет культурных ресурсов развивается въездной туризм. Известные корпорации активно участвуют в спонсировании масштабных культурных акций активно используя культурные символы в продвижении своих имен и брендов. Поддержка культурных программ способствует формированию позитивного имиджа компании ее репутация повышает социальную...
45213. Этапы и технологии проектирования, социально культурной акции 36 KB
  Характеристика аудитории проекта т. Характеризуя аудиторию программы необходимо выявить наиболее сущностные личностные и социально-культурные проблемы; определить их источники установить причинно-следственную зависимость; обосновать возможности разрешения или предупреждения в рамках разрабатываемого проекта. Именно они определяют наряду с социальнокультурной проблематикой цели и задачи проекта виды и содержание деятельности. Ориентация на решение социальных проблем это способ повышения общественной значимости проекта а...
45214. Социальные проекты общественных объединений: маркетинговый потенциал, технологии, этапы разработки, условия реализации 24 KB
  Характеристика аудитории проекта. Обоснование целей и определение задачи проекта. Инструментальное оснащение проекта. Бюджет проекта.
45215. ПР как форма маркетинговых коммуникаций организации и сумма технологий 26 KB
  ПР искусство убеждающей коммуникации. Профессиональная компетентность ПР овладение наиболее эффективными приемами и методами коммуникации убеждения влияния на общественное мнение. Сферы публичной коммуникации: политика экономика социальнкульт. Средства формирования эффективной системы коммуникаций субъекта со средой: позитивное позиционирование субъекта по отношению к конкурентам наращивание его соцстатусного и культсимволического капитала формирование конверциональных ресурсов коммуникации субъекта со всеми составляющими...
45216. Опыт использования информационных техник как средства диалога с общественностью в политической жизни Древней Греции и Рима 32 KB
  Трудно сказать к каким временам восходит зарождение ремесла паблик рилейшнз. И это не удивительно ведь паблик рилейшнз строятся на усилиях не только убеждать людей но и влиять на поведение. Фактор убеждения и сегодня остается движущей силой практики рилейшнз. Рассмотрение ранних форм и методов ремесла связей с общественностью влияния на людей убеждения их поможет глубже понять современное состояние паблик рилейшнз путь пройденный ими в своем развитии.
45217. Зарубежный опыт становления политических ПР технологий 37 KB
  Для этого им служил целый арсенал ПР инструментов: пресс-бюллетени газеты встречи с героями освободительного движения лозунги символы риторика паблисити организации выставки митинги поэзия песни праздники фейерверки. Можно сказать что Бостонское чаепитие это первый классический пример организации псевдособытия и использования принципа пресспосредничества в связях с общественностью. Важнейшим шагом в развитии ПР в тот период стала борьба за конституцию между федералистами и их противниками которая развернулась на страницах...
45218. Опыт пропаганды и агитации советского периода 41.5 KB
  Опыт пропаганды и агитации советского периода И. Но для того чтобы проводить работу наиболее эффективно необходимо создание системы понастоящему массовой пропаганды которая . В 1939 году было создано управление пропаганды и агитации при ЦК ВКПб По словам Сталина: .сосредоточить в одном месте дело партийной пропаганды и агитации и объединить отделы пропаганды и агитации и отделы печати в едином Управлении с организацией соответствующего отдела пропаганды и агитации в составе каждой республики краевой и областной парторганизации.
45219. Современные политические ПР-технологии России: опыт, тенденции и проблемы развития 48 KB
  Задачи: формирование и продвижение имиджа доведение до избирателя правдивой информации о кандидатах донесение до кандидата реальных проблем и ожиданий групп населения. Особенность воздействия на массовое сознание состоит в том что с помощью него можно усилить роль тех черт кандидата его способностей внешности которые могут привлечь симпатии избирателей. Для персонального консультирования специалист должен уметь: провести адекватную диагностику ситуации видеть явные и скрытые проблемы и ресурсы; выстроить стратегию наращивания...