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

Вывод

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


 

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

27325. Память и способы запоминания 34.5 KB
  По содержанию образная память моторная память эмоциональная память; по организации запоминания эпизодическая память семантическая память процедурная память; по временным характеристикам долговременная декларативная память кратковременная память ультракратковременная память; по физиологическим принципам определяемая структурой связей нервных клеток она же долговременная и определяемая текущим потоком электрической активности нервных путей она же кратковременная по наличию цели произвольная и непроизвольная; по наличию...
27326. Мышление как особый психологический процесс 35.5 KB
  К формам мышления относятся: Понятие – это форма мышления отражающая существенные свойства связи и отношения предметов и явлений. Суждения – это форма мышления позволяющая устанавливать простейшие связи между познаваемыми явлениями как связи и отношения между предметами и явлениями окружающего мира их свойствами и признаками. Умозаключение – форма мышления в которой из одного или нескольких суждений выводится новое суждение. Виды мышления чаще всего мышление подразделяют на теоретическое понятийное и образное и практическое...
27327. Педагогика в системе гуманитарных знаний и наук о человеке 20.18 KB
  Педагогика начального образования как наука о воспитании образовании и развитии младших школьников Педагогика с греческого означает детоводство дитяведение. Педагогика наука о воспитании человека совокупность теоретических и прикладных наук изучающих воспитание образование и обучение. Педагогика – это относительно самостоятельная дисциплина имеющая свой объект и предмет изучения. Педагогика в широком смысле – влияние всех внешних воздействий естественной и социальной среды.
27328. Методология и методика педагогического исследования, Методологическая культура учителя 30.65 KB
  Методы обучения т. В свою очередь возможность исследователя сформировать новые методы и подходы в своей педагогической деятельности является показателем его высокой методологической культуры. Теоретические и эмпирические методы педагогического исследования Пути способы познания объективной реальности принято называть методами исследования. Различают теоретические и эмпирические методы педагогического исследования.
27329. Система образования и ее характеристика 23.22 KB
  Ведущую роль в области образования играют принципы государственной политики. Создавать условия для общедоступности образования приспособления системы образования к уровням и особенностям развития и подготовки обучающихся воспитанников. Носить демократический характер образования и допускать автономность обр.
27330. Целостный педагогический процесс 42.13 KB
  Раскрывая вторую характерную черту педагогического процесса усовершенствование он пишет: Усовершенствование же имеет три направления: 1 устранение препятствий с пути естественного развития сил отрицательная сторона; 2 прямое положительное содействие правильному развитию наличных способностей положительная сторона; 3 искоренение недостатков и насаждений ценных свойств усовершенствование в тесном смысле. Понятие структура и функции педагогического процесса Педагогическим процессом называется развивающиеся взаимодействие...
27331. Воспитательный процесс и его характеристика 17.82 KB
  Сложность воспитательного процесса Сложность воспитательного процесса состоит и в том что его результаты не так явственно ощутимы и не так быстро обнаруживают себя как например в процессе обучения. Одна из особенностей воспитательного процесса его непрерывность. Процесс воспитания комплексный что означает единство целей задач содержания форм и методов воспитательного процесса подчиненное идее целостности формирования личности.
27332. Концепция духовно-нравственного развития и воспитания личности гражданина России 21.42 KB
  Принципы: Организация социально открытого пространства духовнонравственного развития и воспитания личности гражданина России нравственного уклада жизни обучающихся осуществляется на основе: нравственного примера педагога; социальнопедагогического партнёрства; индивидуальноличностного развития; интегративности программ духовнонравственного воспитания; социальной востребованности воспитания. Нравственность учителя моральные нормы которыми он руководствуется в своей профессиональной деятельности и жизни его отношение к своему...