I did some quick research on Google and Wikipedia to find some more information on sorting methods and isogram lengths. The maximum known English isogram is seventeen letters (subdermatoglyphic if you are curious.)
Using this knowledge we can assume any word with a length greater than seventeen letters is not an isogram, and can begin to sort if it is between two and seventeen letters in length.
Moving forward we must sort the hidden words letters and compare them, and depending on the sorting method used we can achieve a speed of O(n) but at worst case we would fall back to O(n log n). (see timsort and librarysort as examples of this.)
so we now would have something like
if (Guess.length() < 2 || Guess.length() > 17 || !IsIsogram(FString Guess)) { return EGuessStatus::Not_Isogram; }
in our CheckGuessValidity class.
Then the call for IsIsogram() would sort the letters by a sorting method that is undefined yet, but if we utilized something as simple as bubble sort it would be O(n^2), or something more complex like timsort/librarysort would yield O(n log n) to hopefully O(n) operations. Why?
-
Bubble sort would be an array where the array length is = to Guess.length() and would run through a do-while loop till the end of the word is reached (or a duplicate letter is found) , where each time a letter is found to be earlier in the alphabet than the current one, it would move the new letter to the front and shift every letter in the array up one. if the guess was an isogram and happened to be completely alphabetically backwards it would result in up to 136 operations for a 17 letter theoretical alphabetically backwards isogram being sorted to alphabetically forwards. (16 comparisons in the first run, 15,14,13,12,11,10,9,8,7,6,5,4,3,2,1 = 136) and that is without checking if the letter is the same so there is another 16 operations there bringing it to 152. as we can see this one quickly approaches the O(n^2) speed and is inefficient.
-
Timsort / Librarysort would achieve a better performance through utilizing blocks of letters instead of individual ones and hopefully achieve O(n), but most likely fall back to O(n log n) if the data was not already sorted or reverse sorted.
I think I got a handle on the concept, I just need to learn more about how to implement the code. If anyone see’s any errors in my understanding please let me know, and thanks for reading.