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

Вывод

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


 

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

15644. Инвазионизм и библейская археология 220.5 KB
  Лекция 23. Инвазионизм и библейская археология 1. Миграционизм как инвазионизм. Миграция вообще предстает в исходном пункте как эмиграция в конечном – как иммиграция а если в новую страну передвинулся целый народ или армия то такая иммиграция описывается как вторж...
15645. Комбинационизм в археологии 279.5 KB
  Лекция 26. Комбинационизм. Незамеченное течение. В трансмиссионизме постепенно всё большее место занимала констатация не самих заимствований а их воздействия на остальную культуру на местные ее элементы причем в воспринимающих очагах под воздейст...
15646. Эмпирические школы в археологии 480.5 KB
  24 Лекция 31. Эмпирические школы. 1. Введение. В археологической литературе иногда встречаются указания на эмпирическую школу но всякий раз оказывается что под этим названием фигурируют разные группы ученых разного времени и в разных странах. То ест
15647. Автономная археология в историческом синтезе и эмергентизм 424 KB
  Лекция 33. Автономная археология в историческом синтезе и эмергентизм 1. На руинах археологии обитания. В 1947 г. на конференции в Гамбурге собравшимся немецким археологам было сказано: Сегодня наша преистория прежде всего стоит перед задачей привести в порядок сп
15648. Реболлинг (восстановление шариковых выводов) BGA компонентов (чипов) 446.5 KB
  Реболлинг восстановление шариковых выводов BGA компонентов чипов Рис.1 Примеры выполненных трафаретов для восстановления шариков BGA Рис.2 Восстановленные шариковые выводы BGA чипа Необходимое оборудование Сушка рекомендуется для подсушки ком
15649. ДОМАШНИЙ АРЕСТ КАК МЕРА ПРЕСЕЧЕНИЯ В УГОЛОВНОМ ПРОЦЕССЕ 36.95 KB
  ДОМАШНИЙ АРЕСТ КАК МЕРА ПРЕСЕЧЕНИЯ В УГОЛОВНОМ ПРОЦЕССЕ А. АЛЕКСАНДРОВ Александров Александр профессор Нижегородской академии МВД России доктор юридических наук профессор. Федеральный закон от 7 декабря 2011 г. N 420ФЗ содержит новую редакцию ст. 107 УПК РФ рег
15650. УГОЛОВНО-ПРОЦЕССУАЛЬНЫЕ ГАРАНТИИ ОБЕСПЕЧЕНИЯ РЕАЛИЗАЦИИ ПРАВ НЕСОВЕРШЕННОЛЕТНИХ ПОТЕРПЕВШИХ 23.94 KB
  УГОЛОВНОПРОЦЕССУАЛЬНЫЕ ГАРАНТИИ ОБЕСПЕЧЕНИЯ РЕАЛИЗАЦИИ ПРАВ НЕСОВЕРШЕННОЛЕТНИХ ПОТЕРПЕВШИХ М.Ю. АРЧАКОВ В статье автором рассмотрены теоретические вопросы касающиеся проблем совершенствования уголовнопроцессуального порядка реализации в отечественном у...
15651. РАЗУМНЫЙ СРОК КАК ОЦЕНОЧНОЕ ПОНЯТИЕ В УГОЛОВНО-ПРОЦЕССУАЛЬНОМ ПРАВЕ 30.83 KB
  РАЗУМНЫЙ СРОК КАК ОЦЕНОЧНОЕ ПОНЯТИЕ В УГОЛОВНОПРОЦЕССУАЛЬНОМ ПРАВЕ М.Т. АШИРБЕКОВА Ф.М. КУДИН В процессе своего реформирования уголовнопроцессуальное законодательство обогащается дополнительными приемами законодательного регулирования уголовнопроцессуаль
15652. Бедный средний класс 28 KB
  Бедный средний класс В июне обнародован доклад Малообеспеченные в России: кто они как живут к чему стремятся подготовленный Институтом социологии РАН в сотрудничестве с московским представительством Фонда имени Фридриха Эберта. Согласно этому докладу самой массо...