
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 a mapping between items, and items they depend on, a topological sort orders items so that no item precedes an item it depends upon.

The compiling of a library in the VHDL language has the constraint that a library must be compiled after any library it depends on.

A tool exists that extracts library dependencies.



Task

Write a function that will return a valid compile order of VHDL libraries from their dependencies.

 Assume library names are single words. 
 Items mentioned as only dependents, (sic), have no dependents of their own, but their order of compiling must be given.
 Any self dependencies should be ignored. 
 Any un-orderable dependencies should be flagged.


Use the following data as an example:

LIBRARY          LIBRARY DEPENDENCIES
=======          ====================
des_system_lib   std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01             ieee dw01 dware gtech
dw02             ieee dw02 dware
dw03             std synopsys dware dw03 dw02 dw01 ieee gtech
dw04             dw04 ieee dw01 dware gtech
dw05             dw05 ieee dware
dw06             dw06 ieee dware
dw07             ieee dware
dware            ieee dware
gtech            ieee gtech
ramlib           std ieee
std_cell_lib     ieee std_cell_lib
synopsys


Note: the above data would be un-orderable if, for example, dw04 is added to the list of dependencies of dw01.



C.f.

   Topological sort/Extracted top item.


There are two popular algorithms for topological sorting:

   Kahn's 1962 topological sort [1] 
   depth-first search [2] [3]


Module testthis {
	\\ empty stack
	Flush
	inventory LL
	append LL, "des_system_lib":=(List:="std", "synopsys", "std_cell_lib", "des_system_lib", "dw02", "dw01",  "ramlib", "ieee")
REM	append LL, "dw01":=(List:="dw04","ieee", "dw01", "dware", "gtech")
	append LL, "dw01":=(List:="ieee", "dw01", "dware", "gtech")
	append LL, "dw02":=(List:="ieee", "dw02", "dware")
	append LL, "dw03":=(List:="std", "synopsys", "dware", "dw03", "dw02", "dw01", "ieee", "gtech")
	append LL, "dw04":=(List:= "ieee", "dw01", "dware", "gtech")
	append LL, "dw05":=(List:="dw05", "ieee", "dware")
	append LL, "dw06":=(List:="dw06", "ieee", "dware")
	append LL, "dw07":=(List:="ieee", "dware")
	append LL, "dware":=(List:="ieee", "dware")
	append LL, "gtech":=(List:="ieee", "gtech")
	append LL, "ramlib":=(List:="std", "ieee")
	append LL, "std_cell_lib":=(List:="ieee", "std_cell_lib")
	append LL, "synopsys":=List
	\\ inventory itmes may have keys/items or keys.
	\\ here we have keys so keys return as item also
	\\ when we place an item in a key (an empty string) ...
	\\ we mark the item to not return the key but an empty string
	inventory final
	mm=each(LL)
	while mm
		k$=eval$(mm!)
		m=eval(mm)
		mmm=each(m)
		While mmm
			k1$=eval$(mmm!)
			if not exist(LL, k1$) then
				if not exist(final, k1$) then append final, k1$
				return m, k1$:=""      \\ mark that item
			else
				mmmm=Eval(LL)
				if len(mmmm)=0 then
					if not exist(final, k1$) then append final, k1$
					return m, k1$:=""     \\ mark that item
				end if
			end if
		end while
	end while
	mm=each(LL)
	while mm
		\\ using eval$(mm!) we read the key as string
		k$=eval$(mm!)
		if exist(final, k$) then continue
		m=eval(mm)
		mmm=each(m)
		While mmm
			\\ we read the item, if no item exist we get the key
			k1$=eval$(mmm)
			if k1$="" then continue
			if exist(final, k1$) then  continue
			data k1$    \\ push to end to stack
		end while
		while not empty
			read k1$
			if exist(final, k1$) then continue
			m=LL(k1$)
			mmm=each(m)
			delthis=0
			While mmm
				k2$=eval$(mmm)
				if k2$="" then continue
				if k1$=k2$ then continue
				if exist(final, k2$) then continue
				push k2$   \\ push to top of stack
				return m, k2$:=""
				delthis++
			end while
			if delthis=0 then
				if not exist(final, k1$) then
					mmm=each(m)
					While mmm
						k2$=eval$(mmm!)
						if k2$=k1$ then continue
						if exist(final, k2$) Else
							Print "unsorted:";k1$, k2$
						end if
					end while
			 		append final, k1$ : Return LL, k1$:=List
				end if
			end if
		end while
		if not exist(final, k$) then append final, k$
	end while
	document doc$
	ret=each(final,1, -2)
	while ret
		doc$=eval$(ret)+" -> "
	end while
	doc$=final$(len(final)-1!)
	Report doc$
	clipboard doc$
}
testthis
 