Results 1 to 20 of 57
Thread: Sorting 10 numbers
 12162008, 02:44 PM #1Member
 Join Date
 Feb 2008
 Posts
 9
 Rep Power
 0
Sorting 10 numbers
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 u 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?
Thanks.
 02042009, 06:30 PM #2Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
pseudo code,
place largest number in group 1, then next largest in group 2, then next in group 2, then next in group 1... do this until you run out of numbers, then add up group 1 and then add up group 2... it seems to me since you have to have 5 numbers in each group then it probably won't be equal all the time. here's an example.
1,2,3,4,5,6,7,8,9,10
Group 1 = 10,7,6,3,2 = 28
Group 2 = 9,8,5,4,1 = 27
and this seems to be right being that both groups add up are an odd number meaning you can't split them equally.
hope this helps, and i always appreciate comments.
 02042009, 07:36 PM #3Senior Member
 Join Date
 Sep 2008
 Posts
 564
 Rep Power
 12
i think this greedy algorithm is more suitable, but don't know if it's correct.
Java Code:for each item in input list if total of list a > total of list b then add current item to list b else add current item to list a
 02042009, 08:24 PM #4Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
unfortunately the greedy algorithm would work however the amount of checks that it would have to reproduce would be O(n^2) and i believe if you could sort the list and then do the split, mathimatically it works out, and programmatically it comes out to sort time + n which is O(n + n log n) time. which is O(n log n) time :0
the sort should be fairly simple since it's only 10 numbers, and the grouping them will be simple also. adding them up will take no time also :) it's a quick math algorithm that might actually already been proven somewhere :)
and i just relooked at what emceenugget posted a bit better, 1 pass through the loop means you have to add group a and b each, and then readd item to a group with a check on top of it. 4 operations per item in the list.
still isn't bad.
if you can get passed the items being sorted then it's 1 operation per item. so it could be better but all depends on sorting i suppose.
so good call emceenugget :) but either way i think could work because of the small list size.Last edited by Jasonre; 02042009 at 08:29 PM.
 02042009, 08:39 PM #5Senior Member
 Join Date
 Sep 2008
 Posts
 564
 Rep Power
 12
oh yeah. forgot about that i can't assume the list is sorted. d'oh.
 02042009, 11:55 PM #6
i found this interesting and thought i'd give it a try.
* Assume a sorted int[10].
I used a for loop.
if i is evenNumber, then copy n[i] and n[lasti] to group1,
else copy to group2.
but if i is middle values, then one goes to group1, and next goes to group2.
so assuming numbers are 1  10,
group1 is: 1,10,3,8,5 = 27
group2 is: 2, 9,4,7,6 = 28
there's more effecient ways, more research, more research...
edit: don't really work when numbers duplicates as in 1,1,1,2,3,3,3,3,5,5,5Last edited by angryboy; 02052009 at 12:03 AM.
USE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02052009, 12:01 AM #7Senior Member
 Join Date
 Sep 2008
 Posts
 564
 Rep Power
 12
well i just realized that my algorithm is broken in that if you have a number that's really big that it'll add on everything else to the second list regardless of balancing the amount of items in it. i'd say once one side is full to add the rest onto the remaining list, but i don't think that's complete yet either.
 02052009, 12:09 AM #8
 02052009, 07:28 AM #9... This is the number partitioning problem, a classic and surprisingly difficult problem in computer science. In particular, it is NPcomplete; it belongs to a category of problems for which no known algorithm can guarantee a resolution in a reasonable time (bounded by a polynomial in their size). ...
