Заключение
В результате выполнения данной работы были решены следующие задачи:
Была рассмотрена предметная область поставленной задачи. Рассмотрены общие понятия и определения, знание которых необходимо для реализации поставленной задачи. Проанализированы различные способы сортировка, рассмотрены различные подходы для решения задачи.
Был спланирован общий алгоритм работы программы, реализованный посредством введения и активного использования подпрограмм выполняющих часто повторяемые действия. Разработан и реализован пользовательский интерфейс, а также защита от возникновения ошибки при неправильном вводе.
Выполнение данной работы позволило закрепить изученный материал, а также получить новые, принципиально важные знания в области программирования, проектирования и разработки программных продуктов.
Литература
Книги
«Объектно-ориентированное программирование в С++» / Р. Лафоре - 4-е изд.-СПБ.: Питер, 2011.-928с.: ил.
«Структуры и алгоритмы обработки данных» Цапко И.В., Учебное пособие/Том.политехн. ун-т. – Томск, 2004. – 136 с.
Интернет источники:
http://ru.wikipedia.org/wiki/Пирамидальная_Сортировка
Общая блок-схема работы программы
Начало
Подготовительные процессы
Пользователь выбирает операцию
Ввод элементов массива
Выбрана 1 операция
Выбрана 2 операция
Определение позиции элемента и запись
его в дерево
да
да
нет
Генерация случайных элементов массива
Создание пирамиды
Вывод результат на экран
Сортировка пирамиды
Освобождение памяти
Конец программы
Листинг программы //---------------------------------------------------------------------------
#pragma hdrstop
#include <conio.h>
#include <iostream.h>
//---------------------------------------------------------------------------
#pragma argsused
void downHeap(int a[], long k, long n)
{
// процедура просеивания следующего элемента
// До процедуры: a[k+1]...a[n] - пирамида
// После: a[k]...a[n] - пирамида
int new_elem;
long child;
new_elem = a[k];
while(k <= n/2) // пока у a[k] есть дети
{
child = 2*k;
if( child < n && a[child] < a[child+1] ) // выбираем большего сына
child++;
if( new_elem >= a[child] )
break;
// иначе
a[k] = a[child]; // переносим сына наверх
k = child;
}
a[k] = new_elem;
}
void heapSort(int a[], long size)
{
long i;
int temp;
// строим пирамиду
for(i = size / 2 - 1; i >= 0; --i)
downHeap(a, i, size-1);
// теперь a[0]...a[size-1] пирамида
for(i=size-1; i > 0; --i)
{
// меняем первый с последним
temp = a[i];
a[i] = a[0];
a[0] = temp;
// восстанавливаем пирамидальность a[0]...a[i-1]
downHeap(a, 0, i-1);
}
}
void main()
{
int key,size=10;
int *arr=new int [10];
cout<<"Vvesti massiv. Otsortirovat' massiv pri pomoshi algoritma\n";
cout<<"Piramidal'noy sortirivku.\n";
cout<<endl;
cout<<"Vibirite sposob vvoda:"<<endl;
cout<<endl;
cout<<"1 S klaviaturi"<<endl;
cout<<"2 Sluhaynie hisla"<<endl;
do{
cin>>key;
if(key==1||key==2) break;
else cout<<"Ne pravil'niy vvod. Povtorite."<<endl;
}while(1);
randomize();
switch(key){
case 1:
cout<<"Ishodnii massiv: "<<endl;
for (int i=0;i<10;i++)
{
cin>>arr[i];
if(cin.fail()){
do {
cout<<"Ne pravil'niy vvod. Povtorite."<<endl;
cin.clear();
cin.ignore();
cin>>arr[i];
}while(cin.fail());
}
}
cout<<endl;
break;
case 2:
cout<<"Sluchainii massiv: "<<endl;
for (int i=0;i<10;i++)
{
arr[i]=random(20)-10;
cout<<arr[i]<<" ";
}
cout<<endl;
break;
}
heapSort(arr, size);
cout<<endl<<"Utogoviy massiv: "<<endl;
for (int i=0; i < 10; i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
delete arr;
getch();
}