配列のソートについて

Question

配列を出現回数の多い順、且つ同じ場合は当初の配列の順番に並べ替えたいです。
例えば、

a = [4, 6, 2, 2, 6, 4, 4, 4]

を

[4, 4, 4, 4, 6, 6, 2, 2]

に並べ替えたいです。

sorted(a, key=lambda x:a.count(x), reverse=True)

で

[4, 4, 4, 4, 6, 2, 2, 6]

と良い所までいったのですが、そこから先で今止まってしまっています。

Answer 1

安定ソートであることを利用して、二回に分けてソートすると楽です。

src = [4, 6, 2, 2, 6, 4, 4, 4]

dst = sorted(src, key=src.index)
dst = sorted(dst, key=src.count, reverse=True)
print(dst)

実行結果 Wandbox

[4, 4, 4, 4, 6, 6, 2, 2]

ただしlist.indexもlist.countも線型の計算量を要するので、
本来なら前以て評価用のデータを生成しておくのが好ましいです。

例えば、こんなふうに。

key = {}
src = [4, 6, 2, 2, 6, 4, 4, 4]

for i, e in enumerate(src):
    if e in key:
        key[e][0] += 1
    else:
        key[e] = [1, -i]
        
print(key)

dst = sorted(src, key=key.get, reverse=True)
print(dst)

実行結果 Wandbox

{4: [4, 0], 6: [2, -1], 2: [2, -2]}
[4, 4, 4, 4, 6, 6, 2, 2]

発展的な方法

安定基数ソートバケットソート。

import collections


class OrderedCounter(collections.Counter, collections.OrderedDict):
    pass

src = [4, 6, 2, 2, 6, 4, 4, 4]
counter = OrderedCounter(src)

dst = [
    key
    for key, num in counter.most_common()
    for _ in range(num)
]
print(dst)

参考： python - Creating an Ordered Counter - Stack Overflow

Comments

[kosshi_s]

回答ありがとうございました。色々な解決法を提示いただいたこちらをベストアンサーにさせていただきます。

Answer 2

a = [4, 6, 2, 2, 6, 4, 4, 4]
#a = [4, 1, 2, 2, 1, 4, 4, 4] 
sorted(a, key=lambda x:(a.count(x), -a.index(x)), reverse=True)

同じ場合は当初の配列の順番に並べ替えたいです。

この条件を見逃していたためコードを修正しました。

Comments

[LouiS0616]

その方法だと a = [4, 1, 2, 2, 1, 4, 4, 4] のときに要件を満たしません。

[yamap55]

なるほど。「当初の配列の順番」これがありましたね。ご指摘ありがとうございます。