Print all anagrams together
Many a times we need to sort some things which are not integers, foremost being strings. How do we go about using quick sort. I did not know that C library has a function for it. This function is very powerful and easily sort anything given the compare function. So in today’s post we will be using that function and learn how it can be used to solve our problem statement.
Given a list of words, group all words together which are anagrams. For example, if input is like :
Now the problem boils down to sorting each individual string and then sort the entire array of strings. The anagram strings will automatically will grouped together.
If we look closely, we have another problem, that is when we sort the original strings individually, original strings are lost. So, idea is to have a duplicate array of strings and then sorting operation. Also to after sorting the duplicate array, we will loose the original index of string once we sort the entire array. Hence we need to store that information too.
Let’s figure what we need to store and how?
We have array of strings, let’s say there can be maximum 100 such strings.
So we create and array of character pointers to store these strings.
Also, we need a duplicate array where we will sort strings and also we need to store the position of the string in original array so, duplicate array would look like:
Next step is to sort individual string in duplicate array, where we will use the library function qsort().
This function is very easy to use, there are four parameters you have to pass:
1. The buffer or the array you want to have sorting performed on.
2. The size of buffer
3. Size of individual element of buffer.
4. And last and most important is the compare function, which has to be written in code and passed as function pointer to this function.
For further details of qsort() function usage follow : qsort
Once all the strings are individually sorted, sort the entire array of strings using the same qsort(), only difference will be the compare function which will now run on entire string instead of character.
We are almost done! Now we have all anagrams placed next to each other, however, we need to print original words. That’s where the index we stored in duplicate array will help and we will print words from original array using the order given in duplicate array.