CODEWITHSUNDEEP
arraysalgorithmsortingcomplexity-theory
Andreas
Andreas

Reputation: 3

2 keys search algorithm in O(n)

i have to find an algorithm to sort an array in O(n) complexity. The array has the length n with two different keys.

For example this array in java:

int[][] array = {{1,2},{2,1},{1,1}};

The result should be

1 1
1 2
2 1

I struggle with solving this problem..

Who might be able to help me?

Thanks in advance

Upvotes: 0

Views: 120

Answers (1)

Khaled.K
Khaled.K

Reputation: 5940

If your data is stored in a Trie, then a DFT (Depth First Traversal) will show you how your trie is actually Radix-sorted by definition.

If you've build the Trie, and all sub-sets have the same number of elements, then leaves of the trie are the subsets in order, where the depth of leaves is number of elements per sub-set.

Using a Trie, you have O(m) where m = number of sub-sets

Or you can try a Radix Sort, where you have Ω(n * m) where n = size of a sub-set

..hope this helps

Upvotes: 1

Related Questions