Home > Back-end >  Trouble trying to quickSort an array of structs
Trouble trying to quickSort an array of structs

Time:03-02

I have to read a .txt file and save the words and the times they are written on the file in a array of structs. I tried looking on the internet to find a way to do that, but everything is about C .

Everything else seems to be working fine. The words are saved in the array with no problem, but the sort simply doesn't work.

The struct:

typedef struct
{
    char palavra[50]; // the word
    int ocorrencia; // times it's written
} dicionario;

My attempt of doing the quickSort:

void quickSort(dicionario tabela[], int inicio, int tamanho)
{
    
    int i = inicio, j = tamanho;
    int temp;
    int pivot = tabela[(i   j) / 2].ocorrencia;

    while(i<=j)
    {
        while(tabela[i].ocorrencia < pivot) i  ;
        while(tabela[j].ocorrencia > pivot) j--;
        if(i<=j)
        {
            temp = tabela[i].ocorrencia;
            tabela[i].ocorrencia = tabela[j].ocorrencia;
            tabela[j].ocorrencia = temp;
            i  ;
            j  ;
        }
    }

    if(inicio < j) quickSort(tabela,inicio,j);
    if(i < tamanho) quickSort(tabela,i,tamanho);

}

When I run the code, it just ends without returning anything, even when I try to print it all at the end.

CodePudding user response:

The wandbox example sorts an array of pointers to strings. You want to sort an array of structs, e.g. dicionario a[20]; on the .ocorrencia field. You call

qsort(a, 20, sizeof(dicionario), cmpdicionario);. Then use:

int cmpdicionario(const void *a, const void *b)
{
    // a and b are really pointers to structs.
    int ai = ((dicionario *)a)->ocorrencia;
    int bi = ((dicionario *)b)->ocorrencia;
    return (ai < bi) ? -1 : (ai > bi) ? 1 : 0;
}

Put the compare function before the call to qsort() to keep it simple.

If you don't have counts high enough to be concerned about overflow, you can just return ai - bi; but I recommend the above.

I haven't studied your quicksort much. It's a tricky thing to get right. If you need to code your own, you should closely follow a known good example. I will note that your j should be j--, and your swap should be swapping entire structs, not just the one field, since you want to keep the words associated with their counts. There may be other bugs.

Also, if you need to code your own sort, and you don't need high performance, use Shell sort. It's shorter and much easier to get right. And typically about 1/5 to 1/2 the speed of quicksort, usually fast enough. If it's less than maybe 50 elements and you don't need to run it often, insertion sort is fine and even simpler. Plus, insertion sort is "stable", that is, it will keep elements with equal counts in their original order. Probably not relevant here, but sometimes it's useful.

  • Related