From Gossip@caterpillar

Algorithm Gossip: 得分排行

說明

假設有一教師依學生座號輸入考試分數，現希望在輸入完畢後自動顯示學生分數的排行，當然學生的分數可能相同。

解法

這個問題基本上要解不難，只要使用額外的一個排行陣列走訪分數陣列就可以了，直接使用下面的程式片段作說明：

for(i = 0; i < count; i++) {
    juni[i] = 1;
    for(j = 0; j < count; j++) {
        if(score[j] > score[i])
            juni[i]++;
    }
}

printf("得分\t排行\n");
for(i = 0; i < count; i++)
    printf("%d\t%d\n", score[i], juni[i]);

上面這個方法雖然簡單，但是反覆計算的次數是n^2，如果n值變大，那麼運算的時間就會拖長；改變juni陣列的長度為n+2，並將初始值設定為0，如下所示：

接下來走訪分數陣列，並在分數所對應的排行陣列索引元素上加1，如下所示：

將排行陣列最右邊的元素設定為1，然後依序將右邊的元素值加至左邊一個元素，最後排行陣列中的「分數+1」」就是得該分數的排行，如下所示：

這樣的方式看起來複雜，其實不過在計算某分數之前排行的人數，假設89分之前的排行人數為x人，則89分自然就是x+1了，這也是為什麼排行陣列最右邊要設定為1的原因；如果89分有y人，則88分自然就是x+y+1，整個陣列右邊元素向左加的原因正是如此。

如果分數有負分的情況，由於C/C++或Java等程式語言無法處理負的索引，所以必須加上一個偏移值，將所有的分數先往右偏移一個範圍即可，最後顯示的時候記得減回偏移值就可以了。

實作：C Java Python Scala Ruby

#include <stdio.h> 
#include <stdlib.h> 
#define MAX 100 
#define MIN 0 

int main(void) { 
    int score[MAX+1] = {0}; 
    int juni[MAX+2] = {0}; 
    int count = 0; 

    do { 
       printf("輸入分數，-1結束："); 
       scanf("%d", &score[count++]); 
    } while(score[count-1] != -1);

    count--; 

    int i;
    for(i = 0; i < count; i++) 
        juni[score[i]]++; 
    juni[MAX+1] = 1; 

    for(i = MAX; i >= MIN; i--) 
        juni[i] = juni[i] + juni[i+1]; 

    printf("得分\t排行\n"); 
    for(i = 0; i < count; i++) 
        printf("%d\t%d\n", score[i], juni[score[i]+1]); 

    return 0; 
}

Java

import java.util.*;

public class Rank {
    final static int MAX = 100;
    final static int MIN = 0;
    public static void main(String[] args) {
	Scanner s = new Scanner(System.in);
        
        List<Integer> score = new ArrayList<Integer>();
        while(true) { 
            System.out.print("輸入分數，-1結束："); 
            int i = s.nextInt();
            if(i == -1) 
                break;
            score.add(i);
        } 

        int[] juni = new int[Rank.MAX + 2];
        for(int i : score)
            juni[i]++; 
        juni[Rank.MAX + 1] = 1; 

        for(int i = Rank.MAX; i >= Rank.MIN; i--) 
            juni[i] += juni[i+1]; 

        System.out.println("得分\t排行"); 
        for(int i : score) {
            System.out.println(i + "\t" + juni[i + 1]); 
        }
    }
}

Python

MAX = 100
MIN = 0

score = []

while True:
    s = int(input("輸入分數, -1 結束："))
    if s == -1:
        break
    score.append(s)
    
juni = [0] * (MAX + 2)
for i in range(len(score)):
    juni[score[i]] += 1
juni[MAX + 1] = 1
for i in range(MAX, MIN - 1, -1):
    juni[i] += juni[i + 1]

print("得分\t排行")
for i in range(len(score)):
    print(score[i], "\t", juni[score[i] + 1])

Scala

import scala.collection.mutable.ListBuffer

val MAX = 100
val MIN = 0

val score = new ListBuffer[Int]

var isContinue = true
while(isContinue) {
    print("輸入分數，-1結束：");
    val input = readInt
    if(input == -1)
        isContinue = false
    else 
        score + input
}

val juni = new Array[Int](MAX + 2)
for(i <- score) {
    juni(i) += 1
}
juni(MAX+1) = 1

for(i <- MAX until(MIN, -1)) {
    juni(i) += juni(i+1)
}

println("得分\t排行")
for(i <- score) {
    printf("%d\t%d%n", i, juni(i + 1))
}

Ruby

# encoding: Big5
MAX = 100
MIN = 0

score = []
while true
    print "輸入分數，-1 結束："
    s = gets.to_i
    if s == -1
        break
    end
    score << s
end

juni = Array.new(MAX + 2, 0)
score.length.times { |i|
    juni[score[i]] += 1
}
juni[MAX + 1] = 1
MAX.downto(MIN) { |i|
    juni[i] += juni[i + 1]
}

print "得分\t排行".encode("Big5")
score.length.times { |i|
    print score[i], "\t", juni[score[i] + 1], "\n"
}