CODEWITHSUNDEEP
algorithmsorting
MGoksu
MGoksu

Reputation: 529

How to order a list according to an arbitrary order

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.

Upvotes: 0

Views: 2122

Answers (3)

Papai from BEKOAIL
Papai from BEKOAIL

Reputation: 1539

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

Upvotes: 0

meowgoesthedog
meowgoesthedog

Reputation: 15045

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.)

Upvotes: 2

Nelfeal
Nelfeal

Reputation: 13269

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
}

Upvotes: 1

Related Questions