0

I searched a relevant question but couldn't find one. So my question is how do I sort an array based on an arbitrary order. For example, let's say the ordering is:

order_of_elements = ['cc', 'zz', '4b', '13']

and my list to be sorted:

list_to_be_sorted = ['4b', '4b', 'zz', 'cc', '13', 'cc', 'zz']

so the result needs to be:

ordered_list = ['cc', 'cc', 'zz', 'zz', '4b', '4b', '13']

please note that the reference list(order_of_elements) describes ordering and I don't ask about sorting according to the alphabetically sorted indices of the reference list.

You can assume that order_of_elements array includes all the possible elements.

Any pseudocode is welcome.

2
  • Any complexity requirements?
    – Nelfeal
    Commented Nov 8, 2018 at 9:58
  • Actually my problem is easy so there isn't any requirement for me but I just wanted to know if there is a specific algorithm or approach for this
    – MGoksu
    Commented Nov 8, 2018 at 10:38

3 Answers 3

2

A simple and Pythonic way to accomplish this would be to compute an index lookup table for the order_of_elements array, and use the indices as the sorting key:

order_index_table = { item: idx for idx, item in enumerate(order_of_elements) }
ordered_list = sorted(list_to_be_sorted, key=lambda x: order_index_table[x])

The table reduces order lookup to O(1) (amortized) and thus does not change the time complexity of the sort.

(Of course it does assume that all elements in list_to_be_sorted are present in order_of_elements; if this is not necessarily the case then you would need a default return value in the key lambda.)

1
  • I made that implicit assumption that order_of_elements includes all the possible elements. Thanks for pointing that out
    – MGoksu
    Commented Nov 8, 2018 at 10:44
1

Since you have a limited number of possible elements, and if these elements are hashable, you can use a kind of counting sort.

Put all the elements of order_of_elements in a hashmap as keys, with counters as values. Traverse you list_to_be_sorted, incrementing the counter corresponding to the current element. To build ordered_list, go through order_of_elements and add each current element the number of times indicated by the counter of that element.

hashmap hm;
for e in order_of_elements {
    hm.add(e, 0);
}

for e in list_to_be_sorted {
    hm[e]++;
}

list ordered_list;
for e in order_of_elements {
    list.append(e, hm[e]); // Append hm[e] copies of element e
}
2
  • Nice solution, thanks. Just out of curiosity, is the complexity O(n) here assuming that the append operation is O(1)?
    – MGoksu
    Commented Nov 8, 2018 at 10:51
  • 1
    Indeed it is. You traverse order_of_elements twice and list_to_be_sorted once. Hashmap insertions and lookup are of amortized constant complexity. Append (of one element) is constant on a linked-list, amortized constant on an array, and constant on a pre-sized array. So, overall, the complexity is amortized O(n), as would a usual counting-sort with hashmap would be (instead of O(n log n) for usual comparison-based sorts).
    – Nelfeal
    Commented Nov 8, 2018 at 11:07
0

Approach:

  1. create an auxiliary array which will hold the index of 'order_of_elements'
  2. sort the auxiliary array.

    2.1 re-arrange the value in the main array while sorting the auxiliary array

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.