3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ By defining an arbitrary ordering for the elements that don't appear, can't you get O(nlog(n)) using merge sort for instance? $\endgroup$ – GoodDeeds Feb 21 at 15:16
  • $\begingroup$ Perhaps you can count the number of occurrences of each of the ordering-strings in the input-array? $\endgroup$ – Hendrik Jan Feb 21 at 18:18
  • $\begingroup$ Is the ordering array negligibly short, or is it order $n$ in length? Practically, turning the ordering array into a hash table from strings to ordering, then using that to turn your input array into (ordering, string) pairs, then sorting on that first element, will be pretty good. $\endgroup$ – Daniel M Gessel Feb 21 at 22:33
  • 1
    $\begingroup$ Please provide a general specification of the problem. A single example is not a substitute for a specification of the problem. $\endgroup$ – D.W. Feb 22 at 0:00
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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