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

Вывод

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


 

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

25275. Криза новочасного матеріалізму (критика Дж.Берклі та Д.Юма) 31.5 KB
  Берклі дотримується позиції суб’єктивноідеалістичного сенсуалізму. Свою критику емпіризму Берклі починає з розгляду локківського вчення. Використавши ці положення Локка як відправні точки Берклі фактично відступає від локківської позиції. А Берклі дає на них відповідь – просто витлумачує Локка в дусі категоричного заперечення об’єктивності первинних якостей.
25276. Піднесення і падіння ідеалістичної філософії (XVIII-XIX ст.) 35.5 KB
  Речі вважає він лише здаються нам незалежними від нас доки ми не усвідомили що вони є продуктами свідомої діяльності суб’єкту. Це відбувається за рахунок суб’єктивації природного світу здійснюваної за рахунок свободи як принципу активної діяльності суб’єкта. Вже в Канта поняття трансцендендентального суб’єкту не співпадає ні з індивідуальним людським суб’єктом ні з божественним розумом традиційного раціоналізму.Шеллінг 17551854 тотожність протилежностей суб’єкта і об’єкта робить вихідним пунктом свого вчення.
25277. Матеріалістичне розуміння історії К.Маркса 27.5 KB
  Гегель розуміє розвиток історії як розвиток абсолютного духу. Для нього історичний розвиток – це розвиток продуктивних силзасобів виробництва знарядь праці тобто капіталу а не духовності.
25278. Деградація філософії К.Маркса у працях Ф.Енгельса у 80-90р XIX 28.5 KB
  Енгельса у 8090р XIX Послідовники Маркса не змогли утриматись на рівні адекватного розуміння його філософії. Типовим виявом цього стала для Енгельса абсолютизація специфічного для філософії XVIIXVIIIст. протистояння матеріалізму та ідеалізму поширюване ним на всю історію філософії звідти і проголошення питання про відношення матерії та свідомості основним питанням філософії а боротьби матеріалізму та ідеалізму основною рушійною силою історикофілософського процесу.
25279. Діалектичний та історичний матеріалізм – російсько-радянська вульгаризація Марксового матеріалістичного розуміння історії 27.5 KB
  Ця філософія вульгаризувавши і догматизувавши елементи Марксової філософії на базі ленінського принципу партійності постала як різновид тоталітарної філософії XXст. – так званого марксизмуленінізму що ніби знаменувала своєю появою революційний поворот у філософії і була в цьому ранзі проголошеною єдино правильною і єдино науковою філософією. Подоланню тоталітарного марксизмуленінізму великою мірою сприяла її критика в 1960х у дусі повернення до адекватного прочитання філософії Маркса молодим поколінням філософів у СРСР у...
25280. Західноєвропейський (Д.Лукач, група «Праксіс», К.Косік. Г.Маркузе, Ж-ПСартр) та радянський (Е.Ільєнков, Г.Братішев, П.Копнін, З.Кабадзе, Ж.Абдільдін) неомарксизм 60-70 рр 62 KB
  Неомарксизм – это особое течение общественной в том числе философской мысли 50–60х годов нашего века выражавшее тот большой интерес к творчеству Маркса и его философии который был характерен для этого периода. Речь идет не о новых исследованиях работ Маркса и не о новой интерпретации его творчества. Неомарксизм – это определенное теоретическое устремление найти при помощи Маркса ответы на животрепещущие вопросы современности. Как правило все они стремились понять насколько применимы взгляды Маркса к решению современных им проблем...
25281. Позитивізм ХІХ-ХХ ст. у Західній Європі та Російській імперії 34 KB
  Існує три історичні стадії позитивізму: перший€ класичний позитивізм другий€ позитивізм емпіріокритицизм і третій€ позитивізм неопозитивізм. Засновником позитивізму був О.Спенсер ще один представник першого позитивізму. Представниками ІІго позитивізму є Е.
25282. Философия прагматизма и неопрагматизма: основные идеи, их эволюция 36 KB
  опыте Мид социальный бихевиоризм и теория значения Неопрагмм К. Теория сомненияверы. наука сама на нее опирается Теория значения. Теория истины.
25283. ЭКЗИСТЕНЦИАЛИЗМ (Э.) 45 KB
  Альбер КАМЮ 19131960 Алжирский унивт. Альбер Камю 1913 1960. Особенностью философии Камю является то что у него нет систематизированного и всеохватывающего философского учения он занимается почти исключительно этическими проблемами. Основная философская работа Камю Миф о Сизифе открывается словами: Есть лишь одна действительно серьезная философская проблема: это самоубийство.