could you help me please . How do I order this struct by short Insert method?

Question

How do I sort the struct using the short Insert I’m new to programming if you can help me please and explain , I’ll send the code I did :

#include <iostream>

using namespace std;


struct Familia {

    int IdadePai;
    int IdadeMae;
    int IdadeFilho;

};


void insertion_sort( Familia  lista [], int  tam ){

    int  valor_pivo;
    int aux ; 
    int j;
    int posPivo ;

    for (int i = 1; i < tam ; i++) {

     valor_pivo = lista [i].IdadePai;
     posPivo = i ;
     j = i - 1;

     while ((j >= 0) and (valor_pivo < lista [j].IdadePai)){

        aux = lista [j].IdadePai;
        lista [j] = lista[posPivo].IdadePai;
        lista[posPivo].IdadePai = aux ;

        aux = lista [j].IdadeMae;
        lista [j] = lista[posPivo].IdadeMae;
        lista[posPivo].IdadeMae = aux ;

        aux = lista [j].IdadeMae;
        lista [j].IdadeMae = lista[posPivo].IdadeMae;
        lista[posPivo].IdadeMae = aux ;

         j--;

     }

        aux = lista [j].IdadePai;
        lista [j] = lista[posPivo].IdadePai;
        lista[posPivo].IdadePai = aux ;

        aux = lista [j].IdadeMae;
        lista [j] = lista[posPivo].IdadeMae;
        lista[posPivo].IdadeMae = aux ;

        aux = lista [j].IdadeMae;
        lista [j].IdadeMae = lista[posPivo].IdadeMae;
        lista[posPivo].IdadeMae = aux ;


    }

}

int main(){

    Familia lista [5];
    bool igual = false ;

    for (int i = 0; i < 5 ; i++){

        cin  >> lista[i].IdadePai;
        cin  >> lista[i].IdadeMae;
        cin  >> lista[i].IdadeFilho;

    }

   insertion_sort( lista , 5);


    for (int j = 0 ; j < 5; j++){

        for (int k = j ; k < 5; k ++){

                if (lista[j].IdadeFilho == lista[k].IdadeFilho ){

                    cout << lista[j].IdadePai << "  " ;
                    cout <<  lista[j].IdadeMae << "  " ;

            igual = true ;

        }else {

            igual = false ; 

        }

        }

    }



    if( igual == false ){

        cout  << -1 ;


    } 


    return 0;
}

Answer 1

Defined by the name, Insertion Sort is an algorithm that sorts a container automatically during insertion. It is useful when every new insertion needs the container to be sorted, in situations where there is a justifiable performance gain such as a list where binary searches are more frequent than insertions.

Your code doesn’t make much sense because you get the user input, add it to the array without the Insertion Sort and then try to sort the container from the outside. This is not efficient, pq to use the Insertion Sort in this situation it is necessary to recopy the integer vector and go inserting the values one by one in the new ordered vector. An algorithm like Quicksort would be a better choice.

#include <iostream>
using namespace std;

struct Familia
{
    unsigned int IdadePai;
    unsigned int IdadeMae;
    unsigned int IdadeFilho;
};

void insertion_sort(Familia novo_item, Familia lista[], int tam)
{
    int posicao_item = -1;

    //encontrar posição de inserção
    for(int i=0; i<tam; i++) {
        if(novo_item.IdadePai < lista[i].IdadePai ) {
            posicao_item = i;
            break;
        }
    }

    //se novo item não for menor que nenhum dos itens na lista, não inserir
    if(posicao_item == -1)
        return;

    //de trás pra frente, empurre itens depois de posição para o final
    for(int i=(tam-1); i>posicao_item; i--) {
        lista[i] = lista[i-1];
    }

    //inserir item na posição
    lista[posicao_item] = novo_item;
}

#define INF 0xFFFFFFFF

int main()
{
    //entrada
    const Familia familia[5] = {{ 2, 2, 2 },
                                { 3, 3, 3 },
                                { 1, 1, 1 },
                                { 5, 5, 5 },
                                { 4, 4, 4 }};

    //lista vazia
    Familia familia_ordenada[5] = {{ INF, INF, INF },
                                   { INF, INF, INF },
                                   { INF, INF, INF },
                                   { INF, INF, INF },
                                   { INF, INF, INF }};

    //adicionando e ordenando itens com insertion sort
    for (int i = 0; i < 5; i++) {
        cout << "\nPasse: " << i+1 << "\n";
        insertion_sort(familia[i], familia_ordenada, 5);

        for (int i = 0; i < 5; i++) {
            cout << " { "   << familia_ordenada[i].IdadePai   << ", "
                            << familia_ordenada[i].IdadeMae   << ", "
                            << familia_ordenada[i].IdadeFilho << " }\n";
        }
    }

    return 0;
}

Passe: 1
 { 2, 2, 2 }
 { 4294967295, 4294967295, 4294967295 }
 { 4294967295, 4294967295, 4294967295 }
 { 4294967295, 4294967295, 4294967295 }
 { 4294967295, 4294967295, 4294967295 }

Passe: 2
 { 2, 2, 2 }
 { 3, 3, 3 }
 { 4294967295, 4294967295, 4294967295 }
 { 4294967295, 4294967295, 4294967295 }
 { 4294967295, 4294967295, 4294967295 }

Passe: 3
 { 1, 1, 1 }
 { 2, 2, 2 }
 { 3, 3, 3 }
 { 4294967295, 4294967295, 4294967295 }
 { 4294967295, 4294967295, 4294967295 }

Passe: 4
 { 1, 1, 1 }
 { 2, 2, 2 }
 { 3, 3, 3 }
 { 5, 5, 5 }
 { 4294967295, 4294967295, 4294967295 }

Passe: 5
 { 1, 1, 1 }
 { 2, 2, 2 }
 { 3, 3, 3 }
 { 4, 4, 4 }
 { 5, 5, 5 }

I rewrote your code to make the implementation of Insertion Sort clearer and to have a better reference of how to use the algorithm. Good luck in your studies.