List sorting algorithm based on the ordering of another, partial, list

Question

This question is different from other questions on sorting a list based on the order of another list in the sense that the order list does not contain all the keys used in the list.

Say I have a list of [a, b, c, d, e] and my list of orders [b, d, e] .

Now I am changing my order list to [b, e, d] . Is there a relatively simple algorithm for using the source list? Let's say it doesn't matter if the final order is [a, b, e, c, d] or [a, b, c, e, d] , and the list of orders will always be a subset of the original list.

Edit: clearing some questions about the final order, from my example: e was ordered between b and d , and in the sorted list it doesn't matter if e ends next to b or d . But, for example, if, due to this sorting, a moved after b - while legal ordering is undesirable.

Answer 1

EDIT Here's a slightly more efficient version; instead of looking for an index of the order elements at each iteration (arr.indexOf), just find them at the beginning to update the indices.

Worst time if N is the length of your array and M is the length of your order O (N * M + M ^ 2)

 function partialSort(arr, order) { var orderIndex = []; for(var i = 0; i < order.length; i++) { orderIndex[i] = arr.indexOf(order[i]); } for(var i = 0; i < orderIndex.length; i++) { var indexI = orderIndex[i]; for(var j = i + 1; j < orderIndex.length; j++) { var indexJ = orderIndex[j]; if(indexI > indexJ) { var temp = arr[indexI]; arr[indexI] = arr[indexJ]; arr[indexJ] = temp; orderIndex[i] = indexJ; orderIndex[j] = indexI; indexI = indexJ; } } } return arr; } var a = [1, 2, 3, 4, 5, 6, 7]; var o = [3,5,7]; console.log(o + "\n" + partialSort(a, o)); o = [5,3,7]; console.log(o + "\n" + partialSort(a, o)); o = [7,3,5]; console.log(o + "\n" + partialSort(a, o)); 

---

Here is the version using MlogM O sort (N * M + M * log (M) + M)

 function partialSort(arr, order) { var orderIndex = []; for(var i = 0; i < order.length; i++) { orderIndex[i] = arr.indexOf(order[i]); } // sort by index ~some quick sort variant O(M * log(M)) orderIndex.sort(function(a, b) { return a - b; }); // put the ordered elements in the correct sequence in the main array for(var i = 0; i < orderIndex.length; i++) { arr[orderIndex[i]] = order[i]; } return arr; } 

If you want maximum efficiency, you can replace orderIndex.sort with sorting the number O (N * M + M + M)

Answer 2

You can accomplish what you want by setting up an arbitrary comparator, as Dennis Callanan suggested, and then performing a stable view of the array. Quicksort is not stable; he, as a rule, changes the order of elements not included in the partial order. Merge sort is a stable view.

If you use linear search in a comparator, the algorithm will work in O (n ^ 2 log n) time, I think. What you need to do to start it faster is to make one pass through a new array, hashing the position of each element in the array for a quick search.

I could implement it in Java, but I do not know Python, sorry.

Another look at this is the use of topological sorting. In your original list, you have → b → c → d → e, where the arrows mean “precedes” b. Then you add new data b → e → d. You must break down any arrows in the first list that lead to contradictions, i.e. D → e. What you have is a bunch of arrows:

a → b, b → c, c → d, b → e, e → d

If it is a directed acyclic graph (i.e. no contradictions), you can toposort in O (V + E) times. Since the number of edges does not exceed 2n, the time O (n) is very efficient.

The problem is to decide which arrows to break (and possibly replace with other arrows) in the original list so that there are no contradictions. In general, the NP-hard problem, called the minimal feedback set , but I suspect there is something in the structure of your problem that will speed up its work.

Finally, as regards simply replacing the elements in the (non-adjacent) subarray [..., b, ..., d, e] with the permutation given by the new array? This can be done in O (n) time.

Answer 3

One naive approach n ^ 2:

 for each S in order-list if S is in other-list remove S from other-list add S to end of other-list 

Because of which, items from the sort list will be deleted and added to your other list: [a, c, b, e, d]

Answer 4

Python approach easily implemented in any language (Java will not require functools )

 import functools order = [5, 1, 4] def numeric_compare(x, y): if x in order and y in order: if order.index(x) > order.index(y): return 1 elif order.index(x) < order.index(y): return -1 else: if x in order: return -1 elif y in order: return 1 return 0 a = [1,2,3,4,5] a.sort(key = functools.cmp_to_key(numeric_compare)) 

Answer 5

I wrote a quicksort version for fun for another question ( Javascript Double sorting algorithm ), which I have no idea if it is completely reliable. It was originally intended to sort only strings or just numbers, but it seems to have been adapted to this case (I changed the functions isNumber and less):

 function isNumber(x,y) { return (map[x]); } function less(a,b,y){ return y ? a < b : map[a] < map[b]; } function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t; } function partition(array, pivot, left, right, what) { var store = left, pivotValue = array[pivot]; swap(array, pivot, right); for (var v = left; v < right; v++) { if (less(array[v],pivotValue,what) && isNumber(array[v],what)) { swap(array, v, store); store++; } } while(!isNumber(array[store],what)) store++; swap(array, right, store); return store; } function doubleQSort(array, left, right, what) { while(!isNumber(array[right],what) && right > left) right--; while(!isNumber(array[left],what) && left < right) left++; var pivot = null; if (left < right) { pivot = (right + left) >> 1; while(!isNumber(array[pivot],what)) pivot--; newPivot = partition(array, pivot, left, right, what); doubleQSort(array, left, newPivot - 1,what); doubleQSort(array, newPivot + 1, right,what); } } 

Output:

 var things = ['a', 'b', 'c', 'd', 'e']; var map = {'b':1, 'e':2, 'd':3} doubleQSort(things,0,things.length - 1); console.log(things) // [a, b, c, e, d]