CODEWITHSUNDEEP
c
Sunny Lei
Sunny Lei

Reputation: 181

sort word in alphabet order in C

Below code is for a test sample given in https://www.testdome.com/for-developers/solve-question/9621

The question is: Implement function sort_words that can sort an array of words which contain lowercase characters from english alphabet, in descending order.

For example, the array { "cherry", "orange", "apple" } should, after sorting, become { "orange", "cherry", "apple" }.

My code is:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

void sort_words(char *words[], int count)
{
    char *x;

    for (int i = 0; i<count; i++)
    {
        for (int j = i + 1; j<count; j++)
        {
            if ((char)(*words[i]) < (char)(*words[j]))
            {
                x = words[j];
                words[j] = words[i];
                words[i] = x;
            }
        }

    }
}

#ifndef RunTests
int main()
{
    char *words[] = { "cherry", "orange", "apple" };

    sort_words(words, 3);

    for (int i = 0; i < 3; i++)
    {
        printf("%s ", words[i]);
    }
}
#endif

Result is correct, but the system notices the fail information "Performance test on a dictionary: Time limit exceeded"

Why this error happens and how to solve this problem? Thanks!

Upvotes: 3

Views: 13649

Answers (3)

xubo peng
xubo peng

Reputation: 1

You can use c standard library function qsort() to beat it.... My code as below:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int compare_c_str(const void * str1, const void * str2)
{

    return strcmp(*(char **)str2,*(char **)str1);
}

void sort_words(char *words[], int count)
{
    // Waiting to be implemented
    qsort(words,count, sizeof(words[0]),compare_c_str);
}

#ifndef RunTests
int main()
{
    char *words[] = { "cherry", "orange", "apple" };

    sort_words(words, 3);

    for (int i = 0; i < 3; i++)
    {
        printf("%s ", words[i]);
    }
}
#endif

Upvotes: 0

NVS Abhilash
NVS Abhilash

Reputation: 577

The above code looks working, but it is actually wrong.

If the input set is:

char *words[] = { "cherry", "orange", "apple", "oyster"};

Then the output is:

orange oyster cherry apple

But the expected output is:

oyster orange cherry apple

The reason for that is in your sorting algorithm this condition:

if ((char)(*words[i]) < (char)(*words[j]))

Is basically just comparing the first letters of the two character arrays.

NOTE: This is not C++ and the data is not stored in string data type in C++. Where the < operator is overloaded to compare two strings.

Hence, instead of that line, you can use the strcmp(), like this:

if (strcmp(words[i], words[j]) < 0)

Here is your working code:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

void sort_words(char *words[], int count)
{
    char *x;

    for (int i = 0; i<count; i++)
    {
        for (int j = i + 1; j<count; j++)
        {
            if (strcmp(words[i], words[j]) < 0)
            {
                x = words[j];
                words[j] = words[i];
                words[i] = x;
            }
        }

    }
}

#ifndef RunTests
int main()
{
    char *words[] = { "cherry", "orange", "apple", "oyester"};

    sort_words(words, 4);

    for (int i = 0; i < 4; i++)
    {
        printf("%s ", words[i]);
    }
    printf ("\n");
}
#endif

Output:

oyester orange cherry apple

Upvotes: 3

Rajeev Ranjan
Rajeev Ranjan

Reputation: 4076

This is because the algorithm you are using is not efficient in terms of time complexity. The on eyou use is very trivial. It would no doubt sort the input, but would incur a lot of time when the input data set is huge. Try using some other sorting algorithm like - mergesort, quicksort, etc. These will do the same work in lesser time. Refer how these algorithms work and try implementing them - https://www.tutorialspoint.com/data_structures_algorithms/sorting_algorithms.htm

Upvotes: 3

Related Questions