CODEWITHSUNDEEP
algorithmdata-structures
abeer00
abeer00

Reputation: 53

Tries for sorting strings in linear time?

I am trying to sort strings alphabetically in linear time and thought about using tries for this, my question is What's the time complexity of running a Pre-Order transversal on tries? is it O(n) ?

Upvotes: 0

Views: 683

Answers (3)

Matt Timmermans
Matt Timmermans

Reputation: 59368

You have to be a little careful with the way you measure complexity in this case. A lot of times, people pretend that sorting N strings with a comparison-based sort takes O(N log N) time, but that is not really true in the worst case unless the length of the strings is bounded. It is the expected time if the strings are randomized, however, so it's not a bad approximation for many use cases.

If you want to account for possible long strings with long common prefixes, then you change the meaning of N to refer to the total size of the input, including all the strings. With this new definition, you can sort a list of strings in O(N) time.

Inserting the strings into a trie, or better a radix tree (https://en.wikipedia.org/wiki/Radix_tree) and then doing a preorder traversal is one way, and yes that works in O(N) time, where N is the total size of the input.

But it's faster and easier to do a radix sort: https://en.wikipedia.org/wiki/Radix_sort The Most-Significant-Digit-First variant works best with variable-length inputs.

Upvotes: 1

Idan
Idan

Reputation: 23

No. it is not O(n). it is Omega(k(log(k))n). without any other restriction,and this is the case as i understand from your question, it is just comparison based sorting algorithm. Sorting an array of length k is in Omega(klog(k)), and doing it n times, without any connections between the times, will lead to Omega(klog(k)n). You can read more here: https://www.geeksforgeeks.org/lower-bound-on-comparison-based-sorting-algorithms/

If you look at k as bounded, because there is no ENGLISH word longer then 10^1000000 (Which probably larger than atoms on Earth), then sort an array of bounded length is in O(1), and doing it n time will lead to O(n).

You get a lot from dealing with infinity, but sometimes you have to pay back...

Upvotes: 0

abeer00
abeer00

Reputation: 53

Radix Sort can be applied in this case to sort them in O(n) refer to the following code implemented in c++:

#include<iostream>

using namespace std;

class RadixSort {
    public:

        static char charAt(string s,int n){
            return s[n];
        }

        static void countingSort(string arr[],int n,int index,char lower,char upper){
            int countArray[(upper-lower)+2];
            string tempArray[n];

            for(int i =0; i < sizeof(countArray)/sizeof(countArray[0]); i++)
                countArray[i]=0;

            //increase count for char at index
            for(int i=0;i<n;i++){
                int charIndex = (arr[i].length()-1 < index) ? 0 : (charAt(arr[i],index) - lower+1);
                countArray[charIndex]++;
            }

            //sum up countArray;countArray will hold last index for the char at each strings index
            for(int i=1;i<sizeof(countArray)/sizeof(countArray[0]);i++){
                countArray[i] += countArray[i-1];
            }

            for(int i=n-1;i>=0;i--){
                int charIndex = (arr[i].length()-1 < index) ? 0 : (charAt(arr[i],index) - lower+1);
                tempArray[countArray[charIndex]-1] = arr[i];
                countArray[charIndex]--;
            }

            for(int i=0;i<sizeof(tempArray)/sizeof(tempArray[0]);i++){
                arr[i] = tempArray[i];   
            }
        }

        static void radixSort(string arr[],int n,char lower,char upper){
            int maxIndex = 0;
            for(int i=0;i<n;i++){
                if(arr[i].length()-1 > maxIndex){
                maxIndex = arr[i].length()-1;
                }
            }

            for(int i=maxIndex;i>=0;i--){
                countingSort(arr,n,i,lower,upper);
            }
        }
};


int main(){

    string arr[] = {"a", "aa", "aaa","kinga", "bishoy","computer","az"};
    int n = sizeof(arr)/sizeof(arr[0]);
    RadixSort::radixSort(arr,n,'a','z');
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }

    return 0;
}

Upvotes: 0

Related Questions