1
$\begingroup$

I have $N$ sequences of numbers. None of them is longer than $10^6$. I want to sort those sequences lexicographically. For example, given sequences {1, 2, 4}, {1, 2, 3}, {2, 5, 7}, {2}, I want to have them sorted in this way - {1, 2, 3}, {1, 2, 4}, {2}, {2, 5, 7}. What is the fastest way to do this? Using quicksort and just comparing them in a normal way I can get $O(N∗K∗logN)$ but this is very slow.

$\endgroup$
10
  • 1
    $\begingroup$ What is $K$ in your big O? $\endgroup$
    – Wojowu
    Nov 2, 2015 at 8:32
  • $\begingroup$ It is the length of the longest sequence. In example above K = 3, because length of the longest sequence is 3. $\endgroup$ Nov 2, 2015 at 8:47
  • $\begingroup$ Since you are assuming that $K\leq 10^6$, you don't need to include it in the big O. $\endgroup$
    – Wojowu
    Nov 2, 2015 at 8:49
  • $\begingroup$ Does it happen often that long initial sequences of two of your sequences are equal? $\endgroup$
    – Stefan Kohl
    Nov 2, 2015 at 9:20
  • 1
    $\begingroup$ This looks like it is from a programming competition. $\endgroup$ Nov 2, 2015 at 15:12

1 Answer 1

1
$\begingroup$

Let $S$ be your set of sequences.

We construct increasingly refined partitions of $S$, where each class in the partition is associated to a node of a tree. Initially, the partition consists of one class (the entirety of $S$), and the tree consists of one node (the root). In your example, the initial state would look like this:

Initial state

If there is a node $N$ in layer $\ell$ (where the root node is layer $0$) with more than one sequence associated to it, we create child nodes for each distinct symbol $\sigma$ occurring in the $(\ell + 1)$th position of any of the sequences, and move the sequences accordingly:

State after first operation

We repeat again for each of the other nodes, since they both have more than one associated sequence. Since the sequence $(2)$ does not have a second element, we leave it where it is. After both of these operations, the tree looks like this:

State after second and third operations

There is only one node remaining with more than one associated sequence. It's in the second layer, so we compare the third elements of the sequences. The tree then becomes this, at which point we terminate since all nodes have at most one associated sequence:

Final state of tree

Now we can just do a preorder traversal of this tree, which takes time linear in the tree size.

Note that in the worst-case scenario this algorithm takes at linear time in the input size, $O(KN)$. Moreover, it is often considerably faster ($\Theta(N \log N)$ for random sequences) since it does not have to read the entire input -- in the example given, it never needs to read the symbol $7$ in the sequence $(2, 5, 7)$.

Indeed, I claim optimality of this algorithm, since it reads the minimum number of symbols required to distinguish between all of the sequences, and the time complexity is proportional to that quantity.

$\endgroup$
2
  • 1
    $\begingroup$ This is how radix sorts for mixed length strings. The time $O(KN)$ assumes you can sort a set of integers in linear time, which is true if only a constant number of integers can occur but isn't true in general. If the sets all have a single element but they can be arbitrary integers, you need $O(N\log N)$. $\endgroup$ Nov 2, 2015 at 10:20
  • 2
    $\begingroup$ Relevant keyword: "trie". It's worth noting that this is not only good for sorting them, but for storing them as well, depending on the actual data and data structures. $\endgroup$
    – user13113
    Nov 2, 2015 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.