Answer the question
In order to leave comments, you need to log in
How to properly sort an array with heap method and select method?
1) how to make in this program so that what I entered in vvod () was available for the rest of the points
2) how to solve this problem: there are no instances of the "HeapSort" function template, corresponding to the argument list, argument types: (, )
#include "stdafx.h"
#include "iostream"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
int vvod(){
printf("Сколько элементов будет в массиве? ");
//cout << "Введите размер массива" << endl;
int p = 0; //количество элементов
int i = 0;
int j = 0;
int temp;
scanf_s("%d", &p);
//cin >> p;
int arr[100];
arr[100] = arr[p];
//ввод элементов
for (i = 0; i < p; i++){
printf("Введите %d элемент: ", i);
//cout << "Введите " << i << " элемент: \n";
scanf_s("%d", arr + i);
}
}
template<class T> void SiftDown(T* const heap, int i, int const n)
{ //Просеивает элемент номер i вниз в пирамиде heap.
//n -- размер пирамиды
//Идея в том, что вычисляется максимальный элемент из трёх:
// 1) текущий элемент
// 2) левый потомок
// 3) правый потомок
//Если индекс текущего элемента не равен индексу максималь-
// ного, то меняю их местами, и перехожу к максимальному
//Индекс максимального элемента в текущей тройке элементов:
int nMax(i);
//Значение текущего элемента (не меняется):
T const value(heap[i]);
while (true)
{ //Рассматривается элемент i и его потомки i*2+1 и i*2+2
//В начале каждой итерации nMax == i и value == heap[i]
int childN(i * 2 + 1); //Индекс левого потомка
//Если есть левый потомок и он больше текущего элемента,
if ((childN < n) && (heap[childN] > value))
nMax = childN; // то он считается максимальным
++childN; //Индекс правого потомка
//Если есть правый потомок и он больше максимального,
if ((childN < n) && (heap[childN] > heap[nMax]))
nMax = childN; // то он считается максимальным
//Если текущий элемент является максимальным из трёх
// (т.е. если он больше своих детей), то конец:
if (nMax == i) break;
//Меняю местами текущий элемент с максимальным:
heap[i] = heap[nMax]; heap[nMax] = value;
// при этом значение value будет в ячейке nMax,
// поэтому в начале следующей итерации значение value
// правильно, т.к. мы переходим именно к этой ячейке
//Переходим к изменившемуся потомку
i = nMax;
};
}
template<class T> void HeapSort(T* const heap, int n)
{ //Пирамидальная сортировка массива heap.
// n -- размер массива
//Этап 1: построение пирамиды из массива
for (int i(n / 2 - 1); i >= 0; --i) SiftDown(heap, i, n);
//Этап 2: сортировка с помощью пирамиды.
// Здесь под «n» понимается размер пирамиды
while (n > 1) //Пока в пирамиде больше одного элемента
{
--n; //Отделяю последний элемент
//Меняю местами корневой элемент и отделённый:
T const firstElem(heap[0]);
heap[0] = heap[n];
heap[n] = firstElem;
//Просеиваю новый корневой элемент:
SiftDown(heap, 0, n);
}
}
void piramid() {
HeapSort(arr, p);
//printf("[");
cout << "[ ";
for (int i = 0; i < p; ++i)
//printf("%d", arr + i);
cout << arr[i] << " ";
//printf("]");
cout << "]" << endl;
system("pause");
}
int Vibor(){
for (i = 0; i < p; i++)
{
for (j = p - 1; j >= i; j--)
if (arr[j - 1] > arr[j])
{
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
for (i = 0; i < p; i++)
{
printf("%d", arr[i]);
//cout << a[i] << " ";
}
}
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(LC_ALL, "Russian");
printf("-----Сделайте выбор-----\n");
printf("1. Ввод массива с клавиатуры\n");
printf("2. Считывание массива с файла(input.txt)\n");
printf("3. Сортировка массива пирамидальным методом\n");
printf("4. Сортировка массива методом выбора\n");
printf("5. Записать результат в файл (output.txt)\n");
printf("6. Выход из программы\n");
printf("Ваш выбор: ");
int input;
scanf_s("%d", &input);
switch (input) {
case 1: vvod();
break;
/*case 2:
{
}*/
case 3:
{
printf("3. Сортировка массива пирамидальным методом\n");
piramid();
break;
}
case 4:
{
printf("4. Сортировка массива методом выбора\n");
Vibor();
break;
}
/*case 5:{
}
*/
case 6: {
printf("До свидания");
break;
}
default:
printf("Неправильный ввод.\n");
}
return 0;
}
Answer the question
In order to leave comments, you need to log in
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question