Отсортировать данные по какому-либо ключу(пирамидальная,гномья сортировка).

[ggjgj]

Помогите пожалуйста разобраться в сортировках, теории на занятиях не было,но дали шаблон:

#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<iomanip>
#include<cmath>
using namespace std;
 
 
ifstream in("input.txt");
ofstream out("output.txt");
 
struct date{//объявляем тип - структуру с датой 
     int dd, mm, yy;
};
 
struct people{//объявляем тип - структуру с данными о человеке
     string Surname; //фамилия
     date DateOfBirth; //дата рождения
     int Salary, Stag; //зарплата, стаж
};
 
date Str_to_Date(string str){//из строки в дату
     date x;
     string temp = str.substr(0, 2);//в temp записываем часть строки с днем из даты рождения (ДР)
     x.dd = atoi(temp.c_str());//переводим строку temp в число-день
     temp = str.substr(3, 2);//в temp записываем часть строки с месяцем из даты рождения (ДР)
     x.mm = atoi(temp.c_str());//переводим строку temp в число-месяц
     temp = str.substr(6, 4);//в temp записываем часть строки с годом из даты рождения (ДР)
     x.yy = atoi(temp.c_str()); //переводим строку temp в число-год
     return x;
}
 
vector<people> inFile(){//функция считывает из файла данные о людях и возвращает вектор из people в качестве результата
   vector<people> x;
   people temp;
   while(in.peek() != EOF){
     in >> temp.Surname;//считывается фамилия
     string tmp;//объявляем строку для считывания даты рождения
     in >> tmp;//считываем строку с датой рождения (ДР)
     temp.DateOfBirth = Str_to_Date(tmp); // переводим строку с ДР в структуру ДР
     in >> temp.Stag;//считываем стаж
     in >> temp.Salary;//считываем зарплату
     x.push_back(temp); //добавляем человека temp в вектор x
   }
   return x; // возвращаем вектор из людей как результат функции
}
 
void print(people x){//функция выводит данные о человеке х в файл
   out << setw(10) << left << x.Surname;// setw(10)- 10 позиций для фамилии, left - выравнивание по левому краю
     if (x.DateOfBirth.dd < 10) out << left << '0' << x.DateOfBirth.dd << '.';//если день в ДР <10, то добавляем 0, например, 02
     else out << left << x.DateOfBirth.dd << '.';
     if (x.DateOfBirth.mm < 10) out << '0' << x.DateOfBirth.mm << '.';//если месяц в ДР <10, то добавляем 0, например, 02
     else out << x.DateOfBirth.mm << '.';
     out << left << setw(6) << x.DateOfBirth.yy;//на год отводится 6 позиций, выравнивание по левому краю
     out << left << setw(4) << x.Stag ;
     out << left << setw(10) << x.Salary << endl;//на запрлату отводится 10 позиций, выравнивание по левому краю
}
 
bool operator < (people a, people b){//переопределяем оператор < для сравнения двух людей a и b в соотвествии с условием
     if (a.Surname < b.Surname) return true;
     if (a.Surname == b.Surname && a.DateOfBirth.yy < b.DateOfBirth.yy) return true;
     if (a.Surname == b.Surname && a.DateOfBirth.yy == b.DateOfBirth.yy && a.Salary < b .Salary) return true;
     return false;
}
 
 
void Select_sort(vector<people> &x)
//сортировка методом выбора
{
    int lowindex;
    for (int i = 0; i < x.size(); i++)
    {
        lowindex = i;
        for (int j = i + 1; j < x.size(); j++)
            if (x[j] < x[lowindex])
                lowindex = j;
        swap(x[lowindex], x[i]);
    }
 
}
int main(){
     vector<people> x;
     x = inFile();
     Select_sort(x);
     for(int i = 0; i < x.size(); i++)
         print(x[i]);
     return 0;
}

Задание.Отсортировать 1) по должности с помощью пирамидальной сортировки.
2)сначала по должности, потом по зарплате с помощью гномьей сортировки.

[Alex11223]

Так и чем помочь-то?

[ura_111]

На youtube видеоролики посмотри. Ну вот например:

https://www.youtube.com/watch?v=ew2MTOTbeNA

https://www.youtube.com/watch?v=cUg68Mw6Et8

https://www.youtube.com/watch?v=Lb6drAbXSF8

................................... ....
................................... ....
................................... ....

а потом спроектируешь знания на свой код.

[ggjgj]

К сожалению эта теория мне ничего не дает, я не понимаю сам алгоритм пирамидальной сортировки для моего задания. Может все таки кто-нибудь поможет отсортировать список по должности пирамидальной сортировкой.(у нас есть файл в котором содержатся данные о сотрудниках предприятия: фамилия, должность, дата
рождения (день, месяц, год), стаж работы, зарплата). Помогите,пожалуйста

[p51x]

А что в нем понимать? Есть четкий алгоритм и операции сравнения/перестановки элементов. Тупо записать подставив свои буковки из вики.

[ggjgj]

Я ничего не понимаю,использовать нужно как я поняла это алгоритм

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;

    };
}

Но как его спроектировать на шаблон который нам дал преподаватель я не понимаю, где у нас что есть что, и как еще вписать,чтобы в итоге это вообще работало. ПОМОГИТЕ

[ura_111]

Для начала разберись в методах:
- Select_sort
- SiftDown

В чём разница?
Как они работают?
Какие начальные переменные требуют?

p.s.: ты же хочешь менять один на другой...