It is like bubble sort type of algorithm. I'm not tested it on different
data sets, created just for fun and your critic)
struct valuePos {int val; int pos;}
valuePos[,] data = new valuePos[n,n]; // assign input data array to [val]
properties
// initialize by maximum val in data +1 or just unreachable value
// if index is not in use, calculated CompetitiveSwaps value will be less
than zero and we use this as flag
int[] CompetitiveSwaps = {10000,10000,...}; // array of values to compare
int[] indexCount = {0,0,0...,0}; // size of n
sort each column of data by val
// input matrix val(index) after sort
6(1) 200(1) 20(1) 150(1) | 4(2) 3(2) 2(2) 10(3)
4(2) 3(2) 2(2) 100(2) | 6(1) 30(3) 20(1)
100(2)
300(3) 30(3) 400(3) 10(3) | 300(3) 200(1) 300(4) 150(1)
400(4) 300(4) 300(4) 400(4) | 400(4) 300(4) 400(3) 400(4)
int swapRow=1;
while(indexCount.indexof(0) != -1) // until all indexes will be used once,
so all elements in indexCount array are "1"
{
for(int i =0; i <n ;i++)
{
indexCount[data[0, i].pos]++; //indexCount {0, 3, 1, 0} for first
iteration
// calculate current replacement weight of such index, the more times
index is used the less expensive to replace it ( / indexCount[data[0,
i].pos])
CompetitiveSwaps[data[0, i].pos] = data[0, i].val /
indexCount[data[0, i].pos];
//CompetitiveSwaps {10000, 0, 10, 10000} for
first iteration
}
for(int i =0; i <n ;i++)
{
//[0] 6 - 4 -10000 = -9998; [1] 30 - 3 -10 = 17; [2] 20 - 2
-10000= -9982; [3] 100 - 10 - 0 =90 for first iteration
// calculating increase of sum in case of swap by substracting top
array val from replacement val ( data[swapRow, i].val - data[0, i].val )
// and indirect increase in case of replacement the current val of
such index ( - CompetitiveSwaps[data[swapRow, i].pos])
CompetitiveSwaps[i] = data[swapRow, i].val - data[0, i].val -
CompetitiveSwaps[data[swapRow, i].pos];
}
int minValColumn = find_Index_Of_Minimum_Value(CompetitiveSwaps);
if(CompetitiveSwaps[minValColumn] < 0) // using negative value as
sign that index is not in use, and it must "float" to the top
{
swap(data[swapRow, minValColumn], data[0, minValColumn]);
}else
{
swapRow++;
}
CompetitiveSwaps = {10000,10000,...};
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
