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 algogeeks+unsubscr...@googlegroups.com.
