Sorting array of strings (with repetitions) according to a given ordering

Question

We get two arrays:

ordering = ["one", "two", "three"]

and

input = ["zero", "one", "two", "two", "three", "three", "three", "four"];

We want to find the array output so that

output = ["one", "two", "two", "three", "three", "three", "zero", "four"]
// or
output = ["one", "two", "two", "three", "three", "three", "four", "zero"]

The strings (with possible repetitions) should be sorted as in the ordering array. Not found/contained strings should be put at the end of the new array and their order doesn't matter.

The $n^{2}$ solution is obvious, can we do better? The memory doesn't matter and it doesn't have to be an in-place algorithm.

Answer 1

The other answers provide correct solutions. However, you can do a bit better considering multivariate complexity. Note that the provided running times in the other answers are not quite specific since they ignore either the size of the first array or the lengths of the strings.

Here are 2 different methods with their specific running times. The first of which is a brief description of the method in the other answers with specific analysis of the running time. The second of which has better running time and is almost optimal.

Let us call the first (ordered) list in the input $A$ and the second (to be ordered) $S$. Let $n$ be the size of $A$ and $m$ the size of $S$. Let $l$ be the maximum length of a string in the input.

The first method. This span the methods in the other answers. Note that in both we need to find for each string the whether it lays in the original ordered array and if so at what position exactly. We need either apply a linear search which will cost something like $O(ml)$ per element or we can build some kind of a dictionary data-structure such as search trees and hashing tables or a "trie" (prefix-tree) data structure to achieve each look-up operation in linear time in the size of the strings. Using this we can achieve a running time of $O((m+n)l)$ for finding the positions over all strings. Afterwards we need to sort all strings in $O(n \log n)$ if we assign the indices directly to the strings (using pairs) or $O(l n \log n)$ by applying the look-ups while searching. So the best running time we can achieve using the methods in the other answers would be $O(l (n+m) + n \log n)$.

---

The second method. Note that we did not make use of the original sorted array and that is why we had to sort the strings again. We can solve the problem more efficiently by using this extra informaiton. To achieve this, let us bild a dictionary $D$ (for the sake of the theoretical bounds let us define it as a trie but in you can implement it as a hash-table as well). Let us define a new list $L$ (a linked list) and a function $C$ that counts how many times each string appeared in the first array. Assume $D$ assigns to each string a distinct number from $1$ to $m$ and $C$ is an array of length $m$. The algorithm goes as follow:

For all i in {1, .., m}
 Set C[i] := 0
// Now build D
Set index := 0
For each string s in A do
 Set D[s] = index
 Increase index by one
// Now find how many times each string occurs
Let L be an empty list
For each string s in S do
 If s in D then
  Find index = D[s]
  Increase C[index] by one
 Else
  Append s to L
//Now output
For each string s in S do
 Find index := D[s]
 Find c := C[index]
 while c > 0
  output s
  decrease c by one
For s in L
 output s

This algorithm runs in $O(l(n+m)$ which is linear (optimal) if the lengths of the strings are bounded by a constant.

Answer 2

I think a straightforward way to accomplish this would be to create a mapping of every element in your ordering list to its index i.e. order["three"] = 3. Then your comparator for sorting two objects a and b in the input is order[a] <= order[b]

This way, you can easily abstract the pairwise comparisons. For example both Python and C++ (and probably many others) allow you to provide comparators/keys for sorting.

Answer 3

Assuming the length of both arrays in your question is $\mathcal{O}(n)$, then in terms of required string comparisons:

Create an array of the form inverse = [("one", 1), ("two", 2), ("three", 3)] where the additional indices are the array indices and sort it lexicographically on the first pair elements. This can be done in $\mathcal{O}(n \ln n)$ string comparisons with common sorting algorithms.

Then, define a lookup of a string in inverse as lexicographical binary search on the first pair element and returning the corresponding second element, or the length of the array plus 1 if the string isn't found. This takes $\mathcal{O}(\ln n)$ string comparisons per lookup.

Then, for each element in output lookup the corresponding index from inverse as described above, taking $\mathcal{O}(n\ln n)$ string comparisons.

The resulting array can be sorted by any common sorting algorithm, which can be done in $\mathcal{O}(n \ln n)$ integer comparisons.

Afterwards transform the indices back to the strings by directly indexing into ordering. This takes $\mathcal{O}(n)$.

This algorithm will then be dominated by $\mathcal{O}(n \ln n)$ string comparisons. The time required for a string comparison will be worst-case proportional to the maximum length of strings involved, so the total time must be multiplied by a factor of that to obtain an upper bound.