Xtykutl

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.

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

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

}

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