#はじめに
データは集めたら整理するものです．
ここでは，複数のデータを法則に従って並べ替える「ソート」を扱います．

Pythonのソート

Pythonにおいてソートはふつうsort(リスト)かリスト.sortedで行います．
sortedはあくまで「ソート済みの別物」を用意するものですが，sortは指定したリストそのものに手を加えます．
どちらもreverse=Trueとすると降順ソートになります．

sort_sample

l=[1,9,2,8,3]
print(sorted(l))  #[1,2,3,8,9]
print(l) #[1,9,2,8,3] 変わらない
l.sort()
print(l)  #[1,2,3,8,9] 変わった

#降順ソート
print(sorted(l,reverse=True)  #[9,8,3,2,1]
l.sort(reverse=True)
print(l)  #[9,8,3,2,1]

多次元リストのソート

ネストされたリストに対し，「第一要素でソートして，さらに第一要素が同じものは第二要素で比較してソート」といったことをやりたい際は，
一次元リストと同じようにsortあるいはsortedをすれば空気を読んでやってくれます．素晴らしいですね．

nested_list_sort

l = [[1, 2], [1, 1], [3, 5] ,[2, 4], [3, 1]]
print(sorted(l))  #[[1, 1], [1, 2], [2, 4], [3, 1], [3, 5]]

指定された要素だけでソート

「第一要素はどうでもいいから，第二要素だけでソートしたい」時はitemgetterを使うとすっきり書けます．

sort_itemgetter

from operator import itemgetter

l = [[1, 2], [1, 1], [3, 5] ,[2, 4], [3, 1]]
print(sorted(l,key=itemgetter(1))) #[[1, 1], [3, 1], [1, 2], [2, 4], [3, 5]]

また，属性を使ってソートしたい時はattrgetterの出番です．

sort_attrgetter

from operator import attrgetter

class Score:
    def __init__(self, _name, _math, _physics):
        self.name = _name
        self.math = _math
        self.physics = _physics
    
    def show(self):
        print(f'name: {self.name}, math: {self.math}, physics: {self.physics}')

s1 = Score('s1', 10, 20)
s2 = Score('s2', 10, 10)
s3 = Score('s3', 15, 5)
s_list = [s1, s2, s3]

for s in sorted(s_list, key = attrgetter('math')):
    s.show()
'''
name: s1, math: 10, physics: 20
name: s2, math: 10, physics: 10
name: s3, math: 15, physics: 5
'''

for s in sorted(s_list, key = attrgetter('physics')):
    s.show()
'''
name: s3, math: 15, physics: 5
name: s2, math: 10, physics: 10
name: s1, math: 10, physics: 20
'''
for s in sorted(s_list, key = attrgetter('math', 'physics')):
    s.show()
'''
name: s2, math: 10, physics: 10
name: s1, math: 10, physics: 20
name: s3, math: 15, physics: 5
'''

bisect

ソート済みのリストに対して，検索や(リストの末尾以外を含めた)挿入が高速に行えるライブラリです．
ご存じだとは思いますが，ソート済みの配列に対して高速に検索が行える「二分探索」というアルゴリズムがあります．
また，「二分探索木」というデータ構造は挿入や削除に対しても高速で，適切に処理を行うといずれもO(log(N))で行えます．bisectはこの原理に基づき実装されているため高速です．

基本，リストに対して検索などを行うのは低速で，状況に応じてなるべくsetや辞書を使った方がよい(第二回参照)のですが，
どうしてもリストを使わなければならないときは，このライブラリを使って少しでも高速化に努めましょう．

sort_bisect

import bisect

def main():
    l = list(range(100000))  #ソート済みリスト

    for i in range(100000):
        print(bisect.bisect_left(l,i))  #ソート状態を保ったままlにiを入れる位置(複数候補があるなら最も左側)を返す
        bisect.insort_left(l,i)  #ソート状態を保ったままlにiを入れる(複数候補があるなら最も左側)
        #↑をl.insert(0,i)に変えると速度の違いが分かる
        
        
main()

bisectを使った二分探索

上で紹介したように，bisect.bisect_sort(配列，数値)は指定した配列に指定した値を，ソート状態を維持したまま入れるために必要なインデックスを返してくれます．
これを利用し，そのインデックスにおける値が指定した値に等しいかを調べればbisectを使った二分探索が実現できることになります．

bisect_search

import bisect

def bisect_search(a, x):
   i = bisect.bisect_left(a, x)
   if i != len(a) and a[i] == x:
       return i
   raise ValueError

l = [1, 3, 5, 9, 11, 13, 15]
bisect_search(l, 13)  # 5

#おまけ：ソートされた複数のリストをソートされた一つのリストに
何か役に立ちそうなのでついでに記しておきます．
配列を合体させた後のソートが不要になるのでスムーズにbisectを使えるところが地味に嬉しい所です．

sorted_list_merge

import heapq
#ソートされた複数のリストをマージする(ソート)
list(heapq.merge([1, 3, 4], [2, 7, 9], [6, 8]))  #[1, 2, 3, 4, 5, 6, 7, 8, 9]

#おわりに
正確に，そして素早く自分の思った通りのソートができるようになりましょう．