EDIT:
jasonre's algor. is pretty good except when used on very large numbers. see here:
Java Code:Set1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 group1: 10, 7, 6, 3, 2 group2: 9, 8, 5, 4, 1 SUMG1: 28 SUMG2: 27 Set2: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 group1: 10, 7, 6, 3, 2 group2: 9, 8, 5, 4, 1 SUMG1: 28 SUMG2: 27 Set3: 10, 13, 23, 6, 20, 30, 12, 3, 9, 34 group1: 34, 20, 13, 9, 6 group2: 30, 23, 12, 10, 3 SUMG1: 82 SUMG2: 78 Set4: 6, 4, 9, 14, 12, 3, 15, 15, 15, 7 group1: 15, 14, 12, 6, 4 group2: 15, 15, 9, 7, 3 SUMG1: 51 SUMG2: 49 Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209 group1: 228, 209, 179, 58, 48 group2: 225, 209, 141, 93, 11 SUMG1: 722 SUMG2: 679 Set6: 2474, 1129, 1388, 3752, 821, 2082, 201, 739, 234, 1964 group1: 3752, 1964, 1388, 739, 234 group2: 2474, 2082, 1129, 821, 201 SUMG1: 8077 SUMG2: 6707 Set7: 600, 4, 9, 15, 15, 3, 15, 15, 15, 7 group1: 600, 15, 15, 7, 4 group2: 15, 15, 15, 9, 3 SUMG1: 641 SUMG2: 57
Last edited by angryboy; 02052009 at 09:05 AM.
USE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02052009, 07:56 PM #10
using jasonre's algo. I added an if statement before splitting the nums into 2 groups. like this:
Java Code:if((sum(n) < max)&&(!(i==LAST))){
and that made a huge difference in the results:
Java Code:Set1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 group1: 10, 7, 6, 3, 2 group2: 9, 8, 5, 4, 1 SUMG1: 28 SUMG2: 27 Set2: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 group1: 10, 7, 6, 3, 2 group2: 9, 8, 5, 4, 1 SUMG1: 28 SUMG2: 27 Set3: 10, 13, 23, 6, 20, 30, 12, 3, 9, 34 group1: 34, 20, 13, 9, 6 group2: 30, 23, 12, 10, 3 SUMG1: 82 SUMG2: 78 Set4: 6, 4, 9, 14, 12, 3, 15, 15, 15, 7 group1: 15, 14, 12, 6, 4 group2: 15, 15, 9, 7, 3 SUMG1: 51 SUMG2: 49 Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209 group1: 228, 209, 179, 58, 48 group2: 225, 209, 141, 93, 11 SUMG1: 722 SUMG2: 679 Set6: 2474, 1129, 1388, 3752, 821, 2082, 201, 739, 234, 1964 group1: 3752, 1964, 1388, 739 group2: 2474, 2082, 1129, 821, 201, 234 SUMG1: 7843 SUMG2: 6941 Set7: 600, 4, 9, 15, 15, 3, 15, 15, 15, 7 group1: 4, 9, 15, 15, 3, 15, 15, 15, 7 group2: 600 SUMG1: 98 SUMG2: 600
USE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02052009, 08:08 PM #11Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
well the only problem with that last part is that when the problem was first proposed, it was stated that there must be 5 numbers in each group. therefore you'll have to disinclude any of the last post that have 6 numbers in 1 group and 4 in the other, or 1 number in 1 group and 9 in the other. but if this is what you meant, i believe the algorithm would be just a tad different than my first post. I could probably figure that one what if that's what you meant but the check you through in there will be needed for sure. let me know..
 02052009, 08:13 PM #12
oh, haha got too into it, forgot about the 5 per group limit.
actually, since the limits are fixed (10num, 5/g), i think its better to check for combinations of 5 per group. then check the difference between each combination for the smallest value. the two groups w/ the smallest diff will be the one desired. what's YHO on this?Last edited by angryboy; 02052009 at 08:26 PM.
USE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02052009, 08:20 PM #13Senior Member
 Join Date
 Sep 2008
 Posts
 564
 Rep Power
 12
npcomplete problem, eh? i think we should all just give ourselves a pat on the back and stop trying =p
 02052009, 08:23 PM #14
that depends on the size. its only 10 numbers. I CAN TAKE IT!!
USE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02052009, 09:05 PM #15Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
Well i don't think it's npcomplete because as long as you have the size, and they are ordered then move 1 in to one group then 2 into the next, 2 into the next so on and so forth and having 2n nodes, then it isn't hard to add up the result. don't doubt it's a hard problem though. however if the 2 group sizes aren't equal then yes it could be quite a hard problem and maybe then npcomplete.
I don't think you want to check each of the combinations of numbers, yes 10 numbers a computer could do it, however 20 numbers a computer might fail big time. that's because the combination of numbers would 10c5 and 5c5 however when we start thinking about 20c10 and 10c10 we are dealing with numbers upward of 20! mean huge...
all i did was think about it, if i place the largest number in the first group. then the next largest number has to be in the 2nd group.... next largest number belongs in the 2nd group because it's already smaller than the first group... but then the next number goes in the 1st...
now for the 10,10,10,20,20,30,30,30,400,500
grp 1: 500,30,30,10,10
grp 2: 400,30,20,20,10
but we can already see that a problem like this won't work. here's where that check comes into play that i mentioned in the post a little earlier. if ( sum(grp1)  sum(grp2) > nextValue ) then add lowest group, and do this till max number of items are in grp2. I think that will finish it up.
 02052009, 11:46 PM #16
yeah jasonre, you're right. it worked out nicely. (still need to test w/ other number combos. thats for later...)
* src will be shown after OP shows his...
Java Code:[B]Set1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10[/B] group1: 10, 7, 6, 3, 2 group2: 9, 8, 5, 4, 1 SUMG1: 28 SUMG2: 27 [B]Set2: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1[/B] group1: 10, 7, 6, 3, 2 group2: 9, 8, 5, 4, 1 SUMG1: 28 SUMG2: 27 [B]Set3: 10, 13, 23, 6, 20, 30, 12, 3, 9, 34[/B] group1: 34, 20, 12, 10, 3 group2: 30, 23, 13, 9, 6 SUMG1: 79 SUMG2: 81 [B]Set4: 6, 4, 9, 14, 12, 3, 15, 15, 15, 7[/B] group1: 15, 15, 9, 7, 4 group2: 15, 14, 12, 6, 3 SUMG1: 50 SUMG2: 50 [B]Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209[/B] group1: 228, 209, 141, 93, 58 group2: 225, 209, 179, 48, 11 SUMG1: 729 SUMG2: 672 [B]Set6: 2474, 1129, 1388, 3752, 821, 2082, 201, 739, 234, 1964[/B] group1: 3752, 1964, 1129, 234, 201 group2: 2474, 2082, 1388, 821, 739 SUMG1: 7280 SUMG2: 7504 [B]Set7: 600, 4, 9, 15, 15, 3, 15, 15, 15, 7[/B] group1: 600, 9, 7, 4, 3 group2: 15, 15, 15, 15, 15 SUMG1: 623 SUMG2: 75
Java Code:nextVal = findNextLargest(); if(gp1gp2 != nextVal && both groups not filled){ [I]// also works w/: if(both groups not filled){ // need more test on this.[/I] if(sum(gp1) < sum(gp2)) add next to gp1; else add next to gp2; } else{ if(gp1 is not filled) add next to gp1; else add next to gp2; }
Java Code:[B]if(gp1gp2 != nextVal && both groups not filled){[/B] Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209 group1: 228, 209, 141, 93, 58 group2: 225, 209, 179, 48, 11 SUMG1: 729 SUMG2: 672 [B]if(both groups not filled){[/B] Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209 group1: 228, 209, 141, 93, 48 group2: 225, 209, 179, 58, 11 SUMG1: 719 SUMG2: 682
Last edited by angryboy; 02062009 at 12:17 AM.
USE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02062009, 09:10 PM #17
I test out the combo method and its PERFECT!! I used a 10C5 combination generator to get all the possible combos, which is 252. Then filter out the results several times to get the final two groups needed. Because its only 10C5, I didn't notice any difference in speed.
Here are the results.
Java Code:Set1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 group1: 1, 2, 5, 9, 10 group2: 3, 4, 6, 7, 8 SUMG1: 27 SUMG2: 28 Set2: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 group1: 10, 9, 6, 2, 1 group2: 8, 7, 5, 4, 3 SUMG1: 28 SUMG2: 27 Set3: 10, 13, 23, 6, 20, 30, 12, 3, 9, 34 group1: 10, 13, 20, 3, 34 group2: 23, 6, 30, 12, 9 SUMG1: 80 SUMG2: 80 Set4: 6, 4, 9, 14, 12, 3, 15, 15, 15, 7 group1: 6, 14, 12, 3, 15 group2: 4, 9, 15, 15, 7 SUMG1: 50 SUMG2: 50 Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209 group1: 93, 141, 209, 48, 209 group2: 58, 179, 225, 228, 11 SUMG1: 700 SUMG2: 701 Set6: 2474, 1129, 1388, 3752, 821, 2082, 201, 739, 234, 1964 group1: 2474, 1388, 821, 739, 1964 group2: 1129, 3752, 2082, 201, 234 SUMG1: 7386 SUMG2: 7398 Set7: 600, 4, 9, 15, 15, 3, 15, 15, 15, 7 group1: 600, 4, 9, 3, 7 group2: 15, 15, 15, 15, 15 SUMG1: 623 SUMG2: 75 Set8: 1, 1, 1, 2, 2, 2, 3, 3, 4, 5 group1: 1, 1, 1, 4, 5 group2: 2, 2, 2, 3, 3 SUMG1: 12 SUMG2: 12
USE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02062009, 09:26 PM #18Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
yea the combo method works, and you won't find a difference in speed unless you were on a very slow computer or if you try to use more numbers to sort. for instance, instead of 10 numbers, use 100 numbers, and 50 in each group. and just for the fun of it, use the fibonacci sequence for the numbers. that's 1,1,2,3,5,8,13,21,34,...
you might find it a bit more difficult for the combination method. i think that would be fun to see the difference. and to verify how much the cpu works, add a system.out of the time stamp just before and after it goes into the work of both ways in which you do it. let me know the results, i'm curious :)
oh yes and make sure it's sorted highest number backwards.
if you need help generating the sequence, its
ArrayList<Double> a = new ArrayList<Double>();
double n = 1;
double m = 1;
a.add(n);
a.add(m);
for (int i = 1; i < 99; i++) {
double o = a.get(i) + a.get(i1);
a.add(o);
}
for (int i = 0; i < a.size(); i++) {
System.out.println(a.get(i));
}
then reorganize them the other direction.Last edited by Jasonre; 02062009 at 09:38 PM.
 02062009, 09:50 PM #19
k, that sounds like a fun project for the weekend. right now, both algo. are written procedural using int arrays, so i'll first need to reorganize it more OOP. then i'll test for fibonacci# from HL and also from LH. and see which has the better speed/result.
USE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02062009, 10:06 PM #20Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
Similar Threads

finding the largest k numbers in an array without sorting the whole list?
By jmmjm in forum Advanced JavaReplies: 5Last Post: 02072009, 08:48 AM 
printing two smallest numbers from a series of numbers
By trofyscarz in forum New To JavaReplies: 2Last Post: 10152008, 12:46 AM 
sorting
By jot321 in forum New To JavaReplies: 18Last Post: 10022008, 11:30 AM 
sorting problem
By mcal in forum New To JavaReplies: 1Last Post: 02142008, 09:13 AM 
sorting JTable
By mansi_3001 in forum Advanced JavaReplies: 3Last Post: 08102007, 07:29 PM
Bookmarks