파이썬 정렬 기법

파이썬 정렬 기법 (Sorting Techniques)

파이썬에서 데이터를 정렬하는 방법은 의외로 자주 헷갈리는 주제인데요. 리스트를 그 자리에서(in-place) 정렬하는 list.sort() 메서드와, 새 정렬된 리스트를 만들어 돌려주는 sorted() 내장 함수. 이름이 비슷해 보이지만 쓰임새가 조금씩 달라요. 이 HOWTO에서는 이 두 도구를 시작으로, 키 함수(key function), 안정 정렬, 복합 정렬 같은 테크닉을 실제 코드와 함께 차근차근 살펴봅니다.

출처: Python 공식 문서 — Sorting HOW TO

정렬의 기본 (Sorting Basics)

오름차순 정렬은 아주 간단합니다. 그냥 sorted() 함수를 호출하면 되거든요. 새로 정렬된 리스트를 돌려줍니다.

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

list.sort() 메서드를 쓸 수도 있어요. 이 메서드는 리스트를 그 자리에서 수정하고(혼동을 피하기 위해 None을 돌려줍니다) 원래의 리스트가 필요 없다면 sorted()보다 약간 더 효율적이에요. 다만 보통은 sorted()가 더 편리하죠.

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

또 하나의 차이는 list.sort() 메서드가 리스트에만 정의되어 있다는 점입니다. 반면 sorted() 함수는 어떤 iterable이든 받아들여요.

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

키 함수 (Key Functions)

list.sort() 메서드와 sorted(), min(), max(), heapq.nsmallest(), heapq.nlargest() 함수들에는 key 매개변수가 있습니다. 비교를 하기 전에 각 리스트 요소에 호출할 함수(또는 다른 callable)를 지정하는 역할을 해요.

예를 들어 str.casefold()를 사용한 대소문자 무시 문자열 비교가 이렇습니다.

>>> sorted("This is a test string from Andrew".split(), key=str.casefold)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

key 매개변수의 값은 인자 하나를 받고 정렬에 사용할 키를 돌려주는 함수(또는 다른 callable)여야 합니다. 이 방식은 빠른데, 키 함수가 각 입력 레코드마다 정확히 한 번씩만 호출되기 때문이에요.

흔한 패턴으로는 복잡한 객체를 객체의 인덱스 일부를 키로 삼아 정렬하는 것입니다. 예를 들면:

