安定ソートであることを利用して、二回に分けてソートすると楽です。
Python
1src = [4, 6, 2, 2, 6, 4, 4, 4]
2
3dst = sorted(src, key=src.index)
4dst = sorted(dst, key=src.count, reverse=True)
5print(dst)
実行結果 Wandbox
ただしlist.indexもlist.countも線型の計算量を要するので、
本来なら前以て評価用のデータを生成しておくのが好ましいです。
例えば、こんなふうに。
Python
1key = {}
2src = [4, 6, 2, 2, 6, 4, 4, 4]
3
4for i, e in enumerate(src):
5 if e in key:
6 key[e][0] += 1
7 else:
8 key[e] = [1, -i]
9
10print(key)
11
12dst = sorted(src, key=key.get, reverse=True)
13print(dst)
実行結果 Wandbox
{4: [4, 0], 6: [2, -1], 2: [2, -2]}
[4, 4, 4, 4, 6, 6, 2, 2]
発展的な方法
安定基数ソートバケットソート。
Python
1import collections
2
3
4class OrderedCounter(collections.Counter, collections.OrderedDict):
5 pass
6
7src = [4, 6, 2, 2, 6, 4, 4, 4]
8counter = OrderedCounter(src)
9
10dst = [
11 key
12 for key, num in counter.most_common()
13 for _ in range(num)
14]
15print(dst)
参考: python - Creating an Ordered Counter - Stack Overflow
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/08/29 21:20