CODEWITHSUNDEEP
algorithmsorting
Projectile Fish
Projectile Fish

Reputation: 955

Sorting Based on Score

I have an 1D array containing a set of rankings. e.g.

0|0
1|2
2|2
3|1
4|0
5|1

(the first column shown here is the array index)

which i'd like to rank like so

1|2
2|2
3|1
5|1
0|0
4|0

Notice that the indexes stay in numerically ascending order when there is a tie. What sort of algorithm should I be looking at to do this?

Upvotes: 1

Views: 1244

Answers (4)

9dan
9dan

Reputation: 4282

Hmm.. is that stability important?

Isn't is sort on ranking?

If data has other attributes beside rank we'd better include that attributes in compare operation.

Stable sort can incur unnecessary performance penalties with added complexity.

Upvotes: 0

divegeek
divegeek

Reputation: 5022

What you're looking for is a "stable" sorting algorithm, one that doesn't reorder elements that compare as equal. You didn't say what language or toolset you're using, so I can't tell you what, specifically to use. Instability is an inherent feature of some algorithms, others can be implemented in either stable or unstable forms. Generally, library sort algorithms will choose a stable implementation if possible.

Upvotes: 4

aaronasterling
aaronasterling

Reputation: 71004

As other posters have answered, you probably want a stable sort. Stable sorting algorithms include

If I was to choose, I would probably go with merge sort because it has the best complexity. Insertion sort can beat it on small lists though. I remember reading that there's one case where Bubble Sort isn't terrible but I forget what it is.

However, it's worth noting that worrying about stability will rule out an algorithm like quicksort which may be the algorithm that your unspecified language uses in its sorting functions.

Whatever language you're using, its sort implementation should be able to take a function that will compare two items and establish which one is "greater". So all you really need to do is write a function which

  • If the ranks are equal, claims that the items with the greater numerical indice is "greater"
  • If the ranks are not equal, claims that the item with the greater rank is "greater".
  • If both rank and numerical index are are equal, claims that they are equal.

This is just sorting the items 'lexicographically' using whatever sort algorithm comes with the language and removes the need for stability assuming that you can consider two items to be equal if they have the same index.

The precise protocol that this function follows will vary from language to language.

Upvotes: 5

BlackBear
BlackBear

Reputation: 22979

Don't know how efficient or good it is, but:

// suppose you have scores[n]

for c1 = 1 to n
    for c2 = c1 + 1 to n
        if scores[c2]>scores[c1] then swap them

Upvotes: 1

Related Questions