Webページでは数式を表すためにLaTeX表記が使えるMathJaxを利用しています。 WebブラウザにはSafari/Chrome/Firefoxを使って下さい（IEでは表示できないようです。）

Pythonの並べ替えを使う

Pythonではリスト型を含むデータの並び（イテラブル）に適用できる並べ替え関数 sorted( ) が用意され、またリスト型のメソッドとしても sort( ) が定義されている。

>>> sorted([2,5,6,1,7,23,15,19,30,-4])
[-4, 1, 2, 5, 6, 7, 15, 19, 23, 30]
>>> sorted([2,5,6,1,7,23,15,19,30,-4], reverse=True)
[30, 23, 19, 15, 7, 6, 5, 2, 1, -4]

>>> a=[2,5,6,1,7,23,15,19,30,-4]
>>> a.sort()
>>> a
[-4, 1, 2, 5, 6, 7, 15, 19, 23, 30]
>>> a=[2,5,6,1,7,23,15,19,30,-4]
>>> a.sort(reverse=True)
>>> a
[30, 23, 19, 15, 7, 6, 5, 2, 1, -4]

文字列の並べ替え

文字列の並べ替えは辞書式順序に従う。

>>> list=['zoo', 'ocean', 'sea', 'apple', 'orange', 'air']
>>> sorted(list)
['air', 'apple', 'ocean', 'orange', 'sea', 'zoo']

>>> list.sort(reverse=True)
>>> list
['zoo', 'sea', 'orange', 'ocean', 'apple', 'air']

数値文字列の並べ替え

数値文字列からなるリストを並べ替えると、辞書式に並べ替えられるために思ったようにはならない。

>>> nlist = ["99", "129", "92", "116", "43", "75", "219", "8", "68"]
>>> sorted(nlist)
['116', '129', '219', '43', '68', '75', '8', '92', '99']

>>> flist = ["9.9", "12.9", "9.2", "1.16", "43", "7.5", "21.9", "8", "6.8"]
>>> sorted(flist)
['1.16', '12.9', '21.9', '43', '6.8', '7.5', '8', '9.2', '9.9']
>>> sorted(flist, key=float)
['1.16', '6.8', '7.5', '8', '9.2', '9.9', '12.9', '21.9', '43']

こうした場合には、キーワード key を使い、次のようにして比較関数 に渡すキーを渡すキャスト関数を指定する。

>>> sorted(nlist, key=int)
['8', '43', '68', '75', '92', '99', '116', '129', '219']

ディクショナリのキーと値で並べ替える

Pythonのディクショナリ型は キーと値 をコロン(:) で挟んで「キー: 値」としたものを、カンマ(,)で区切って並べて中括弧 { と } で囲った構造

{'キー1':値1, 'キー2':値2, ......}

ディクショナリ fruites

fruits = {'apple': 20, 'orange': 15, 'lemon':30, 'grape'; 25, 'melon': 5, 'berry': 40}

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# sort dictionary data w.r.t. keys and balues

fruits = {'apple': 20, 'orange': 15, 'lemon':30, 'grape': 25, 'lemon': 35, 'melon': 5, 'berry': 40, 'lemon': 45}

# confirm contents of dictionary
for (k, v) in fruits.items():
    print 'key: %-10s, value: %4d' % (k, v)
print

# sort w.r.t. dictionary's keys
for k in sorted(fruits.keys()):
    print 'key: %-10s, value: %4d' % (k, fruits[k])
print

# sort w.r.t. dictionary's values
for v in sorted(fruits.values()):
    print 'value', v
print

レコードの並べ替え

$n$個の属性を持つレコードを $n$タプル ($a_1,a_2,\dots,a_n$) で表そう。 この$n$-タプルを並べてレコードデータ

records =[(a1,..,an), (b1,..,bn), (c1,..,cn),....]

persons =[
('taro', 'm', 19), ('jiro', 'm', 18), ('hanako','f',18), ('sakura','f',19)
]

次のスクリプト sort_records.py では、モジュールの operator の関数 operator.itemgetter() を使って、レコードデータを複数段階で並べ替えていることに注意する。 12行目では、2番目のタプル（age）をキーとしてレコードデータ persons を並べ替えて sort1 とし、16行目ではさらに並べ替えたレコードデータ sort1 を0番目のタプル(name)をキーとして並べ替えている。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# sort record data

from operator import itemgetter

persons =[
('taro', 'm', 19), ('jiro', 'm', 18), ('hanako','f',18), ('sakura','f',19)
]

print "First stage:"
sort1 = sorted(persons, key=itemgetter(2))
print sort1

print "Second stage:"
sort2 = sorted(sort1, key=itemgetter(0))
print sort2

$ ./sort_records.py
First stage:
[('jiro', 'm', 18), ('hanako', 'f', 18), ('taro', 'm', 19), ('sakura', 'f', 19)]
Second stage:
[('hanako', 'f', 18), ('jiro', 'm', 18), ('sakura', 'f', 19), ('taro', 'm', 19)]

並べ替えの安定性

Python組み込みの並べ替えは、並べ替えの安定性(stable)が保証されている。 並べ替えが安定であるとは、レコードデータ中に同一キーを持つレコードが複数ある場合、並べ替えた後に並べ替え前のレコードの順序関係が維持されるということである。

上のスクリプト sort_records.py では、レコードの並べ替えキーをタプルの2番目（age）として並び替えたたとき、jiroのレコードはhanakoの前に位置していたことが保存されている（taroについてもsakuraよりも前にあった）。 sort_records.py は、この並び替えの安定性を利用して複数の並べ替えを段階的に実現していることに注意しよう。

並べ替えることで、並べ替え前の位置関係が崩れるような並べ替えを不安定な並べ替えという。 いうまでもなく、並べ替えが高速で終了し、しかも安定であるような並べ替えアルゴリズムの採用が望ましい。

データの並べ替えは最も基本的な計算処理の一部をなしており、その効率化は計算時間の短縮に大きな影響を及ぼす。