ソート機能を持たない特定の要素でネストされたリストをソートする。

Question

私はこのようなネストされたリストがある場合：

L = [['James', '1', '2'], ['Alan', '1', '1'], ['Henry', '1', '5']] 

どのように私は最高から最低のソートまたはソート機能を使用せずに、サブリストのそれぞれに最後の数に基づいて、それを並べ替えることができますか？

出力：

final = [['Henry', '1', '5'], ['James', '1', '2'], ['Alan', '1', '1']] 

私はそれを行う方法を知っている唯一の方法は、ソート機能であるが、私はそれなしでそれを行う方法を知っていただきたいと思います。

Answer 1

L = [['James', '1', '2'], ['Alan', '1', '1'], ['Henry', '1', '5']] 

keys = [(int(v[-1]),k) for k,v in enumerate(L)] 
final = [] 

for i in range(len(keys)): 
    #find the next biggest element according to last element of the list. 
    final.append(L[max(keys)[-1]]) 
    keys[max(keys)[-1]] = '' 

final 
Out[83]: [['Henry', '1', '5'], ['James', '1', '2'], ['Alan', '1', '1']] 

Answer 2

実装可能なものは多くあります。sorting algorithmsがあります。 Pythonのsortedビルトインは、Tim Petersによってずっと前にthoughtfully implementedでした。

しかし、ここheapqを使用して別のソートオプションは次のとおりです。

import heapq 
import operator as op 

heapq.nlargest(len(L), L, key=op.itemgetter(-1)) 
# [['Henry', '1', '5'], ['James', '1', '2'], ['Alan', '1', '1']] 

比較すると、いくつかの直感的なオプションを持っている、sortedとの類似性に気づく：

import operator as op 

expected = [['Henry', '1', '5'], ['James', '1', '2'], ['Alan', '1', '1']] 

r1 = sorted(L, key=op.itemgetter(-1))[::-1] 
r2 = sorted(L, key=op.itemgetter(-1), reverse=True) 
r3 = list(reversed(sorted(L, key=op.itemgetter(-1)))) 

assert r1 == r2 == r3 == expected 

sortedは、一部の例外を除いて、一般的に高速ですheapqがより高速です。詳細については、this postも参照してください。

Answer 3

独自のquicksort関数を記述することができます。あなたは、出力を反転する兆しをほとんど切り替えることができます

def quicksort(arr): 
    if len(arr) <= 1: 
     return arr 

    pivot = arr[len(arr)/2] 

    left = [x for x in arr if x > pivot] 
    middle = [x for x in arr if x == pivot] 
    right = [x for x in arr if x < pivot] 

    return quicksort(left) + middle + quicksort(right) 

次のステップは、あなたが適切な数字を抽出していることを確認すること、そしてあなたができるように、親リストにそれらをバックにマッピングできることを確認します再び右の場所にそれらをドロップ - Allen's answerは良い方法があります。

L = [['James', '1', '2'], ['Alan', '1', '1'], ['Henry', '1', '5']] 

keys = [(int(v[-1]),k) for k,v in enumerate(L)] # This line here 

その行基本的に私たちは並べ替えたい番号を格納タプルのリストを作成し、包括的なリストで、その番号の親リストのインデックス。したがって、基本的には、Lの場合、keys = [(2, 0), (1, 1), (5, 2)]です。

def quicksort(arr): 
    # Put the actual sorting function into a subfunction that can be called recursively 
    def subsort(arr2): 
     if len(arr2) <= 1: 
      return arr2 
     pivot = arr2[len(arr2)/2] 
     left = [x for x in arr2 if x > pivot] 
     middle = [x for x in arr2 if x == pivot] 
     right = [x for x in arr2 if x < pivot] 
     return subsort(left) + middle + subsort(right) 

    # Get the value-key pairs and sort them 
    keys = [(int(v[-1]),k) for k,v in enumerate(L)] 
    keys = subsort(keys) 

    # Do the mapping back to the original array fed into the main function 
    final = [] 
    for i in keys: 
     final.append(arr[i[1]]) 

    return final 

そして、それを持つ：

>>> L = [['James', '1', '2'], ['Alan', '1', '1'], ['Henry', '1', '5']] 
>>> quicksort(L) 
[['Henry', '1', '5'], ['James', '1', '2'], ['Alan', '1', '1']] 

注：

は、だからあなたは再帰的に使用することができますサブ関数を作成することによって、このすべてを説明するために quicksort機能を変更したいです最後の位置に同じ番号のアイテムが2つある場合、元のリスト内の元の相対位置（互いに）を得ることになる 。タプルの比較の詳細については、 this answerを参照してください。 の降順でここにの順序でソートしています（そうでない場合は、元の位置を互いに対して保持しています）。だから：

>>> L = [['Simon', '1', '2'], ['Henry', '1', '5'], ['Finn', '1', '2'] 
>>> quicksort(L) 
[['Henry', '1', '5'], ['Finn', '1', '2'], ['Simon', '1', '2']]