How to sort array structures based on the rank of the songs?

Asked

Viewed 362 times

1

The rank of the code ta going in ascending order but the others do not change the positions along with the rank, as I do for the positions of the songs and styles 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);
}
}

1 answer

4


The problem is in swap values of the vector, which only rank of each element to be ordered. In order for the exchange to be done as a whole, you can exchange 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 because each time it assigns one structure to another:

temp = a[i];

Forces the copy of all bytes from one element to another.

Using pointers

If the amount of music grows a little the efficiency of the ordering can be called into question due to 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 only modifying the pointer without having to copy the bytes all between elements.

This has implications as it makes it necessary to change the way the vector is being used in the rest of the program, just as it implies allocating the songs 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 sorting efficiency in a serious way you should change the sorting algorithm you are using, in this case the Bubblesort, by a more efficient as for example the Quicksort.

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

Example of implementation:

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 on the main just need to call the function by crossing the sorting limits:

quicksort(a, 0, 3);

See also this example in Ideone

Ordering with qsort

In fact C itself already has ordination functions, one of them being the qsort. Although the name suggests the quicksort algorithm the specification does not indicate that the algorithm has to be the one used, which gives room for different implementations. Typically implementations tend to algorithms with O(nlogn) complexity that give quicksort-level efficiency.

To use the qsort must first construct a comparison function of the 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 for each element of the vector. If each element is a Musica* and so a pointer already, the parameters will be Musica**, or pointers to pointers.

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

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

These parameters are:

  • a - array to order
  • 4 - quantity of items to be sorted
  • sizeof(Musica*) - size of each element
  • compararMusicas comparison function of elements

See this last example in Ideone

Browser other questions tagged

You are not signed in. Login or sign up in order to post.