Sorting 10 numbers
Sam Benry
Ranch Hand
Posts: 89
posted 8 years ago
I'm basically looking for a good algorithm or method to do the following:
I have 10 numbers, you can use List<Integer> or int[] or what ever you want.
I want to sort the 10 numbers so the sum of the first 5 is approximately (or exactly if possible) equal to the sum of the last 5. The sum of the first 5 must be as close as possible to the sum of the last 5.
How can I do that?
Thank you.
I have 10 numbers, you can use List<Integer> or int[] or what ever you want.
I want to sort the 10 numbers so the sum of the first 5 is approximately (or exactly if possible) equal to the sum of the last 5. The sum of the first 5 must be as close as possible to the sum of the last 5.
How can I do that?
Thank you.
saumil baxi
Ranch Hand
Posts: 58
posted 8 years ago
one solution can be. If I have understood your problem correctly
Sort the numbers in such a way that .
You place the latest number at the last index.
Then Second latest at the first location.
Third Latest at Second last location and so on.
The sum of the first five elements would be close to sum of last five element in your List.
Sort the numbers in such a way that .
You place the latest number at the last index.
Then Second latest at the first location.
Third Latest at Second last location and so on.
The sum of the first five elements would be close to sum of last five element in your List.
posted 8 years ago
saumil baxi, I don't think that will work. What if your set of numbers were
1,2,3,4,5,6,7,8,9,100
If i'm reading your algorithm correctly, you would sort them like:
group 1: 100, 8, 6, 4, 2: Sum is 120
group 2: 9, 7, 5, 3, 1: Sum is 25
diff = 95
But this would be a better way to do it:
group 1: 100, 1, 2, 3, 4: Sum = 110
group 2: 5,6,7,8,9: Sum = 35
diff = 75
I think your best bet is to go through the numbers from largest to smallest. Add each number to whichever group has the lowest sum. If the sums are the same, it doesn't matter.
I haven't proved to myself this is the correct way to go, but it feels right to me...
1,2,3,4,5,6,7,8,9,100
If i'm reading your algorithm correctly, you would sort them like:
group 1: 100, 8, 6, 4, 2: Sum is 120
group 2: 9, 7, 5, 3, 1: Sum is 25
diff = 95
But this would be a better way to do it:
group 1: 100, 1, 2, 3, 4: Sum = 110
group 2: 5,6,7,8,9: Sum = 35
diff = 75
I think your best bet is to go through the numbers from largest to smallest. Add each number to whichever group has the lowest sum. If the sums are the same, it doesn't matter.
I haven't proved to myself this is the correct way to go, but it feels right to me...
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
Sam Benry
Ranch Hand
Posts: 89
What are you doing? You are supposed to be reading this tiny ad!
the new thread boost feature brings a LOT of attention to your favorite threads
https://coderanch.com/t/674455/ThreadBoostfeature
