How to sort array structures based on song rank?

1

The rank of the code is going in increasing order but the others do not change the positions along with the rank, how do I position the songs and styles to go along with the code?

#include <stdio.h>
#include <locale.h>

struct musica{
char nome[100];
char estilo[100];
int rank;
};

typedef struct musica Musica;

int main (void){
int i,j,aux;
Musica a[8];

setlocale(LC_ALL, "Portuguese");

for (i=0; i<4; i++){

    printf ("Nome da música: ");
    gets (a[i].nome);

    printf ("Estilo musical: ");
    gets (a[i].estilo);

    printf ("Ranking da música: ");
    scanf ("%d",&a[i].rank);

    printf ("\n\n");

    getchar();
}
//RANKING DIGITADO DESORDENADO
for (i=0; i<4; i++){
    printf ("RANK %d\t%s\t%s\t\n", a[i].rank, a[i].nome, a[i].estilo);
}
    for (i=0; i<4; i++){
        for (j=i+1; j<8; j++){
            if (a[i].rank > a[j].rank){
                aux = a[i].rank;
                a[i].rank = a[j].rank;
                a[j].rank = aux;
                }
            }
        }
printf ("\n");
//RANKING ORDEM
for (i=0; i<4; i++){
    printf ("RANK %d\t%s\t%s\t\n", a[i].rank, a[i].nome, a[i].estilo);
}
}
    
asked by anonymous 08.11.2017 / 23:56

1 answer

4

The problem is in the swap of vector values, which only changes the rank of each element to sort. For the exchange to be made as a whole, you can switch between elements of the structure directly:

Musica temp; //variável temporária para troca do tipo Musica

for (i=0; i<4; i++) {
    for (j=i+1; j<4; j++) {
        //--------^ 4 e não 8
        if (a[i].rank > a[j].rank) {
            //trocas agora todas feitas com a variável temp
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}

Example working on Ideone

Although already working this solution is quite weak in efficiency since each time you assign one structure to another:

temp = a[i];

Requires copying all bytes from one element to another.

Using pointers

If the amount of music grows a bit, the efficiency of the ordering can be called into question because of the excessive amount of copies made in memory. One of the several points of resolution of this problem is the use of pointers, as it can make the exchange between elements just by modifying the pointer without having to copy the all bytes between elements.

This has implications because it makes it necessary to change the way the vector is being used in the rest of the program, as it implies allocating the music dynamically with malloc :

int main (void) {
    int i,j;
    Musica *a[8]; //vetor de ponteiros

    setlocale(LC_ALL, "Portuguese");

    for (i=0; i<4; i++) {
        a[i] = malloc(sizeof(Musica)); //criação do elemento da estrutura
        printf ("Nome da música: ");
        gets (a[i]->nome); //acesso com -> por partir de ponteiro

        printf ("Estilo musical: ");
        gets (a[i]->estilo); //acesso com -> por partir de ponteiro

        printf ("Ranking da música: ");
        scanf ("%d",&(a[i]->rank)); //acesso com -> por partir de ponteiro

        printf ("\n\n"); 
        getchar();
    }

    //RANKING DIGITADO DESORDENADO
    for (i=0; i<4; i++) {
        printf ("RANK %d\t%s\t%s\t\n", a[i]->rank, a[i]->nome, a[i]->estilo);
        //---------------------------------^-----------^-----------^
    }

    Musica *temp; //agora cada elemento é um ponteiro

    for (i=0; i<4; i++) {
        for (j=i+1; j<4; j++) {
            if (a[i]->rank > a[j]->rank) {
                //agora estas trocas são trocas de ponteiros, apenas indicando que
                //estão a apontar para elementos diferentes
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    printf ("\n");
    //RANKING ORDEM
    for (i=0; i<4; i++) {
        printf ("RANK %d\t%s\t%s\t\n", a[i]->rank, a[i]->nome, a[i]->estilo);
    }
}

See also this example in Ideone

Quicksort

If you want to consider ordering efficiently in a serious way, you should change the sorting algorithm you are using, in this case Bubblesort , to a more efficient one such as Quicksort .

For Quicksort there will be a main sort function that divides the array into two parts and orders each sub-part recursively using the same function. The element where it divides is called the pivot and the lower elements are placed to the left of it and the upper ones to the right. This process is called partitioning.

Implementation example:

int particao(Musica *musicas[], int baixo, int alto){
    Musica *pivot = musicas[baixo], *temp;
    int i = baixo - 1, j = alto + 1;

    while (1){
        do { i = i + 1; } while (musicas[i]->rank < pivot->rank);
        do { j = j - 1; } while (musicas[j]->rank > pivot->rank);

        if (i >= j) return j;

        temp = musicas[i];
        musicas[i] = musicas[j];
        musicas[j] = temp;
    }
}

void quicksort(Musica *musicas[], int baixo, int alto){
    if (baixo < alto){
        int pivot = particao(musicas, baixo, alto);
        quicksort(musicas, baixo, pivot);
        quicksort(musicas, pivot+1, alto);
    }
}

Now in main you just need to call the function by passing the sort limits:

quicksort(a, 0, 3);

See this example on Ideone

Sorting with qsort

In fact, C itself already has sorting functions, one of which is qsort . Although the name suggests the quicksort algorithm the specification does not indicate that it has to be the algorithm used, which gives scope for different implementations. Usually implementations tend to algorithms with complexity of O (nlogn) that give efficiency at the level of quicksort.

To use qsort you must first construct a function to compare elements:

int compararMusicas(const void* musica1, const void* musica2){
    Musica* m1 = *((Musica**)musica1);
    Musica* m2 = *((Musica**)musica2);

    return m1->rank-m2->rank;
}

The comparison function receives as a parameter a pointer to each vector element. If each element is a Musica* and therefore a pointer already, the parameters will be Musica** , ie pointers to pointers.

Having this function, just call qsort with the correct parameters:

qsort(a, 4, sizeof(Musica*), compararMusicas);

These parameters are:

  • a - array to sort
  • 4 - number of items to sort
  • sizeof(Musica*) - size of each element
  • compararMusicas element comparison function

See this last example on Ideone

    
09.11.2017 / 00:54