Это должно сработать:
freqs = sorted([frequency[x]/float(n) for x in frequency], reverse=True)
Если вы хотите больше походить на оператор печати, который вы указали выше, попробуйте следующее:
for (fxn, fx, x) in sorted([(frequency[x]/float(n), frequency[x], x) for x in frequency], reverse=True):
print x, fx, fxn