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

Вывод

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


 

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

7916. Література. Драматургія. Архітектура та містобудування. Живопис. Музика. Музеї. Українські підприємці-благодійники. Родини Терещенків та Харитоненків 34.55 KB
  Література. Драматургія. Архітектура та містобудування. Живопис. Музика. Музеї. Українські підприємці-благодійники. Родини Терещенків та Харитоненків Мета: Створити умови для всебічного розуміння учнями всіх особливостей розвитку української культур...
7917. Фольклор та декоративно-ужиткове мистецтво. Повсякденне життя: звичаї, традиції, побут. Зміни у житті українських жінок. Особливості релігійного життя 26.35 KB
  Фольклор та декоративно-ужиткове мистецтво. Повсякденне життя: звичаї, традиції, побут. Зміни у житті українських жінок. Особливості релігійного життя МЕТА: розуміння учнями всіх особливостей розвитку народного мистецтва. пов...
7918. Поняття людини як біосоціальної істоти 22.26 KB
  Поняття людини як біосоціальної істоти Людина... Хто вона така? На перший погляд це питання зовсім просте. Хто ж не знає, хто така людина? Адже на рівні здорового глузду кожен з нас впевнено виділяє людину з оточуючого середовища, її відмінність від...
7919. Радянська українізація та культурна революція. Освіта та наука 68 KB
  Радянська українізація та культурна революція. Освіта та наука. Перемога радянської влади в Україні призвела до того, що всі досягнення в галузі українізації були визнані контрреволюційними, націоналістичними та ворожими народу. В 1919 та на початку...
7920. Українська культура періоду ІІ світової війни 58 KB
  Українська культура періоду ІІ світової війни Радянські митці у своїх творах оспівували масовий героїзм, стійкість, ратні подвиги радянських воїнів, їх безмежну відданість Комуністичній партії, беззавітну любов до Батьківщини. У період Великої Вітчи...
7921. Політика Українізації 59 KB
  Українізація Причини українізації Політикаукраїнізаціїсуперечила великодержавним прагненням ВКП(б), але була вимушена ворожим ставленням до радянської влади з боку населення України, національна свідомість якого зросла за попередні десят...
7922. Освіта: братські школи, Острозька та Києво-Могилянська колегії (Академії) 82.5 KB
  Освіта: братські школи, Острозька та Києво-Могилянська колегії (Академії). Братства - релігійно-національні товариства, що їх створювали при церковних парафіях члени ремісничих та цехових організацій по містах України в 15-17 ст., продовжуючи традиц...
7923. Як зацікавити сучасних школярів предметами духовно-морального спрямування 17.73 KB
  Як зацікавити сучасних школярів предметами духовно-морального спрямування. Ессе на конкурс до Острозької академії. На сучасному етапі розвитку українського суспільства постає проблема виховання моральності школярів. Так як, батьківська турбота сьогодні, в основному, орієнтується на матеріа...
7924. Правобережна Україна в другій половині ХVIII століття 65.5 KB
  Тема уроку. Правобережна Україна в другій половині ХVIII століття. Мета уроку: охарактеризувати події другої половині ХVIII століття на території правобережної України розглянути особливості повстань на західній Україні розвивати вміння учнів анал...