
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Given   M   as a list of items and another list   N   of items chosen from   M,   create   M'   as a list with the first occurrences of items from   N   sorted to be in one of the set of indices of their original occurrence in   M   but in the order given by their order in   N.

That is, items in   N   are taken from   M   without replacement, then the corresponding positions in   M'   are filled by successive items from   N.



For example

if   M   is   'the cat sat on the mat'
And   N   is   'mat cat' 
Then the result   M'   is   'the mat sat on the cat'. 
The words not in   N   are left in their original positions.



If there are duplications then only the first instances in   M   up to as many as are mentioned in   N   are potentially re-ordered.



For example

  M = 'A B C A B C A B C' 
  N = 'C A C A' 
Is ordered as:

 M' = 'C B A C B A A B C' 


Show the output, here, for at least the following inputs:

Data M: 'the cat sat on the mat' Order N: 'mat cat'
Data M: 'the cat sat on the mat' Order N: 'cat mat'
Data M: 'A B C A B C A B C'      Order N: 'C A C A'
Data M: 'A B C A B D A B E'      Order N: 'E A D A'
Data M: 'A B'                    Order N: 'B'      
Data M: 'A B'                    Order N: 'B A'    
Data M: 'A B B A'                Order N: 'B A'



Cf

 Sort disjoint sublist


#lang racket
(define disjorder
  (match-lambda**
   (((list) n) '())      
   ((m (list)) m)      
   (((list h m-tail ...) (list h n-tail ...))
    (list* h (disjorder m-tail n-tail)))
   ;; the (not g/h) below stop greedy matching of the list which
   ;; would pick out orderings from the right first.
   (((list h (and (not g) m-tail-left) ... g m-tail-right ...)
     (list g (and (not h) n-tail-left) ... h n-tail-right ...))
    (disjorder `(,g ,@m-tail-left ,h ,@m-tail-right)
               `(,g ,@n-tail-left ,h ,@n-tail-right)))
   (((list h m-tail ...) n)
    (list* h (disjorder m-tail n)))))
 
(define (report-disjorder m n)
 (printf "Data M: ~a Order N: ~a -> ~a~%"
  (~a #:min-width 25 m) (~a #:min-width 10 n) (disjorder m n)))
 
;; Do the task tests
(report-disjorder '(the cat sat on the mat) '(mat cat))
(report-disjorder '(the cat sat on the mat) '(cat mat))
(report-disjorder '(A B C A B C A B C)      '(C A C A))
(report-disjorder '(A B C A B D A B E)      '(E A D A))
(report-disjorder '(A B)                    '(B))
(report-disjorder '(A B)                    '(B A))
(report-disjorder '(A B B A)                '(B A))
;; Do all of the other python tests
(report-disjorder '()            '())
(report-disjorder '(A)           '(A))
(report-disjorder '(A B)         '())
(report-disjorder '(A B B A)     '(A B))
(report-disjorder '(A B A B)     '(A B))
(report-disjorder '(A B A B)     '(B A B A))
(report-disjorder '(A B C C B A) '(A C A C))
(report-disjorder '(A B C C B A) '(C A C A))