A
A
Andrey Novak2015-03-20 14:30:40
C++ / C#
Andrey Novak, 2015-03-20 14:30:40

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 question

Ask a Question

731 491 924 answers to any question