Rounded Percentages up to 100% using Insertion-Sort Algorithm

When you need to represent percentages as whole numbers using  Math.round() ,  you end up with a total of 101%. 

	Value	Percentage	Rounded
A	650	49.88%	50
B	230	17.65%	18
C	150	11.51%	12
D	273	20.95%	21
	1303	100.00%	101

As you can see above the total in the rounded column is 101. Let's solve this problem using a well known algorithm.

Step 1:

We begin to sum the given values for calculating the percentages. While iterating, we copy all the properties to a destination object (NVPPercentage) which will be pushed to an array (temp).

	let total: number = 0;
	let temp: NVPPercentage[] = [];
	//sum values
	list.forEach((element) => {
	total += element.value;
	let l: NVPPercentage = {
	name: element.name,
	value: Math.abs(element.value),
	percentage: 0
	}
	temp.push(l);
	});

view raw sumValues hosted with ❤ by GitHub

Step 2:

The insertion sort, is an efficient algorithm for sorting a small number of elements. We start for each element to calculate the percentage (P) and the rounded percentage (RP). We sum also the rounded percentages (e.g. 101). We also compare in an inner loop the current element (CE) with the left ones for sorting purpose.

While j is CE - 1, we define the criteria for the inner loop as :

j >= 0 && (RP[j] - P[j]) < (RP[CE] - P[CE])

So, we sort our sequence in descending order (temp) by calculating the difference between the RP and P.

We substract the sum of rounded percentages from 100 to get the remainder.

	let off: number = 0;
	let remainder: number = 0;
	//insertion sort algorithm
	temp.forEach((element, index) => {
	let percentage = (element.value / total) * 100;
	let rounded = Math.round(percentage);
	element.percentage = rounded;
	off += element.percentage;
	let j = index - 1;
	while (j >= 0 && Math.round((temp[j].value / total) * 100)
	- (temp[j].value / total) * 100 < (rounded - percentage)) {
	temp[j + 1] = temp[j];
	j = j - 1;
	}
	temp[j + 1] = element;
	});
	remainder = off - 100;

view raw insertionSort hosted with ❤ by GitHub

Step 3:

The last step simply add or substract the remainder from the sorting sequence elements.

	if (remainder > 0) {
	let i: number = 0;
	while (remainder > 0) {
	temp[i].percentage = temp[i].percentage - 1;
	i += 1;
	remainder -= 1;
	}
	} else {
	let i: number = temp.length - 1;
	while (remainder < 0) {
	temp[i].percentage = temp[i].percentage + 1;
	i -= 1;
	remainder += 1;
	}
	}

view raw appReminder hosted with ❤ by GitHub

Full Code:

	toPercent(list: NVPNumber[]): NVPPercentage[] {
	//initialization
	let total: number = 0;
	let temp: NVPPercentage[] = [];
	//sum values
	list.forEach((element) => {
	total += element.value;
	let l: NVPPercentage = {
	name: element.name,
	value: Math.abs(element.value),
	percentage: 0
	}
	temp.push(l);
	});
	let off: number = 0;
	let remainder: number = 0;
	//insertion sort algorithm
	temp.forEach((element, index) => {
	let percentage = (element.value / total) * 100;
	let rounded = Math.round(percentage);
	element.percentage = rounded;
	off += element.percentage;
	let j = index - 1;
	while (j >= 0 && Math.round((temp[j].value / total) * 100)
	- (temp[j].value / total) * 100 < (rounded - percentage)) {
	temp[j + 1] = temp[j];
	j = j - 1;
	}
	temp[j + 1] = element;
	});
	remainder = off - 100;
	if (remainder > 0) {
	let i: number = 0;
	while (remainder > 0) {
	temp[i].percentage = temp[i].percentage - 1;
	i += 1;
	remainder -= 1;
	}
	} else {
	let i: number = temp.length - 1;
	while (remainder < 0) {
	temp[i].percentage = temp[i].percentage + 1;
	i -= 1;
	remainder += 1;
	}
	}
	return temp;
	}

view raw toPercent hosted with ❤ by GitHub