>>> student_tuples = [
...     ('john', 'A', 15),
...     ('jane', 'B', 12),
...     ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

이 기법은 이름 붙은 속성(named attribute)을 가진 객체에도 똑같이 적용됩니다.

>>> class Student:
...     def __init__(self, name, grade, age):
...         self.name = name
...         self.grade = grade
...         self.age = age
...     def __repr__(self):
...         return repr((self.name, self.grade, self.age))
>>>
>>> student_objects = [
...     Student('john', 'A', 15),
...     Student('jane', 'B', 12),
...     Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age)   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

이름 붙은 속성을 가진 객체는 위처럼 일반 클래스로 만들 수도 있고, dataclass나 named tuple의 인스턴스일 수도 있습니다.

operator 모듈 함수와 부분 함수 평가 (Operator Module Functions and Partial Function Evaluation)

위에서 본 키 함수 패턴은 아주 흔해서, 파이썬은 접근자(accessor) 함수를 더 쉽고 빠르게 만들 수 있는 편의 함수를 제공합니다. operator 모듈에는 itemgetter(), attrgetter(), 그리고 methodcaller() 함수가 있어요.

이 함수들을 쓰면 위 예시들이 더 간단하고 빨라집니다.

>>> from operator import itemgetter, attrgetter
>>>
>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>>
>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

operator 모듈 함수는 여러 수준의 정렬을 지원합니다. 예를 들어 grade 순으로 정렬한 다음 age 순으로 정렬하려면:

>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
>>>
>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

functools 모듈은 키 함수를 만드는 또 하나의 유용한 도구를 제공합니다. partial() 함수는 여러 인자를 받는 함수의 인자 개수(arity)를 줄여서 키 함수로 쓸 수 있게 만들어 줘요.

>>> from functools import partial
>>> from unicodedata import normalize
>>>
>>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split()
>>>
>>> sorted(names, key=partial(normalize, 'NFD'))
['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë']
>>>
>>> sorted(names, key=partial(normalize, 'NFC'))
['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana']

오름차순과 내림차순 (Ascending and Descending)

list.sort()와 sorted() 둘 다 부울 값을 갖는 reverse 매개변수를 받습니다. 내림차순 정렬을 나타내는 데 쓰이죠. 예를 들어 학생 데이터를 age 역순으로 얻으려면:

>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>>
>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

정렬 안정성과 복합 정렬 (Sort Stability and Complex Sorts)

파이썬 정렬은 안정적(stable)이라고 보장됩니다. 즉 여러 레코드가 같은 키를 가질 때 원래 순서가 유지된다는 뜻이에요.

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

blue에 대한 두 레코드가 원래 순서를 유지해서 ('blue', 1)이 ('blue', 2)보다 앞에 오는 것이 보장되는 걸 볼 수 있어요.

이 멋진 성질 덕분에 여러 단계의 정렬을 연속으로 하여 복합 정렬을 만들 수 있습니다. 예를 들어 학생 데이터를 grade 내림차순, 그 다음 age 오름차순으로 정렬하려면 age 정렬을 먼저 하고 grade로 다시 정렬하면 됩니다.

>>> s = sorted(student_objects, key=attrgetter('age'))     # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True)       # now sort on primary key, descending
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

이를 래퍼 함수로 추상화해서, 리스트와 (필드, 순서) 튜플들을 받아 여러 회차로 정렬하게 만들 수도 있어요.

>>> def multisort(xs, specs):
...     for key, reverse in reversed(specs):
...         xs.sort(key=attrgetter(key), reverse=reverse)
...     return xs
>>>
>>> multisort(list(student_objects), (('grade', True), ('age', False)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

파이썬이 사용하는 Timsort 알고리즘은 데이터셋에 이미 존재하는 어떤 정렬도 활용할 수 있기 때문에 여러 번의 정렬을 효율적으로 수행합니다.

Decorate-Sort-Undecorate

이 관용구는 세 단계에서 이름을 따 Decorate-Sort-Undecorate라고 불러요.

먼저, 정렬 순서를 좌우할 새 값들로 초기 리스트를 장식(decorate)합니다.
둘째, 장식된 리스트를 정렬합니다.
마지막으로, 장식을 제거(undecorate)해서 원래 값들만 새 순서로 담긴 리스트를 만듭니다.

예를 들어 DSU 방식으로 학생 데이터를 grade 순으로 정렬하면:

>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated]               # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

이 관용구는 튜플이 사전식(lexicographically)으로 비교되기 때문에 동작합니다. 첫 번째 항목들을 비교하고, 같으면 두 번째 항목들을 비교하는 식으로요.

장식된 리스트에 인덱스 i를 포함하는 것이 모든 경우에 꼭 필요한 건 아닙니다. 다만 포함하면 두 가지 이점이 있어요.

정렬이 안정적입니다 – 두 항목이 같은 키를 가지면 정렬된 리스트에서도 순서가 유지돼요.
원래 항목들이 비교 가능할 필요가 없습니다. 장식된 튜플의 순서는 기껏해야 처음 두 항목으로 결정되거든요. 예를 들어 원래 리스트가 직접 정렬할 수 없는 복소수를 담고 있어도 괜찮다는 뜻입니다.

이 관용구의 또 다른 이름은 Schwartzian transform인데, Perl 프로그래머들 사이에서 이를 널리 알린 Randal L. Schwartz의 이름을 딴 것입니다.

이제 파이썬 정렬이 키 함수를 제공하기 때문에, 이 기법이 자주 필요하지는 않게 되었어요.

비교 함수 (Comparison Functions)

정렬을 위한 절대 값을 돌려주는 키 함수와 달리, 비교 함수(comparison function)는 두 입력의 상대적인 순서를 계산합니다.

예를 들어 저울(balance scale)은 두 표본을 비교해 상대적인 순서(더 가벼움, 같음, 더 무거움)를 알려주죠. 마찬가지로 cmp(a, b) 같은 비교 함수는 작으면(a < b) 음수, 같으면 0, 크면(a > b) 양수를 돌려줍니다.

다른 언어의 알고리즘을 번역할 때 비교 함수를 마주치는 일이 흔합니다. 또한 일부 라이브러리는 API의 일부로 비교 함수를 제공하기도 해요. 예를 들어 locale.strcoll()이 비교 함수입니다.

이런 상황에 대처하기 위해 파이썬은 functools.cmp_to_key를 제공하는데, 비교 함수를 감싸 키 함수로 쓸 수 있게 만들어 줍니다.

sorted(words, key=cmp_to_key(strcoll))  # locale-aware sort order

정렬 불가능한 타입과 값에 대한 전략 (Strategies For Unorderable Types and Values)

정렬할 때 여러 타입·값 관련 문제가 생길 수 있습니다. 도움이 되는 전략 몇 가지를 볼게요.

비-비교 가능한 입력 타입을 정렬 전에 문자열로 변환합니다:

>>> data = ['twelve', '11', 10]
>>> sorted(map(str, data))
['10', '11', 'twelve']

대부분의 타입 간 비교가 TypeError를 일으키기 때문에 필요합니다.

정렬 전에 특수 값을 제거합니다:

>>> from math import isnan
>>> from itertools import filterfalse
>>> data = [3.3, float('nan'), 1.1, 2.2]
>>> sorted(filterfalse(isnan, data))
[1.1, 2.2, 3.3]

IEEE-754 표준이 "모든 NaN은 자기 자신을 포함해 무엇과도 순서 없는(unordered) 비교를 한다"고 규정하기 때문에 필요해요.

마찬가지로 None도 데이터셋에서 제거할 수 있습니다.

>>> data = [3.3, None, 1.1, 2.2]
>>> sorted(x for x in data if x is not None)
[1.1, 2.2, 3.3]

None이 다른 타입과 비교 불가능하기 때문에 필요합니다.

매핑(mapping) 타입을 정렬 전에 정렬된 항목 리스트로 변환합니다:

>>> data = [{'a': 1}, {'b': 2}]
>>> sorted(data, key=lambda d: sorted(d.items()))
[{'a': 1}, {'b': 2}]

딕셔너리끼리의 비교가 TypeError를 일으키기 때문에 필요합니다.

집합(set) 타입을 정렬 전에 정렬된 리스트로 변환합니다:

>>> data = [{'a', 'b', 'c'}, {'b', 'c', 'd'}]
>>> sorted(map(sorted, data))
[['a', 'b', 'c'], ['b', 'c', 'd']]

집합 타입에 담긴 요소들은 결정적인 순서를 갖지 않기 때문에 필요해요. 예를 들어 list({'a', 'b'})는 ['a', 'b'] 또는 ['b', 'a'] 중 무엇이든 만들 수 있습니다.

그 밖에 이것저것 (Odds and Ends)

로케일 인식 정렬에는 키 함수로 locale.strxfrm()을 쓰거나 비교 함수로 locale.strcoll()을 사용하세요. 기반 알파벳이 같더라도 "알파벳순" 정렬 순서는 문화에 따라 다를 수 있기 때문에 필요합니다.
reverse 매개변수는 정렬 안정성을 유지합니다(같은 키를 가진 레코드는 원래 순서를 유지한다는 뜻). 흥미롭게도 그 효과는 매개변수 없이 내장 reversed() 함수를 두 번 써서 흉내 낼 수 있어요.

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> standard_way = sorted(data, key=itemgetter(0), reverse=True)
>>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))
>>> assert standard_way == double_reversed
>>> standard_way
[('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]

정렬 루틴은 두 객체를 비교할 때 <를 사용합니다. 그래서 __lt__() 메서드를 정의하면 클래스에 표준 정렬 순서를 쉽게 추가할 수 있어요.

>>> Student.__lt__ = lambda self, other: self.age < other.age
>>> sorted(student_objects)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

다만 __lt__()가 구현되어 있지 않으면 <가 __gt__()를 대신 사용할 수 있다는 점을 유의하세요(메커니즘의 자세한 내용은 object.__lt__() 참조). 놀라움을 피하기 위해 PEP 8은 여섯 개의 비교 메서드를 모두 구현할 것을 권장합니다. 이 작업을 쉽게 해 주는 @functools.total_ordering 데코레이터가 제공됩니다.

키 함수는 정렬되는 객체들에 직접 의존할 필요가 없습니다. 외부 자원에 접근할 수도 있어요. 예를 들어 학생 성적이 딕셔너리에 저장되어 있다면, 그것을 사용해 별개의 학생 이름 리스트를 정렬할 수 있습니다.

>>> students = ['dave', 'john', 'jane']
>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
>>> sorted(students, key=newgrades.__getitem__)
['jane', 'dave', 'john']

부분 정렬 (Partial Sorts)

어떤 애플리케이션은 데이터의 일부만 정렬하면 됩니다. 표준 라이브러리는 전체 정렬보다 일을 적게 하는 도구 몇 가지를 제공해요.

min()과 max()는 각각 가장 작은 값과 가장 큰 값을 돌려줍니다. 이 함수들은 입력 데이터를 한 번만 훑고 거의 보조 메모리를 필요로 하지 않습니다.
heapq.nsmallest()와 heapq.nlargest()는 각각 가장 작은 n개의 값과 가장 큰 n개의 값을 돌려줍니다. 이 함수들은 한 번에 n개의 요소만 메모리에 유지하면서 데이터를 한 번 훑어요. 입력 수에 비해 n이 작은 값일 때, 이 함수들은 전체 정렬보다 훨씬 적은 비교를 수행합니다.
heapq.heappush()와 heapq.heappop()은 가장 작은 요소를 위치 0에 유지하는 부분 정렬된 데이터 배치를 만들고 유지합니다. 이 함수들은 태스크 스케줄링에 흔히 쓰이는 우선순위 큐(priority queue)를 구현하는 데 적합합니다.

파이썬 정렬 기법