-1
$\begingroup$

Introduction

Hi everyone,

I am currently pondering how to efficiently design an algorithm for a sorting problem and hope that someone here may help me out a bit.

The problem

I have two lists of integers, let's call them the 'input' list and the 'position' list, and want to sort the 'input' list based on the position of each 'integer' in the position list. Which algorithm could I use to achieve this in the most efficient manner possible?

Assumptions

This Question assumes the following:

  • accessing a list element by index and/or calculating the length of a list is possible in O(1).
  • the input list has k elements and the position list n elements. Both lists contain each element at most once, but may contain elements not in the other list. n will usually be greater than k.
  • The behavior for elements present in the input list but not the position list is not important, but must be consistent (e.g. all sorted to the start). Discarding the integers not present in the other list is acceptable, but suboptimal. Integers present in the position list but not in the input list must be ignored.
  • the input list is sorted by the integers themselves (lowest integer first), the position list is sorted by an unknown criteria
  • 'efficiency' refers to both runtime complexity and memory complexity, but runtime complexity is more important

Example of the problem

Here is an example of the problem I am trying to solve:

input_list = [1, 3, 5, 7, 11, 13]  # the list to sort
position_list = [5, 6, 7, 1, 11, 12, 13, 3]  # the order of elements
sorted_list = sort_by_position(input_list, position_list)
print(sorted_list)
[5, 7, 1, 11, 13, 3]

Potential solutions

So far I've identified the following solutions:

  • Simply using a regular sorting algorithm (e.g. merge sort, quick sort, ...), using a simple linear (O(n)) algorithm to determine the position of each element in the position list as comparison key. Even using the merge sort sorting methods this would be O(k * log(k) * n) at best.
  • Iterating over the position list and utilizing binary search on the input list to determine presence of the elements in the input list, inserting each found element one after another. This could achieve O(n * log(k)), which is better.

I believe that there is probably potential for improvement here and would appreciate your help.

$\endgroup$
3
  • $\begingroup$ You could put all the elements of the input list in a hashtable. Then traverse the position table from left to right. Each time you encounter an element stored in the hash table, append it to an output list. $\endgroup$ Aug 25 at 21:22
  • $\begingroup$ @ManuelLafond I see. That's a great idea, O(n + k) if I am not mistaken. Thanks. $\endgroup$ Aug 25 at 21:45
  • $\begingroup$ From the example, the designation position list seems slightly off: the second list does seem to impose a (total?) order. $\endgroup$
    – greybeard
    Aug 25 at 21:57

1 Answer 1

0
$\begingroup$

Small input_list:

h = {}
for x in input_list:
    h[x] = 1
for x in position_list:
    if h[x] == 1:
        yield x
        h[x]=2

Note I'm not using exact python syntax, "if h[x]==1" should handle the case where "x not in h" but you get the idea. Now, let's do elements present in the input list but not the position list, these still have h[x] set to 1:

for x in input_list:
    if h[x] == 1:
        yield x

This places the input-only elements at the end of the result. To place them at the beginning, the result array needs to be moved in memory since the number of these elements is only known at the end. If there are no duplicates, a set could be used:

h = set()
for x in input_list:
    h.add(x)
for x in position_list:
    if x in h:
        yield x
        h.remove(x)

Variant: instead of a hashtable, binary search can be used on the input list since it is sorted. This will use less memory.

  • Build zeroed byte array or bitmap b[ len(input_list) ]
  • For x in position_list, binary-search in input_list. If found at position pos, set b[pos]=1 and output x.
  • Iterate input_list, if h[pos]=0, it means x has not been found in the position_list, so output x

This version may also be faster, depending on what fit in cache. The second step of outputting the values not found in position_list is also faster, so if there is a large proportion of those, it could beat the previous version.

If the ints are densely packed and the bounds are known, an array or bitmap can be used instead of a hash.

It only reads position_list once sequentially, and ignores elements not present in input_list. Hashtable size depends on input_list only. So it allows an unlimited size of position_list, but the size of input_list is limited by fast memory for the hashtable.

Small position_list

If position_list is much shorter than input_list, then building a hash/bitmap of the whole input list is a waste of time.

  • Create a hashtable pos[x] which contains the position of integer x in position_list
  • Create an zeroed array out[] of the same length as position_list
  • for x in input_array, if pos[x] exists, set out[pos[x]]=1. Else, output x.
  • scan out[] and output the ints in order of position

This puts the input-only elements first in the output. It reads the input once, so if the position list fits in memory, there is no limit to the size of input_list.

Large input and position lists

By large, I mean it doesn't fit in a practical amount of fast RAM, so hashtables and algos relying on random access are out. This is basically a huge database join, so the same strategies apply, for example:

  • Scan position_list and create a table t1 (x,pos)
  • disk-sort t1 on x (for example block qsort + merge)
  • Merge join with input_list which is already sorted on x
  • If x is present in input_list but not in position_list, output it. Otherwise, insert (x,pos) another table t2
  • Sort t2 on pos
  • output x values from t2
$\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.