dependency ordering

solve_dep.cs

var x = new S("x");
var y = new S("y");
var z = new S("z");
var k = new S("k");

y.Dep(z);

var xs = new List<S> { k, y, x, z };

var ys = new List<S>(xs);
ys.Sort();
Console.WriteLine(ys);

ys = new List<S>(xs);
BubbleSort(ys);
Console.WriteLine(ys);


ys = new List<S>(xs);
QuickSort<S>(ys, 0, ys.Count);
Console.WriteLine(ys);


void QuickSort<T>(IList<T> input, int low, int high) where T: IComparable<T>
{

    if (high - low >= 1)
	{
        int pivot_loc = partition(input, low, high);
    	QuickSort(input, low, pivot_loc);
    	QuickSort(input, pivot_loc + 1, high);
	}
}

int partition<T>(IList<T> input, int low, int high) where T: IComparable<T>
{
    var pivot = input[high - 1];
    int i = low;

    for (int j = low; j < high - 1; j++)
    {
        if (input[j].CompareTo(pivot) <= 0)
        {
            swap(input, i, j);
			i++;
        }
    }
    swap(input, i, high - 1);
    return i;
}



void swap<T>(IList<T> input, int a, int b)
{
    var temp = input[a];
    input[a] = input[b];
    input[b] = temp;
}


static void BubbleSort<T>(IList<T> array) where T: IComparable<T>
{
    int length = array.Count;
    if (length == 0)
        return;
    

    for (int i = 0; i < length; i++)
    {
        for (int j = i + 1; j < length; j++)
        {
            if (array[i].CompareTo(array[j]) > 0)
            {
                var temp = array[i];

                array[i] = array[j];

                array[j] = temp;
            }
        }
    }
}


public class S: IComparable<S>
{
	HashSet<S> deps = new HashSet<S>();
	string Name;
	public S(string name)
	{
	   Name = name;
	}
	public void Dep(S s)
	{
		deps.Add(s);
	}
	
	public override string ToString() => Name;
	
	public int CompareTo(S s)
	{
	    if (deps.Contains(s))
		{
			return 1;
		}
		if (s.deps.Contains(this))
		{
			return -1;
		}
		return 0;
	}
}