2

I'm currently working on a software project in Swift that requires several different types of sorting mechanisms. I have been searching, to no avail, to find an algorithm to do a sort with tie-breaking. In other words, say you have a data set that could be represented like so:

[Name Of Data]:[Someone's ID]-[Same Someone's Score],[Someone's ID]-[Same Someone's Score],[etc...]\n
[Name Of Data]:[Someone's ID]-[Same Someone's Score],[Someone's ID]-[Same Someone's Score],[etc...]\n
[etc...]

One line, then, may look like this:

Wins:7-1,8-1,9-1,2-1,10-1,3-0,4-0,5-0,1-0,6-0

And another looks like this:

SpeakerPoints:6-26,2-20,4-19,7-17,8-16,9-16,5-16,1-12,3-11,10-8

I would like to be able to sort the IDs in terms of 'winner', where the 'Wins' criteria is 1st priority, and if there is a tie, the program would move to the 'SpeakerPoints' criteria, and so on...

Ordinarily I would use a platform specific mechanism (like LINQ for Windows or NSSortDescriptor for MacOS). However, the project is "Shared Code" that should compile on any platform necessary. If it matters, I'm using Silver, an implementation of Apple's Swift that compiles for Windows/MacOS/iOS/Android/etc... targets, so I am basically limited to using "pure swift" (Pure swift code works perfectly well). How might I implement a Sort to do this? I don't care about the algorithm being super efficient (though I don't want a simple sort to take hours either, I could do that myself :P), a modified bubble sort would be fine as long as it returned the correctly sorted ID's.

As a complication, the number of criteria is also a variable: this time it may be wins and speakerPoints, but next time may include opponentWins

  • If so many sort fields are identical, does it really matter which one goes first? – Robert Harvey Aug 11 '16 at 4:04
  • @RobertHarvey- no, it doesn't matter how 'wins' is ordered, as long as the scores themselves are sorted high-low. It is simply a waste of time to sort by score then id if you have to sort again for a tie break. Plus after round 6 or 7, the score's differences increase drastically and similar fields are less of an issue – Will Aug 11 '16 at 4:34
  • 5
    I don't get it. Sorting stuff of type A is always based on an ordering of As. No one ever said that a comparison has to only consider 'wins'. How is your question different from just if (a.wins > b.wins) +1 else if (b.wins > a.wins) -1 else { similar comparison on speakerPoints }? – Frank Aug 11 '16 at 5:49
1

When implementing a sort algorithm you need only create a function which returns greater, equal or less than when given two inputs. You dont need to worry about the absolute value of wins + speaker points + whatever.

So use or create an arbitrary sort algorithm (for example, a bubble sort) which just uses an injected:

IComparer
{
    Int Compare(x, y); // return 1,0,-1
}

Then you can write a concrete implementation with the required, compare wins, compare speaker points etc.

You can imagine more genric solutions where you inject an array of IComparers. But might be best to keep it simple to begin with.

  • not sure what you mean, but we usualy agree. Feel free to edit the answer – Ewan Aug 14 '16 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.