정렬 기법¶
파이썬 리스트에는 리스트를 제자리에서(in-place) 수정하는 내장 list.sort() 메서드가 있습니다. 또한, 이터러블로부터 새로운 정렬된 리스트를 만드는 sorted() 내장 함수가 있습니다.
이 문서에서는, 파이썬을 사용하여 데이터를 정렬하는 다양한 기술을 살펴봅니다.
정렬 기초¶
간단한 오름차순 정렬은 매우 쉽습니다; 그저 sorted() 함수를 호출하면 됩니다. 새로운 정렬된 리스트를 반환합니다:
>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]
list.sort() 메서드를 사용할 수도 있습니다. 리스트를 제자리에서 수정합니다 (그리고 혼동을 피하고자 None을 반환합니다). 일반적으로 sorted()보다 덜 편리합니다 - 하지만 원래 목록이 필요하지 않다면, 이것이 약간 더 효율적입니다.
>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]
또 다른 점은 list.sort() 메서드가 리스트에게만 정의된다는 것입니다. 이와 달리, sorted() 함수는 모든 이터러블을 받아들입니다.
>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]
키 함수¶
list.sort() 메서드와 sorted(), min(), max(), heapq.nsmallest(), 그리고 heapq.nlargest() 함수들은 리스트의 각 요소에 대해 비교를 수행하기 전에 호출할 함수(또는 다른 호출 가능 객체)를 지정하는 key 파라미터를 가집니다.
예를 들어, 다음은 str.casefold() 를 사용하여 대소 문자를 구분하지 않고 문자열을 비교하는 경우입니다:
>>> sorted("This is a test string from Andrew".split(), key=str.casefold)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
key 매개 변수의 값은 단일 인자를 취하고 정렬 목적으로 사용할 키를 반환하는 함수(또는 다른 콜러블)여야 합니다. 키 함수가 각 입력 레코드에 대해 정확히 한 번 호출되기 때문에 이 기법은 빠릅니다.
일반적인 패턴은 객체의 인덱스 중 일부를 키로 사용하여 복잡한 객체를 정렬하는 것입니다. 예를 들어:
>>> student_tuples = [
... ('john', 'A', 15),
... ('jane', 'B', 12),
... ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2]) # 나이로 정렬합니다
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
같은 기법이 이름있는 어트리뷰트를 갖는 객체에서도 작동합니다. 예를 들어:
>>> 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) # 나이로 정렬합니다
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
이름이 지정된 속성을 가진 객체는 위와 같이 일반 클래스로 만들 수 있으며, dataclass 또는 named tuple 의 인스턴스로도 만들 수 있습니다.
operator 모듈 함수와 부분 함수 평가¶
위에서 보여준 키 함수 패턴은 매우 일반적이므로, 파이썬은 액세스 함수를 더 쉽고 빠르게 만드는 편리 함수를 제공합니다. 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 모듈은 key 함수를 만드는 데 도움이 되는 또 다른 도구를 제공합니다. partial() 함수는 다중 인자 함수의 arity 를 줄여서 key 함수로 사용하기 적합하게 만들어 줍니다.
>>> 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']
오름차순과 내림차순¶
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)]
정렬 안정성과 복잡한 정렬¶
정렬은 안정적임이 보장됩니다. 즉, 여러 레코드가 같은 키를 가질 때, 원래의 순서가 유지됩니다.
>>> 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')) # 두 번째 키로 정렬합니다
>>> sorted(s, key=attrgetter('grade'), reverse=True) # 이제 첫 번째 키로 내림차순 정렬합니다
[('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)이라고 합니다:
첫째, 초기 리스트가 정렬 순서를 제어하는 새로운 값으로 장식됩니다.
둘째, 장식된 리스트를 정렬합니다.
마지막으로, 장식을 제거하여, 새 순서로 초깃값만 포함하는 리스트를 만듭니다.
예를 들어, DSU 방식을 사용하여 grade로 학생 데이터를 정렬하려면 다음과 같이 합니다:
>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated] # 복원
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
이 관용구는 튜플이 사전식으로 비교되기 때문에 작동합니다; 첫 번째 항목이 비교됩니다; 그들이 같으면 두 번째 항목이 비교되고, 이런 식으로 계속됩니다.
모든 경우에 장식된 리스트에 인덱스 i를 포함할 필요는 없지만, 두 가지 이점이 있습니다:
정렬이 안정적입니다 – 두 항목이 같은 키를 가지면, 그 들의 순서가 정렬된 리스트에 유지됩니다.
장식된 튜플의 순서는 최대 처음 두 항목에 의해 결정되므로 원래 항목은 비교 가능할 필요가 없습니다. 그래서 예를 들어, 원래 리스트에는 직접 정렬될 수 없는 복소수가 포함될 수 있습니다.
이 관용구의 또 다른 이름은 펄 프로그래머들 사이에서 이것을 대중화한 Randal L. Schwartz의 이름을 딴 Schwartzian 변환입니다.
이제 파이썬 정렬이 키 함수를 제공하기 때문에, 이 기법은 자주 필요하지 않습니다.
비교 함수¶
정렬을 위해 절대값을 반환하는 key 함수와 달리, 비교 함수는 두 입력값에 대한 상대적인 순서를 계산합니다.
예를 들어, balance scale 는 두 샘플을 비교하여 가벼움, 같음, 또는 무거움과 같은 상대적 순서를 제공합니다. 마찬가지로 cmp(a, b) 와 같은 비교 함수는 작으면 음수, 입력이 같으면 0, 크면 양수를 반환합니다.
다른 언어에서 알고리즘을 번역할 때 비교 함수를 마주치는 경우가 흔합니다. 또한 일부 라이브러리는 API의 일부로 비교 함수를 제공하기도 합니다. 예를 들어, locale.strcoll() 은 비교 함수입니다.
그러한 상황에 대응하기 위해 파이썬은 비교 함수를 감싸서 key 함수로 사용할 수 있게 하는 functools.cmp_to_key 를 제공합니다:
sorted(words, key=cmp_to_key(strcoll)) # 로케일 인식 정렬 순서
정렬 불가능한 타입 및 값에 대한 전략¶
정렬 시 여러 가지 타입 및 값 관련 문제가 발생할 수 있습니다. 다음은 도움이 될 수 있는 몇 가지 전략입니다:
비교 불가능한 입력 타입을 정렬 전에 문자열로 변환하십시오:
>>> 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 standard 에서 “모든 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 이 다른 타입과 비교 가능하지 않기 때문에 필요합니다.
정렬 전 매핑 타입을 정렬된 아이템 리스트로 변환하십시오:
>>> 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'] 중 하나를 생성할 수 있습니다.
잡동사니¶
로케일 인식 정렬의 경우, 키 함수로는
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 은 6가지 비교 메서드가 모두 구현될 것을 권장합니다. 이 작업을 더 쉽게 수행할 수 있도록@~functools.total_ordering데코레이터가 제공됩니다.키 함수는 정렬되는 객체에 직접 의존할 필요가 없습니다. 키 함수는 외부 자원에 액세스할 수도 있습니다. 예를 들어, 학생 성적이 딕셔너리에 저장되어 있다면, 학생 이름의 별도 리스트를 정렬하는 데 사용할 수 있습니다:
>>> students = ['dave', 'john', 'jane'] >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'} >>> sorted(students, key=newgrades.__getitem__) ['jane', 'dave', 'john']
부분 정렬¶
일부 애플리케이션은 데이터 중 일부만 정렬되면 충분한 경우가 있습니다. 표준 라이브러리는 전체 정렬보다 적은 작업을 수행하는 여러 도구를 제공합니다.
min()과max()은 각각 가장 작은 값과 가장 큰 값을 반환합니다. 이 함수들은 입력 데이터를 한 번만 훑으며(single pass) 거의 추가 메모리를 소모하지 않습니다.heapq.nsmallest()와heapq.nlargest()는 각각 가장 작은 값과 큰 값 n 개를 반환합니다. 이 함수들은 메모리에 한 번에 n 개의 요소만 유지하며 데이터를 한 번 훑습니다. 입력 데이터 수에 비해 n 의 값이 작은 경우, 이 함수들은 전체 정렬보다 훨씬 적은 비교를 수행합니다.heapq.heappush()와heapq.heappop()은 가장 작은 요소를 위치0에 유지하는 부분 정렬된 데이터 구조를 생성하고 유지합니다. 이 함수들은 작업 스케줄링에 흔히 사용되는 우선순위 큐(priority queue)를 구현하는 데 적합합니다.