Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / Multivariable Sorting

Author
Message
PirateJohn
14
Years of Service
User Offline
Joined: 4th Aug 2011
Location: California
Posted: 11th Sep 2011 22:37
I've seen and implemented some of the quicksort algorithms I've found here and elsewhere, but one thing I've never been able to find is a good algorithm for multivariable sorting.

As an example, in the Olympic shooting game I'm creating, the scores, according to ISSF rules, are sorted by number of points, then ties are broken by the score of the most recent round, and then by the score of the second most recent round, and so on.

Anybody know a good algorithm for sorting by several variables?
Suicidal Sledder
21
Years of Service
User Offline
Joined: 17th Aug 2004
Location: Tikrit, Iraq
Posted: 11th Sep 2011 22:46
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 11th Sep 2011 22:50
http://en.wikipedia.org/wiki/Bubble_sort is wiki's bubble sort algorithm. There's tons of other references if you narrow your google search...

Warning! May contain Nuts!
PirateJohn
14
Years of Service
User Offline
Joined: 4th Aug 2011
Location: California
Posted: 11th Sep 2011 23:15
I did think of the bubble sort as a fallback. I didn't know if there was something better, for example what Excel uses.

As for SS's question, the scores are either integers or they have one decimal point. Here's an example as it is used in the shooting game:

The following are scores from six shooters

Smith USA 100 100 99 100 99 100 -- 598
Jones CAN 99 100 100 99 100 100 -- 598
Ivanov RUS 100 100 100 100 99 100 -- 599
Mendez MEX 100 99 100 99 100 99 -- 597
Picard FRA 100 99 100 100 100 98 -- 597
McKay IRL 100 100 99 100 100 100 -- 599

They would be sorted this way:

McKay IRL 100 100 99 100 100 100 -- 599
Ivanov RUS 100 100 100 100 99 100 -- 599
Jones CAN 99 100 100 99 100 100 -- 598
Smith USA 100 100 99 100 99 100 -- 598
Mendez MEX 100 99 100 99 100 99 -- 597
Picard FRA 100 99 100 100 100 98 -- 597

McKay would defeat Ivanov because although they had the same score in round six, McKay's score for round five was higher. And so on down the line.
Pincho Paxton
23
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 11th Sep 2011 23:19 Edited at: 11th Sep 2011 23:22
The one I use is just...



IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 11th Sep 2011 23:39
@PirateJohn,
I think that SS was more interested in how the scores are stored in memory. Do you use a UDT, or a multi-dimensional array? Can you give us example code to work with?

How many different scores are possible per person?

Suicidal Sledder
21
Years of Service
User Offline
Joined: 17th Aug 2004
Location: Tikrit, Iraq
Posted: 11th Sep 2011 23:40
PP is thinking about what i was thinking... should be as simple as a greater than/less than check and moving the variables around in the array accordingly.

PirateJohn
14
Years of Service
User Offline
Joined: 4th Aug 2011
Location: California
Posted: 11th Sep 2011 23:58 Edited at: 12th Sep 2011 00:00
Well, I do recognize the bubble sort, but the issue, of course, is how to sort on one variable THEN sort on another in case the first variable is a tie.

So, the basic question is how do I create a tiebreaker in a regular sorting algorithm?

As for how I store them, I have two integer arrays. The first array is a two dimensional array that stores the value of each individual shot. It is in the format ScoreOfShot(ShooterNumber,ShotTaken), so if the second shooter's fourteenth shot is a score of 9, then ScoreOfShot(2,14) = 9. I have an additional one dimensional array that is the running total score, so TotalScore(ShooterNumbr) = the sum of all ScoreOfShot(ShooterNumber,X)
Pincho Paxton
23
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 12th Sep 2011 00:18 Edited at: 12th Sep 2011 00:24
Ties are left alone, so you don't need to worry about them. Just compare them if you want. You can do a 2 dim version like this...



zenassem
23
Years of Service
User Offline
Joined: 10th Mar 2003
Location: Long Island, NY
Posted: 12th Sep 2011 00:20 Edited at: 12th Sep 2011 00:31
It's a "stable sort". Most simple sorts are stable, including the Bubble Sort, though I usually wind up using an Insertion Sort.

It's as simple as adding a condition to compare the Next field of the items IF and Only if the comparison is EQUAL, keep doing that until a swap is made.

If you want to post up the code you are using to sort, I'll alter it to sort on multiple fields.

Your signature has been erased by a mod please reduce it to 600 x 120.
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 12th Sep 2011 00:28
I couldn't remember the names of the sort algorithms at the time but Pinchos method can be easily implemented, you will just need to prioritise which order ties, and other values will be put.

Warning! May contain Nuts!
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 12th Sep 2011 01:01
@Zenassem,
Great minds...

Here's code that does the job, using an insertion sort:


I've unnecessarily complicated things by using zero-based arrays, and variables that hold the count and not the top item - sorry, I can't work up the enthusiasm to go back and fix that.

The sort itself and the 'swap' function were fairly simple and mechanical to write (I wrote them on 'auto-pilot) - it's the comparison function that you need to think about carefully when comparing multi-valued items.

Alternatively, you can use a stable sort to sort by score 1, then score 2, etc up to score 6, then sort by total score, and you'll get the same result - this is how you do it in Excel when you have more than 3 fields to sort by, as Excel also uses a stable sort (not sure which one though).

PirateJohn
14
Years of Service
User Offline
Joined: 4th Aug 2011
Location: California
Posted: 12th Sep 2011 01:44
Thanks a bunch! I hadn't thought of the idea of a stable sort, either. I'll be sure to test out this code and let you know how it goes.
zenassem
23
Years of Service
User Offline
Joined: 10th Mar 2003
Location: Long Island, NY
Posted: 12th Sep 2011 02:19 Edited at: 12th Sep 2011 02:29
This is what I hate.. lol. I spent time coding A bubblesort since I had no idea when a reply would come. anyways might as well post it, then I'll take a look at Ianm's.


This code was to do the bubsort on just one value


edit: I like Ianm's better as it looks cleaner and it uses the insertion sort I was referring to. I really wasn't going to bother setting up my functions to take parameters or deal with the names. Was just going to show the global solution. I don't have the motivation now to continue it, as seeing I would of normally done it similar to IanM's solution.

Your signature has been erased by a mod please reduce it to 600 x 120.
Pincho Paxton
23
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 12th Sep 2011 02:37
Well whilst were on the subject, this code has been bugging me for days. It's VB 6 code, but it's still sorting code. Everything works OK, but there is a cosmetic Bug. Same data switches around with the members of its own group, and they shouldn't. Like Data 1, and another Data 1 member switch around. they are called Version, and same versions shouldn't switch. All that this means is that their titles which are like.. Page 1, Page 2, Page 3, become Page 3, Page 1, Page 2. But at least the contents are correct. I can't figure it out. The question to swap Version if higher is the first question. If Val(PrinterInfo(N, 2)) > Val(PrinterInfo(N1, 2)) Then PrinterInfo(N,2) is version number. So why does it swap the same ones around?



IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 12th Sep 2011 09:32
Quote: "I like Ianm's better as it looks cleaner and it uses the insertion sort I was referring to"

Actually, I mis-labelled the search - my code implements a selection sort, not an insertion sort.

It's not great for large lists, but is fine for this size of list.

Login to post a reply

Server time is: 2026-07-10 20:11:10
Your offset time is: 2026-07-10 20:11:10